A Predictor-corrector Infeasible-interior-point Algorithm for Semidefinite Optimization in a Wide Neighborhood

Abstract

In this paper, we propose a predictor-corrector infeasible interior-point algorithm for semidefinite optimization based on the Nesterov-Todd scaling scheme. In each iteration, the algorithm computes the new iterate using a new combination of the predictor and corrector directions. Using the Ai-Zhang’s wide neighborhood for linear complementarity problems, and extended to semidefinite optimization by Li and Terlaky, it is shown that the iteration complexity bound of the algorithm is $𝒪\left(n^{\frac{5}{4}}\log {\epsilon }^{-1}\right)$ , where n is the dimension of the problem and ɛ is the required precision.