|
Abstract
|
In this paper, we propose an arc-search infeasible interior-point algorithm with infeasible central path wide neighborhood for semidefinite optimization. In every iteration, the algorithm uses an analytic expression of an ellipse and searches an ε-approximation solution of the problem along an ellipsoidal approximation of the infeasible central path. Based on the commutative class of scaling matrices at an iterate (X,S)≻(0,0), we show that the algorithm has the complexity order O(n32L) to Nesterov-Todd (NT) search directions, which coincides with the results for the corresponding algorithm for linear optimization. Then, we present a simplified version of the algorithm and show that the iteration complexity bound of the algorithm is the same as the best iteration bound for feasible interior-point algorithms.
|