Log-Barrier Interior Point Methods Are Not Strongly Polynomial

DOI10.1137/17M1142132zbMath1391.90637arXiv1708.01544OpenAlexW2745127509WikidataQ117245035 ScholiaQ117245035MaRDI QIDQ4564017

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)

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

zbMATH Keywords

linear programmingcentral pathtropical geometrycontinuous analogue of Hirsch conjecture

Mathematics Subject Classification ID

Interior-point methods (90C51)

Related Items

Formalizing the Face Lattice of Polyhedra, Computing zero-dimensional tropical varieties via projections, Tropical Gaussians: a brief survey, Universal Analytic Gröbner Bases and Tropical Geometry, Abstract tropical linear programming, Tropical Carathéodory with matroids, Tropical medians by transportation, Tropical combinatorial Nullstellensatz and sparse polynomials, Toric geometry of entropic regularization, Massively parallel computation of tropical varieties, their positive part, and tropical Grassmannians, Convergent Hahn series and tropical geometry of higher rank, 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 Ehrhart theory and tropical volume, Exact algorithms for semidefinite programs with degenerate feasible set, What Tropical Geometry Tells Us about the Complexity of Linear Programming, Tropical spectrahedra, The tropical analogue of the Helton-Nie conjecture is true, Approximating the volume of tropical polytopes is difficult, Detecting tropical defects of polynomial equations, Unnamed Item, Computing complex and real tropical curves using monodromy, Tropical bisectors and Voronoi diagrams, On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate, Parametric Shortest-Path Algorithms via Tropical Geometry, A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

Uses Software

• polymake

Cites Work

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