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

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 O(n(5/4) log epsilon(-1)), where n is the dimension of the problem and epsilon is the required precision.