A path following method for LCP with superlinearly convergent iteration sequence

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.