ON QUADRATIC AND O(ROOT-N L) CONVERGENCE OF A PREDICTOR CORRECTOR ALGORITHM FOR LCP

Recently several new results have been developed for the asymptotic (local) convergence of polynomial-time interior-point algorithms. It has been shown that the predictor-corrector algorithm for linear programming (LP) exhibits asymptotic quadratic convergence of the primal-dual gap to zero, without any assumptions concerning nondegeneracy, or the convergence of the iteration sequence. In this paper we prove a similar result for the monotone linear complementarity problem (LCP), assuming only that a strictly complementary solution exists. We also show by example that the existence of a strictly complementarity solution appears to be necessary to achieve superlinear convergence for the algorithm.