How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds

DOI10.1007/S10107-006-0044-XMaRDI QIDQ2476985zbMATH OpenOpenAlexFDO

Authors Antoine Deza, Eissa Nematollahi, Tamás Terlaky

Publication date 12 March 2008

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-006-0044-x

zbMATH Keywords

linear programminginterior point method

Mathematics Subject Classification ID

Linear programming (90C05) Interior-point methods (90C51) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Recommendations

• Central path curvature and iteration-complexity for redundant Klee-Minty cubes
• The central path visits all the vertices of the Klee–Minty cube
• What is the worst case behavior of the simplex algorithm?
• The iteration-complexity upper bound for the Mizuno-Todd-Ye predictor-corrector algorithm is tight
• A simpler and tighter redundant Klee-Minty construction

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 1017028 (Why is no real title available?)
• scientific article; zbMATH DE number 964349 (Why is no real title available?)
• A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
• A new polynomial-time algorithm for linear programming
• A primal-dual interior point method whose running time depends only on the constraint matrix
• Boundary Behavior of Interior Point Algorithms in Linear Programming
• Pivot rules for linear programming: A survey on recent theoretical developments
• Polytopes and arrangements: diameter and curvature
• The central path visits all the vertices of the Klee–Minty cube

Cited in

(14)

• Smoothed analysis of condition numbers and complexity implications for linear programming
• The iteration-complexity upper bound for the Mizuno-Todd-Ye predictor-corrector algorithm is tight
• A new family of exponential LP problems
• On the volumetric path
• Polytope-based computation of polynomial ranges
• Central path curvature and iteration-complexity for redundant Klee-Minty cubes
• A redundant Klee-Minty construction with all the redundant constraints touching the feasible region
• Interior Point Methods for Nonlinear Optimization
• A linear constrained optimization Benchmark for probabilistic search algorithms: the rotated Klee-Minty problem
• The Chebyshev center as an alternative to the analytic center in the feasibility pump
• Revisiting degeneracy, strict feasibility, stability, in linear programming
• A simpler and tighter redundant Klee-Minty construction
• The central path visits all the vertices of the Klee–Minty cube
• On semidefinite least squares and minimal unsatisfiability

This page was built for publication: How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds

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