Predictor-corrector method for nonlinear complementarity problem

Recently, Ye et al. proved that the predictor-corrector method proposed by Mizuno et al. maintains O(√n L)-iteration complexity while exhibiting the quadratic convergence of the dual gap to zero under very mild conditions. This impressive result becomes the best-known in the interior point methods. In this paper, we modify the predictor-corrector method and then extend it to solving the nonlinear complementarity problem. We prove that the new method has a (√n log(1/ε))-iteration complexity while maintaining the quadratic asymptotic convergence.