Improved Complexity Analysis of Full Nesterov-Todd Step Interior-Point Methods for Semidefinite Optimization

摘要

In this paper, we present an improved convergence analysis of full Nesterov-Todd step feasible interior-point method for semidefinite optimization, and extend it to the infeasible case. This improvement due to a sharper quadratic convergence result, which generalizes a known result in linear optimization and leads to a slightly wider neighborhood for the iterates in the feasible algorithm and for the feasibility steps in the infeasible algorithm. For both versions of the full Nesterov-Todd step interior-point methods, we derive the same order of the iteration bounds as the ones obtained in linear optimization case.