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).”
Citation
Research Memorandum No.1120 The Institute of Statistical Mathematics, 10-3 Midori-cho, Tachikawa, Tokyo, 190-8562, Japan.