On the curvature of the central path of linear programming theory

DOI10.1007/S10208-003-0116-8MaRDI QIDQ2505641zbMATH OpenOpenAlexFDO

Authors Jean-Pierre Dedieu, Gregorio Malajovich, Michael Shub

Publication date 28 September 2006

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational aspects of algebraic curves (14Q05) Numerical computation of solutions to systems of equations (65H10) Analysis of algorithms and problem complexity (68Q25) Interior-point methods (90C51) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We prove a linear bound on the average total curvature of the central path of linear programming theory in terms on the number of independent variables of the primal problem, and independent on the number of constraints.

Recommendations

• The central curve in linear programming
• On the Relationship Between the Curvature Integral and the Complexity of Path-Following Methods in Linear Programming
• 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
• On the complexity of following the central path of linear programs by linear extrapolation. II
• scientific article; zbMATH DE number 409894

Cited in

(15)

• A continuous d-step conjecture for polytopes
• An analogue of the Klee-Walkup result for sonnevend's curvature of the central path
• A note on the structure of the central path in linear programming
• Central path curvature and iteration-complexity for redundant Klee-Minty cubes
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• The degree of the central curve in semidefinite, linear, and quadratic programming
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• Diameter and Curvature: Intriguing Analogies
• On the central path of semidefinite optimization: degree and worst-case convergence rate
• Two simple proofs for analyticity of the central path in linear programming.
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• On the complexity of analyticity in semi-definite optimization
• The central curve in linear programming
• Polytopes and arrangements: diameter and curvature

This page was built for publication: On the curvature of the central path of linear programming theory

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