|
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κ)√n log n log (x0)T s0
iteration bound, which is the best known iteration
complexity for problems of this type.
|