On quadratic andO\left( {\sqrt {nL} } \right) 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.Research supported in part by NSF Grants DDM-8922636 and DDM-9207347, and an Interdisciplinary Research Grant of the University of Iowa, Iowa Center for Advanced Studies.