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.
Citation
Technical Report, Department of Mathematics and Statistics, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore, MD 21250, July, 2012