Log-Barrier Interior Point Methods Are Not Strongly Polynomial

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

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

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

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

Cited In (30)

• 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
• Exact algorithms for semidefinite programs with degenerate feasible set
• Universal Analytic Gröbner Bases and Tropical Geometry
• An invitation to tropical Alexandrov curvature
• On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• Parametric Shortest-Path Algorithms via Tropical Geometry
• Abstract tropical linear programming
• Tropical Carathéodory with matroids
• 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
• 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
• Title not available (Why is that?)
• 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

Recommendations

• Logarithmic barrier decomposition-based interior point methods for stochastic symmetric programming 👍 👎
• A logarithm barrier method for semi-definite programming 👍 👎
• Polynomial-time interior-point algorithm based on a local self-concordant finite barrier function 👍 👎
• A Polynomial-Time Interior-Point Method for Conic Optimization, With Inexact Barrier Evaluations 👍 👎
• A note on the use of vector barrier parameters for interior-point methods 👍 👎
• Logarithmic-Barrier Decomposition Interior-Point Methods for Stochastic Linear Optimization in a Hilbert Space 👍 👎
• A logarithm barrier method for linear programming 👍 👎
• A weighted logarithmic barrier interior-point method for linearly constrained optimization 👍 👎
• No self-concordant barrier interior point method is strongly polynomial 👍 👎
• Title not available (Why is that?) 👍 👎

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)