The Riemannian Geometry Underlying the Interior-Point Algorithm for Linear Programming

In this talk, we will formulate the Riemannian metric and the corresponding affine connection for the Riemannian geometry underlying Karmarkar's algorithm for linear programming. We obtain continuous trajectories generated by the algorithm as the solution of an associated variational problem. We then introduce the concept of relative curvature of one Riemannian metric w.r.t. to another and analyze the length and relative curvature of the continuous trajectories to shed some light on the logarithmic number of iterations required by the algorithm.