RESEARCH ARTICLE On Extending Some Wide-neighborhood Interior Point Algorithms From Linear Programming To Linear Complementarity Problems

This paper establishes the polynomial convergence of a new class of path-following methods for linear complementarity problems (LCP) whose search directions are obtained by applying Newton's method to the central path equation Xz = e; Mx c = z: Speci cally, we show that the short-step path-following methods based on the L1 norm neighborhood and the semilong-step path-following methods based on the L1 seminorm neighborhood have the iteration-complexity bounds of O(n), respectively