The Geometry of Linear Programming
In 1984 Narendra Karmarkar discovered a new polynomial time linear programming algorithm which is an interior point algorithm. This algorithm is apparently competitive with the simplex method in practice. This talk describes joint work with David Bayer on a geometric structure underlying this algorithm, which is the set of trajectories determined by the "infinitesimal" version of the algorithm. These trajectories are algebraic curves, and are also geodesics of a certain non-Euclidean geometry defined inside the polytope of feasible solutions i Rn. They have a simple relation to trajectories of a completely integrable Hamiltonian dynamical system. The algebraic nature of the trajectories leads to their being defined outside the polytope as well and in fact they exist as Rieman surfaces embedded in Pn(C). Algebraic information about these Riemann surfaces is presumably related in a mysterious way to convergence properties of Karmarkar's and related algorithms. New directions for linear programming algorithms exploiting this geometric structure are described.