Log-barrier interior point methods are not strongly polynomial
arXiv:1708.01544 · doi:10.1137/17M1142132
Abstract
We prove that primal-dual log-barrier interior point methods are not strongly polynomial, by constructing a family of linear programs with inequalities in dimension for which the number of iterations performed is in . The total curvature of the central path of these linear programs is also exponential in , disproving a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko. Our method is to tropicalize the central path in linear programming. The tropical central path 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.
arXiv commentThis paper supersedes arXiv:1405.4161. 31 pages, 5 figures, 1 table
References in corpus (8)
- Duality and separation theorems in idempotent semimodules
- Tropicalizing the simplex algorithm
- Minimal half-spaces and external representation of tropical polyhedra
- A Field of Generalised Puiseux Series for Tropical Geometry
- Tropical spectrahedra
- The central curve in linear programming
- On the Curvature of the Central Path of Linear Programming Theory
- Long and winding central paths
Cited by in corpus (18)
- Tropical spectrahedra
- Tropical medians by transportation
- Parametric shortest-path algorithms via tropical geometry
- Approximating the Volume of Tropical Polytopes is Difficult
- The tropical analogue of the Helton-Nie conjecture is true
- Tropical bisectors and Voronoi diagrams
- An Invitation to Tropical Alexandrov Curvature
- Tropical Gaussians: A Brief Survey
- Face posets of tropical polyhedra and monomial ideals
- Asymmetric tropical distances and power diagrams
- A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
- Detecting tropical defects of polynomial equations
- Convergent Hahn Series and Tropical Geometry of Higher Rank
- The complexity of geometric scaling
- The degree of the central curve in semidefinite, linear, and quadratic programming
- Oriented Matroids from Triangulations of Products of Simplices
- The tropicalization of the entropic barrier
- Formalizing the Face Lattice of Polyhedra