Superlinearly convergent infeasible-interior-point algorithm for degenerate LCP

A large-step infeasible path-following method is proposed for solving general linear complementarity problems with sufficient matrices. If the problem has a solution, the algorithm is superlinearly convergent from any positive starting points, even for degenerate problems. The algorithm generates points in a large neighborhood of the central path. Each iteration requires only one matrix factorization and at most three (asymptotically only two) backsolves. It has been recently proved that any sufficient matrix is a P*(kappa)-matrix for some kappa greater than or equal to 0. The computational complexity of the algorithm depends on kappa as well as on a feasibility measure of the starting point. If the starting point is feasible or close to being feasible, then the iteration complexity is O((1 + kappa)root nL). Otherwise, for arbitrary positive and large enough starting points, the iteration complexity is O((1 + kappa)(2)nL). We note that, while computational complexity depends on kappa, the algorithm itself does not.