Optimization Online


Information Geometry and Primal-Dual Interior-point Algorithms

Satoshi Kakihara(Satoshi_Kakihara***at***mist.i.u-tokyo.ac.jp)
Atsumi Ohara(ohara***at***sys.es.osaka-u.ac.jp)
Takashi Tsuchiya(tsuchiya***at***grips.ac.jp)

Abstract: In this paper, we study polynomial-time interior-point algorithms in view of information geometry. We introduce an information geometric structure for a conic linear program based on a self-concordant barrier function. Riemannian metric is defined with the Hessian of the barrier function. We introduce two connections $\nabla$ and $\nabla^*$ which roughly corresponds to the primal and the dual problem. The dual feasible region is embedded in the primal cone and thus we consider the primal and dual problems in the same space. Characterization of the central trajectory and its property in view of the curvature is studied. A predictor-corrector primal path-following algorithm is represented based on this geometry and (its asymptotic) iteration-complexity is related to an integral involving the embedding curvature. Then we focus on the classical linear program and primal-dual algorithm. We will study an integral over the central trajectory which represents the number of iterations of the Mizuno-Todd-Ye predictor-corrector (MTY-PC) algorithm. We will show that this integral admits a rigorous differential geometric expression involving the embedding curvature. Connecting this expression to an integral bound previously obtained by Monteiro and Tsuchiya in relation to the layered interior-point algorithm by Vavasis and Ye, we prove a global geometric theorem on the central trajectory. Finally, we demonstrate that the integral value by itself provides an accurate estimate of the number of iterations of the MTY-PC algorithm through numerical experiments with fairly large practical instances from Netlib problems such as DFL001 and PILOT87. This leads to an interesting conclusion: the number of iterations of the standard primal-dual algorithm is the value of a differential geometric curvature integral over the central trajectory. This paper is a revised version of the paper A. Ohara and T. Tsuchiya: an imformation geometric approach to interior-point algorithms: complexity estimate via curvature integral (December, 2007).

Keywords: interior-point methods, informaion geometry, polynomial-time algorithm, linear programming, semidefinite programming, embedding curvature, computational complexity, differential geometry, convex programming

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Research Memorandum No.1120 The Institute of Statistical Mathematics, 10-3 Midori-cho, Tachikawa, Tokyo, 190-8562, Japan.

Download: [PDF]

Entry Submitted: 05/14/2010
Entry Accepted: 05/14/2010
Entry Last Modified: 05/14/2010

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 Programming Society