What tropical geometry tells us about the complexity of linear programming

Tropical geometry has been recently used to obtain new complexity results in convex optimization and game theory. In this paper, we present an application of this approach to a famous class of algorithms for linear programming, i.e., log-barrier interior point methods. We show that these methods are not strongly polynomial by constructing a family of linear programs with 3r + 1 inequalities in dimension 2r for which the number of iterations performed is in Ω (2r). The total curvature of the central path of these linear programs is also exponential in r, disproving a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky, and Zinchenko. These results are obtained by analyzing the tropical central path, which is the piecewise linear limit of the central paths of parameterized families of classical linear programs viewed through "logarithmic glasses." This allows us to provide combinatorial lower bounds for the number of iterations and the total curvature in a general setting.