A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy

Abstract

Abstract In this paper, we propose a Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization using the arc-search strategy. The proposed algorithm searches for optimizers along the ellipses that approximate the central path and ensures that the duality gap and the infeasibility have the same rate of decline. By analyzing, we obtain the iteration complexity O ( r log ε − 1 ) $\mathcal{O}(r\log \varepsilon^{-1})$ for the Nesterov-Todd direction, where r is the rank of the associated Euclidean Jordan algebra and ε is the required precision. To our knowledge, the obtained complexity bounds coincide with the currently best known theoretical complexity bounds for infeasible symmetric optimization.

Keywords

• symmetric optimization
• infeasible-interior-point method
• arc-search
• Mizuno-Todd-Ye predictor-corrector
• iteration complexity