A Polynomial-Iteration Infeasible Interior-Point Algorithm with Arc-Search for Semidefinite optimization

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 s-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 (n(3/2) L) 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.

Automated summary

This paper introduces an arc-search infeasible interior-point algorithm for semidefinite optimization, demonstrating its complexity order. Furthermore, through a simplified version of the algorithm, it is proven that the iteration complexity bound of the algorithm is equivalent to the best iteration bound for feasible interior-point algorithms.