A Predictor-Corrector Algorithm for P _∗(κ)-Linear Complementarity Problems Based on a Specific Self-Regular Proximity Function

Abstract

First-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior point methods. In Peng et al. (SIAM J. Optim. 15(4):1105–1127, 2005), based on a specific proximity function, a wide neighborhood of the central path is defined which matches the standard large neighborhood defined by the infinity norm. In this paper, we extend the predictor-corrector algorithm proposed for linear optimization in Peng et al. (SIAM J. Optim. 15(4):1105–1127, 2005) to P _∗(κ)-linear complementarity problems. Our algorithm performs two kinds of steps. In corrector steps, we use the specific self-regular proximity function to compute the search directions. The predictor step is the same as the predictor step of standard predictor-corrector method in the interior point method literature. We prove that our predictor-corrector algorithm has an ${\mathcal {O}}\left ((1+2\kappa )\sqrt {n}\log n\log \frac {(x^{0})^{T} s^{0}}{\epsilon }\right )$ iteration bound, which is the best known iteration complexity for problems of this type.