Optimization Online


Curvature Integrals and Iteration Complexities in SDP and Symmetric Cone Programs

Satoshi Kakihara(s-kakihara***at***grips.ac.jp)
Atsumi Ohara(ohara***at***fuee.u-fukui.ac.jp)
Takashi Tsuchiya(tsuchiya***at***grips.ac.jp)

Abstract: 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.

Keywords: interior-point methods, primal-dual algorithms, path-following methods, iteration complexities, curvature, semidefinite programming, symmetric cone programs

Category 1: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 09/30/2011
Entry Accepted: 09/30/2011
Entry Last Modified: 09/30/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society