Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes

DOI10.1007/978-0-387-75714-8_7zbMath1189.90098OpenAlexW30154001MaRDI QIDQ3565464

Antoine Deza, Tamás Terlaky, Yuriy Zinchenko

Publication date: 4 June 2010

Published in: Advances in Mechanics and Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-0-387-75714-8_7

zbMATH Keywords

linear programminginterior-point methodscentral pathtotal curvature

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05)

Related Items

Formalizing the Face Lattice of Polyhedra, Log-Barrier Interior Point Methods Are Not Strongly Polynomial, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Polytopes and arrangements: diameter and curvature, A simpler and tighter redundant Klee-Minty construction, What Tropical Geometry Tells Us about the Complexity of Linear Programming, A tropical isoperimetric inequality, Unnamed Item, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, A continuous \(d\)-step conjecture for polytopes

Cites Work

• A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
• Polytopes and arrangements: diameter and curvature
• 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
• Computational techniques of the simplex method
• On the Riemannian geometry defined by self-concordant barriers and interior-point methods.
• A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
• How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
• On the curvature of the central path of linear programming theory
• The central path visits all the vertices of the Klee–Minty cube
• Boundary Behavior of Interior Point Algorithms in Linear Programming
• Presolve Analysis of Linear Programs Prior to Applying an Interior Point Method
• NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING
• Interior Point Methods for Linear Optimization