High order long-step methods for solving linear complementarity problems

The paper is concerned with methods for solving linear complementarity problems (LCP) that are monotone or at least sufficient in the sense of Cottle, Pang and Venkateswaran. A basic concept of interior-point-methods is the concept of (perhaps weighted) feasible or infeasible interior-point paths. They converge to a solution of the LCP if a natural path parameter, usually the current duality gap, tends to 0. After reviewing some basic analyticity properties of these paths it is shown how these properties can be used to devise also long-step path-following methods (and not only predictor–corrector type methods) for which the duality gap converges Q-superlinearly to 0 with an arbitrarily high order.