  


Information Geometry and PrimalDual Interiorpoint Algorithms
Satoshi Kakihara(Satoshi_Kakiharamist.i.utokyo.ac.jp) Abstract: In this paper, we study polynomialtime interiorpoint algorithms in view of information geometry. We introduce an information geometric structure for a conic linear program based on a selfconcordant 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 predictorcorrector primal pathfollowing algorithm is represented based on this geometry and (its asymptotic) iterationcomplexity is related to an integral involving the embedding curvature. Then we focus on the classical linear program and primaldual algorithm. We will study an integral over the central trajectory which represents the number of iterations of the MizunoToddYe predictorcorrector (MTYPC) 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 interiorpoint 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 MTYPC 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 primaldual 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 interiorpoint algorithms: complexity estimate via curvature integral (December, 2007).” Keywords: interiorpoint methods, informaion geometry, polynomialtime 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, 103 Midoricho, Tachikawa, Tokyo, 1908562, Japan. Download: [PDF] Entry Submitted: 05/14/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  