# Log-barrier interior point methods are not strongly polynomial

arXiv: https://arxiv.org/abs/1708.01544 · HTML: https://mlsanity.com/paper/1708.01544/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Aug 2017.

## Built on by (most cited first, 1 of 1)

- [Toric Geometry of Entropic Regularization](https://mlsanity.com/paper/2202.01571/) (2022)

## Abstract (arXiv)

We prove that primal-dual log-barrier interior point 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 Omega(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. 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.