High Order Infeasible-Interior-Point Methods for Solving Sufficient Linear Complementarity Problems

In this paper we develop systematically infeasible-interior-point methods of arbitrarily high order for solving horizontal linear complementarity problems that are sufficient in the sense of Cottle, Pang and Venkateswaran (1989). The results apply to degenerate problems and problems having no strictly complementary solution. Variants of these methods are described that eventually avoid recentering steps, and for which all components of the approximate solutions converge superlinearly at a high order, and other variants which even terminate with a solution of the complementarity problem after finitely many steps.