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.
Citation
Research Memorandum No.1055, The Institute of Statistical Mathematics, Tokyo, Japan, December 2007