ON THE CONVERGENCE OF A CLASS OF INFEASIBLE INTERIOR-POINT METHODS FOR THE HORIZONTAL LINEAR COMPLEMENTARITY-PROBLEM

Interior-point methods require strictly feasible points as starting points. In theory, this requirement does not seem to be particularly restrictive, but it can be costly in computation. To overcome this deficiency, most existing practical algorithms allow positive but infeasible starting points and seek feasibility and optimality simultaneously. Algorithms of this type shall be called infeasible interior-point algorithms. Despite their superior performance, existing infeasible interior-point algorithms still lack a satisfactory demonstration of theoretical convergence and polynomial complexity This paper studies a popular infeasible interior-point algorithmic framework that was implemented for linear programming in the highly successful interior-point code OBI [I. J. Lustig, R. E. Marsten, and D. F. Shanno, Linear Algebra Appl., 152 (1991), pp. 191-222]. For generality, the analysis is carried out on a horizontal linear complementarity problem that includes linear and quadratic programming, as well as the standard linear complementarity problem. Under minimal assumptions, it is demonstrated that with properly controlled steps the algorithm converges at a global Q-linear rate. Moreover, with properly chosen starting points it is established the algorithm can obtain epsilon-feasibility and epsilon-complementarity in at most O(n(2) In(1/epsilon)) iterations.