Skip to Main content Skip to Navigation
Journal articles

Log-barrier interior point methods are not strongly polynomial

Xavier Allamigeon 1 Pascal Benchimol 2 Stéphane Gaubert 1 Michael Joswig 3 
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
Abstract : 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(2^r)$. 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.
Complete list of metadata
Contributor : Xavier Allamigeon Connect in order to contact the contributor
Submitted on : Wednesday, January 3, 2018 - 6:55:54 PM
Last modification on : Friday, February 4, 2022 - 3:23:59 AM

Links full text



Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig. Log-barrier interior point methods are not strongly polynomial. SIAM Journal on Applied Algebra and Geometry, Society for Industrial and Applied Mathematics 2018, 2 (1), pp.140-178. ⟨10.1137/17M1142132⟩. ⟨hal-01674959⟩



Record views