In this paper, we study iteration complexities of Mizuno-Todd-Ye predictor-corrector (MTY-PC) algorithms in SDP and symmetric cone programs by way of curvature integrals. The curvature integral is defined along the central path, reflecting the geometric structure of the central path. The idea to exploit the curvature of the central path for the analysis of iteration complexities is based on the intuitive observation that path-following algorithms trace faster in relatively straight parts than in the rest of the curved parts. Our analyses in this paper are direct extensions to SDP and symmetric cone programs, of Monteiro and Tsuchiya, which gave a rigorous asymptotic estimate on iteration complexity of MTY-PC algorithms in Linear programming using the aforementioned curvature integral by tending the opening of the neighborhood to zero. More specifically, we give concrete formulas for curvature integrals in SDP and symmetric cone programs and give asymptotic estimates for iteration complexities. In particular, we conduct numerical experiments in practically large SDP problems from SDPLIB, which suggests that our results serve as a useful analytical tool for various SDP problems.
Article
View Curvature Integrals and Iteration Complexities in SDP and Symmetric Cone Programs