Optimization Online


On a class of superlinearly convergent polynomial time interior point methods for sufficient LCP

Florian A. Potra(potra***at***math.umbc.edu)
Josef Stoer(jstoer***at***mathematik.uni-wuerzburg.de)

Abstract: A new class of infeasible interior point methods for solving sufficient linear complementarity problems requiring one matrix factorization and $m$ backsolves at each iteration is proposed and analyzed. The algorithms from this class use a large $(\caln_\infty^-$) neighborhood of an infeasible central path associated with the complementarity problem and an initial positive, but not necessarily feasible, starting point. The Q-order of convergence of the complementarity gap, the residual, and the iteration sequence is $m+1$ for problems that admit a strict complementarity solution and $(m+1)/2$ for general sufficient linear complementarity problems. The methods do not depend on the handicap $\kappa$ of the sufficient LCP. If the starting point is feasible (or ``almost" feasible) the proposed algorithms have ${\cal O}( (1+\kappa)(1+\log\sqrt[m]{1+\kappa}\,) \sqrt{n}\;L)$ iteration complexity, while if the starting point is ``large enough" the iteration complexity is ${\cal O}((1+\kappa)^{2+1/m}(1+\log\sqrt[m]{1+\kappa}\,){n}\;L )$.

Keywords: linear complementarity, interior point, affine scaling, large neighborhood, superlinear convergence

Category 1: Complementarity and Variational Inequalities

Citation: Technical Report TR2008-2, Department of Mathematics and Statistics, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore, MD 22150, USA, February/2008.

Download: [PDF]

Entry Submitted: 03/03/2008
Entry Accepted: 03/03/2008
Entry Last Modified: 03/03/2008

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 Programming Society