A Polynomial Primal-Dual Dikin-Type Algorithm for Linear Programming

DOI10.1287/moor.21.2.341zbMath0857.90082OpenAlexW2120351295MaRDI QIDQ4895562

Benjamin Jansen, Cornelis Roos, Tamás Terlaky

Publication date: 11 March 1997

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/8fbc82cd82e8cfe7adf519b76a7a4ca7176a9492

zbMATH Keywords

duality gapbarrier functionpolynomial-time convergence proofprimal-dual scaling

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items

Improved complexity using higher-order correctors for primal-dual Dikin affine scaling, Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems, Primal-dual target-following algorithms for linear programming, An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming, An affine scaling method using a class of differential barrier functions: primal approach, On the chaotic behavior of the primal–dual affine–scaling algorithm for linear optimization, Linear optimization over homogeneous matrix cones, A constraint-reduced variant of Mehrotra's predictor-corrector algorithm, A Primal-dual affine scaling algorithm with necessary centering as a safeguard, A polynomial primal-dual affine scaling algorithm for symmetric conic optimization, Primal-dual potential reduction methods for semidefinite programming using affine-scaling directions, Generalized affine scaling algorithms for linear programming problems