Jv. Burke et S. Xu, The global linear convergence of a noninterior path-following algorithm for linear complementarity problems, MATH OPER R, 23(3), 1998, pp. 719-734
A noninterior path-following algorithm is proposed for the linear complemen
tarity problem. The method employs smoothing techniques introduced by Kanzo
w. If the LCP is P-0 + R-0 and satisfies a nondegeneracy condition due to F
ukushima, Luo, and Pang, then the algorithm is globally linearly convergent
. As with interior point path-following methods, the convergence theory rel
ies on the notion of a neighborhood for the central path. However, the choi
ce of neighborhood differs significantly from that which appears in the int
erior point literature. Numerical experiments are presented that illustrate
the significance of the neighborhood concept for this class of methods.