Infeasible path following algorithms for linear complementarity problems
Florian A. Potra and J. Frederic Bonnans
A generalized class of infeasible-interior-point methods for solving
horizontal linear complementarity problem is analyzed and sufficient
conditions are given for the convergence of the sequence of iterates
produced by methods in this class. In particular it is shown that the
largest step path following algorithms generates convergent iterates
even when starting from infeasible points. The computational
complexity of the latter method is discussed in detail and its local
convergent rate is analyzed. The primal-dual gap of the iterates
produced by this method is superlinearly convergent to zero. A variant
of the method has quadratic convergence.
INRIA Research Report RR-2445, December 1994.