  


An Information Geometric Approach to Polynomialtime Interiorpoint Algorithms: Complexity Bound via Curvature Integral
Ohara Atsumi (oharasys.es.osakau.ac.jp) Abstract: In this paper, we study polynomialtime interiorpoint 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 selfconcordant barrier functions, and develop a precise iterationcomplexity estimate of the polynomialtime interiorpoint 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 ``primaldual curvature" integral bound established by Monteiro and Tsuchiya, which is based on the work of Vavasis and Ye of the layeredstep interiorpoint 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 differentialgeometric characterization of the primaldual curvature in the primaldual algorithm. Finally, in view of this integral bound, we observe that the primal (or dual) interiorpoint algorithm requires fewer number of iterations than the primaldual interiorpoint algorithm at least in the case of linear programming. Keywords: interiorpoint methods, information 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 Citation: Research Memorandum No.1055, The Institute of Statistical Mathematics, Tokyo, Japan, December 2007 Download: [PDF] Entry Submitted: 12/29/2007 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  