The global linear convergence of a non--interior
path--following algorithm for linear complementarity
Jim Burke and Song Xu
A non--interior path following algorithm is proposed for the linear
complementarity problem. The method employs smoothing techniques
introduced by Kanzow. Under suitable hypotheses, the algorithm is
shown to be 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
appears in the interior point literature.
Numerical experiments are presented that illustrate the significance of the
neighborhood concept for non--interior path following algorithms.
Technical report, Department of Mathematics,
University of Washington, Seattle, WA 98195,