Optimization Online


An Information Geometric Approach to Polynomial-time Interior-point Algorithms: Complexity Bound via Curvature Integral

Ohara Atsumi (ohara***at***sys.es.osaka-u.ac.jp)
Takashi Tsuchiya (tsuchiya***at***sun312.ism.ac.jp)

Abstract: In this paper, we study polynomial-time interior-point algorithms in view of information geometry. Information geometry is a differential geometric framework which has been successfully applied to statistics, learning theory, signal processing etc. We consider information geometric structure for conic linear programs introduced by self-concordant barrier functions, and develop a precise iteration-complexity estimate of the polynomial-time interior-point algorithm based on an integral of (embedding) curvature of the central trajectory in a rigorous differential geometrical sense. We further study implication of the theory applied to classical linear programming, and establish a surprising link to the strong ``primal-dual curvature" integral bound established by Monteiro and Tsuchiya, which is based on the work of Vavasis and Ye of the layered-step interior-point algorithm. By using these results, we can show that the total embedding curvature of the central trajectory, i.e., the aforementioned integral over the whole central trajectory, is bounded by $O(n^{3.5}\log (\bar\chi_A^*+n))$ where $\bar\chi_A^*$ is a condition number of the coefficient matrix $A$ and $n$ is the number of nonnegative variables. In particular, the integral is bounded by $O(n^{4.5} m)$ for combinatorial linear programs including network flow problems where $m$ is the number of constraints. We also provide a complete differential-geometric characterization of the primal-dual curvature in the primal-dual algorithm. Finally, in view of this integral bound, we observe that the primal (or dual) interior-point algorithm requires fewer number of iterations than the primal-dual interior-point algorithm at least in the case of linear programming.

Keywords: interior-point methods, information 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

Citation: Research Memorandum No.1055, The Institute of Statistical Mathematics, Tokyo, Japan, December 2007

Download: [PDF]

Entry Submitted: 12/29/2007
Entry Accepted: 12/29/2007
Entry Last Modified: 03/31/2009

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