A Mehrotra-Type Predictor-Corrector Algorithm for $P_*(\kappa)$ Linear Complementarity Problems

Abstract:

      Mehrotra-type predictor-corrector algorithm, as one of most efficient interior point methods, has become the backbones of most optimization packages. Salahi et al. proposed a cut strategy based algorithm for linear optimization that enjoyed polynomial complexity and maintained its efficiency in practice. We extend their algorithm to $P_*(\kappa)$ linear complementarity problems. The way of choosing corrector direction for our algorithm is different from theirs. The new algorithm has been proved to have an ${\mathcal O}((1+4\kappa)(17+19\kappa)\sqrt{1+2\kappa}n^\frac{3}{2}\log \frac{(x^0)^\T s^0}{\varepsilon})$ worst case iteration complexity bound. An numerical experiment verifies the feasibility of the new algorithm.