Optimization Online


Information Geometry and Interior-Point Algorithms 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: This paper is a continuation of the paper Kakihara, Ohara and Tsuchiya by the authors where they demonstrated that the number of iterations of Mizuno-Todd-Ye predictor-corrector primal-dual interior-point methods for SDP and more generally symmetric cone programs is (asymptotically) expressed with an integral over the central trajectory called ``curvature integral." It was shown that the number of the iterations of the algorithm is approximated surprisingly well with the integral for fairly large problems of LP and SDP with thousands of variables. In this paper, we demonstrate that the curvature integral admits a rigorous differential geometric expression in view of information geometry. Our result is a direct extension of Ohara and Tsuchiya in linear programming to SDP and symmetric cone programs, using the results for curvature integrals of primal-dual algorithms in SDP and symmetric cone programs in Kakihara, Ohara and Tsuchiya. Together with the numerical evidence in that paper, we claim that the number of iterations of the interior-point algorithm is expressed as a differential geometric quantity.

Keywords: interior-point methods, primal/dual algorithms, primal-dual algorithms, iteration complexities, curvature integral, semidefinite programming, symmetric cone programs, information geometry

Category 1: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 09/30/2011
Entry Accepted: 09/30/2011
Entry Last Modified: 10/10/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