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 )$.
Citation
Technical Report TR2008-2, Department of Mathematics and Statistics, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore, MD 22150, USA, February/2008.