Second-order Predictor-corrector Interior-point Algorithm for Linear Complementarity Problems Based on a Wide Neighbourhood

In this paper, we present a new second-order predictor-corrector interior-point method for solving monotone linear complementarity problem. The algorithm is based on the wide neighborhood of the central path and modified corrector directions. We show that, in addition to the predictor step, each corrector step decreases the duality gap as well. We also prove that the iteration complexity of the proposed algorithm coincides with the best iteration bound for small neighborhood algorithms that use the Nesterov-Todd direction

Keywords:

linear complementarity problems , predictor-corrector method , wide neighborhood , polynomial complexity