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)

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.

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

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

zbMATH Keywords

linear programmingtropical geometrycentral pathcontinuous analogue of Hirsch conjecture

Mathematics Subject Classification ID

Interior-point methods (90C51)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• -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)

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

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)