## A path following method for LCP with superlinearly convergent iteration sequence

### Florian A. Potra and Ronquin Sheng

A new algorithm for solving linear complementarity problems with sufficient matrices is
proposed. If the problem has a solution the algorithm is superlinearly convergent from any
positive starting points, even for degenerate problems. Each iteration requires only one
matrix factorization and at most two backsolves. Only one backsolve is necessary if the
problem is known to be nondegenerate. The algorithm generates points in a large
neighborhood of the central path and has the lowest iteration complexity obtained so far
in the literature. Moreover, the iteration sequence converges superlinearly to a maximal
solution with the same $Q$-order as the complementarity sequence.

Reports on Computational Mathematics, No. 69, Department of Mathematics, University of
Iowa, April, 1995.