PREDICTOR-CORRECTOR METHOD FOR LINEAR COMPLEMENTARITY-PROBLEMS WITH POLYNOMIAL COMPLEXITY AND SUPERLINEAR CONVERGENCE

We extend the Mizuno-Todd-Ye predictor-corrector algorithm for solving monotone linear complementary problems. We prove that the extended algorithm is globally Q-linearly convergent and solves problems with integer data of bitlength L in at most O(square-root nL) interations. We also prove that the duality gap converges to zero Q-superlinearly for problems having strictly complemetary solutions. Our results generalize the results obtained by Ye, Tapia, and Zhang for linear programming