Optimization Online


Interior point methods for sufficient LCP in a wide neighborhood of the central path with optimal iteration complexity

Florian A. Potra(potra***at***umbc.edu)

Abstract: Three interior point methods are proposed for sufficient horizontal linear complementarity problems (HLCP): a large update path following algorithm, a first order corrector-predictor method, and a second order corrector-predictor method. All algorithms produce sequences of iterates in the wide neighborhood of the central path introduced by Ai and Zhang. The algorithms do not depend on the handicap $\kappa$ of the problem, so that they can be used for any sufficient HLCP. They have $O((1+\kappa)\sqrt{n}L)$ iteration complexity, the best iteration complexity obtained so far by any interior point method for solving sufficient linear complementarity problems. The first order corrector-predictor method is Q-quadratically convergent for problem that have a strict complementarity solution. The second order corrector-predictor method is superlinearly convergent with Q order 1.5 for general problems, and with Q order 3 for problems that have a strict complementarity solution.

Keywords: linear complementarity, interior point, path-following, corrector-predictor, sufficient matrix, wide neighborhood

Category 1: Complementarity and Variational Inequalities

Category 2: Linear, Cone and Semidefinite Programming

Citation: Technical Report, Department of Mathematics and Statistics, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore, MD 21250, July, 2012

Download: [PDF]

Entry Submitted: 07/11/2012
Entry Accepted: 07/11/2012
Entry Last Modified: 07/11/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society