|
Abstract
|
This paper proposes a second-order corrector infeasible interior-point method for semidefinite
optimization in a large neighborhood of the central path. Our algorithm uses the Nesterov–
Todd search directions as a Newton direction. We make use of the scaled Newton directions
for symmetric search directions. Based on Ai and Zhang idea, we decompose the Newton
directions into two orthogonal directions corresponding to positive and negative parts of the
right-hand side of the Newton equation. In such a way, we use different step lengths for each
of them and the corrector step is multiplied by the square of the step length of the infeasible
directions in the expression of the new iterate. Starting with a point (X0, y0, S0) in the
neighborhood in terms of Frobenius norm, we showthat the algorithm terminates after at most
O(n
5
4 log ε
−1) iterations, improving by a factor n
14
results on these kinds of algorithms. We
believe that this is the first infeasible interior-point algorithm in a large neighborhood, which
uses a Newton direction decomposition and a second-order corrector step to improve the
iteration complexity.The main difference of the proposed method comparing with the existing
methods in literature is the strategy for generating corrector directions. Some preliminary
numerical results are given to verify the efficiency of the algorithm.
|