An analogue of the Klee-Walkup result for sonnevend's curvature of the central path

DOI10.1007/s10957-015-0764-2zbMath1370.90140OpenAlexW2182422590MaRDI QIDQ289062

Murat Mut, Tamás Terlaky

Publication date: 27 May 2016

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10957-015-0764-2

zbMATH Keywords

complexitypolytopescurvaturediameterinterior-point methodslinear optimizationcentral path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Interior-point methods (90C51)

Cites Work

• Representing the space of linear programs as the Grassmann manifold
• 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
• A continuous \(d\)-step conjecture for polytopes
• 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
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• Diameter and Curvature: Intriguing Analogies
• Interior Point Methods for Linear Optimization