The global linear convergence of a noninterior path-following algorithm for linear complementarity problems. (English) Zbl 0977.90056

Summary: A noninterior path-following algorithm is proposed for the linear complementarity problem. The method employs smoothing techniques introduced by Kanzow. If the LCP is \(P_0+ R_0\) and satisfies a nondegeneracy condition due to Fukushima, Luo, and Pang, then the algorithm is globally linearly convergent. As with interior point path-following methods, the convergence theory relies on the notion of a neighborhood for the central path. However, the choice of neighborhood differs significantly from that which applies in the interior point literature. Numerical experiments are presented that illustrate the significance of the neighborhood concept for this class of methods.


90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Full Text: DOI Link