Print

 

A Predictor-Corrector Algorithm for P (κ)-Linear Complementarity Problems Based on a Specific Self-Regular Proximity Function
B. Kheirfam, K. Ahmadi

 

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 O((1+2κ)nlognlog(x0)Ts0ϵ) iteration bound, which is the best known iteration complexity for problems of this type.