Central path curvature and iteration-complexity for redundant Klee-Minty cubes

DOI10.1007/978-0-387-75714-8_7MaRDI QIDQ3565464zbMATH OpenOpenAlexFDO

Authors 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

central pathinterior-point methodslinear programmingtotal curvature

Mathematics Subject Classification ID

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

Recommendations

• The central path visits all the vertices of the Klee–Minty cube
• A simpler and tighter redundant Klee-Minty construction
• How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
• scientific article; zbMATH DE number 1559540
• A redundant Klee-Minty construction with all the redundant constraints touching the feasible region

Cites work

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

Cited in

(15)

• A redundant Klee-Minty construction with all the redundant constraints touching the feasible region
• A continuous d-step conjecture for polytopes
• A tropical isoperimetric inequality
• How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
• An analogue of the Klee-Walkup result for sonnevend's curvature of the central path
• The central path visits all the vertices of the Klee–Minty cube
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• Formalizing the Face Lattice of Polyhedra
• Formalizing the face lattice of polyhedra
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Interior point methods in the year 2025
• Polytopes and arrangements: diameter and curvature
• A simpler and tighter redundant Klee-Minty construction

This page was built for publication: Central path curvature and iteration-complexity for redundant Klee-Minty cubes

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