Log-Barrier Interior Point Methods Are Not Strongly Polynomial

DOI10.1137/17M1142132zbMATH Open1391.90637OpenAlexW2745127509WikidataQ117245035 ScholiaQ117245035MaRDI QIDQ4564017FDOQ4564017

Authors Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig 

Publication date 12 June 2018

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.01544

zbMATH Keywords

linear programmingtropical geometrycentral pathcontinuous analogue of Hirsch conjecture

Mathematics Subject Classification ID

Interior-point methods (90C51)

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.

Recommendations

• No self-concordant barrier interior point method is strongly polynomial
• A weighted logarithmic barrier interior-point method for linearly constrained optimization
• A polynomial-time interior-point method for conic optimization, with inexact barrier evaluations
• Logarithmic-barrier decomposition interior-point methods for stochastic linear optimization in a Hilbert space
• A polynomial-time interior-point algorithm based on a local self-concordant finite barrier function
• A logarithm barrier method for semi-definite programming
• scientific article; zbMATH DE number 4100957
• A logarithm barrier method for linear programming
• Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming
• A note on the use of vector barrier parameters for interior-point methods

Cites work

• scientific article; zbMATH DE number 4164543 (Why is no real title available?)
• scientific article; zbMATH DE number 1944711 (Why is no real title available?)
• scientific article; zbMATH DE number 1503621 (Why is no real title available?)
• scientific article; zbMATH DE number 195007 (Why is no real title available?)
• scientific article; zbMATH DE number 6437647 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• scientific article; zbMATH DE number 2221693 (Why is no real title available?)
• -convexity
• A Complexity Analysis for Interior-Point Algorithms Based on Karmarkar’s Potential Function
• A Field of Generalised Puiseux Series for Tropical Geometry
• A Variant of the Vavasis--Ye Layered-Step Interior-Point Algorithm for Linear Programming
• A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
• A modified layered-step interior-point algorithm for linear programming
• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A primal-dual interior point method whose running time depends only on the constraint matrix
• A simple variant of the Mizuno-Todd-Ye predictor-corrector algorithm and its objective-function-free complexity
• A strongly polynomial algorithm for solving two-sided linear systems in max-algebra
• Asymptotics of the Perron eigenvalue and eigenvector using max-algebra
• Central path curvature and iteration-complexity for redundant Klee-Minty cubes
• Convergence behavior of Karmarkar's projective algorithm for solving a simple linear program
• Duality and separation theorems in idempotent semimodules.
• Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
• Examples of ill-behaved central paths in convex optimization
• Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra
• Handbook of Hilbert geometry
• Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs
• Interior path following primal-dual algorithms. I: Linear programming
• Linear Programs and Convex Hulls Over Fields of Puiseux Fractions
• Logarithmic limit sets of real semi-algebraic sets
• Minimal half-spaces and external representation of tropical polyhedra
• NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING
• Non-archimedean amoebas and tropical varieties
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• On the Performance of Karmarkar’s Algorithm over a Sequence of Iterations
• On the complexity of following the central path of linear programs by linear extrapolation. II
• On the curvature of the central path of linear programming theory
• On the number of iterations of Karmarkar's algorithm for linear programming
• On the total curvature of tropical hypersurfaces
• On the worst case complexity of potential reduction algorithms for linear programming
• Polytopes and arrangements: diameter and curvature
• The Logarithmic Limit-Set of an Algebraic Variety
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The central curve in linear programming
• The real field with convergent generalized power series
• Tropical Polytopes and Cellular Resolutions
• Tropical algebraic geometry
• Tropical convexity
• Tropicalizing the simplex algorithm
• polymake: a framework for analyzing convex polytopes

Cited in

(29)

• Tropical Ehrhart theory and tropical volume
• On the central path of semidefinite optimization: degree and worst-case convergence rate
• Massively parallel computation of tropical varieties, their positive part, and tropical Grassmannians
• Parametric shortest-path algorithms via tropical geometry
• Formalizing the face lattice of polyhedra
• Universal Analytic Gröbner Bases and Tropical Geometry
• Formalizing the Face Lattice of Polyhedra
• Computing complex and real tropical curves using monodromy
• Asymmetric tropical distances and power diagrams
• Tropical Gaussians: a brief survey
• Short-step methods are not strongly polynomial-time
• Tropical spectrahedra
• Convergent Hahn series and tropical geometry of higher rank
• The tropical analogue of the Helton-Nie conjecture is true
• Detecting tropical defects of polynomial equations
• An invitation to tropical Alexandrov curvature
• Approximating the volume of tropical polytopes is difficult
• The degree of the central curve in semidefinite, linear, and quadratic programming
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• Face posets of tropical polyhedra and monomial ideals
• Tropical combinatorial Nullstellensatz and sparse polynomials
• Tropical medians by transportation
• Toric geometry of entropic regularization
• Tropical bisectors and Voronoi diagrams
• Tropical Carathéodory with matroids
• The complexity of geometric scaling
• Computing zero-dimensional tropical varieties via projections
• Abstract tropical linear programming
• What Tropical Geometry Tells Us about the Complexity of Linear Programming

Describes a project that uses

Uses Software

• polymake

This page was built for publication: Log-Barrier Interior Point Methods Are Not Strongly Polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4564017)