An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming

DOI10.1137/0802017zbMath0783.90071OpenAlexW2104431380MaRDI QIDQ4018832

Michael J. Todd, Clóvis C. Gonzaga

Publication date: 16 January 1993

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0802017

zbMATH Keywords

interior-point methodspath-following methodsprimal-dual interior- point algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

A primal-dual potential reduction method for problems involving matrix inequalities, Smoothed analysis of condition numbers and complexity implications for linear programming, Comparative analysis of affine scaling algorithms based on simplifying assumptions, On lower bound updates in primal potential reduction methods for linear programming, A note on a potential reduction algorithm for LP with simultaneous primal-dual updating, Dual versus primal-dual interior-point methods for linear and conic programming, Convergence behavior of interior-point algorithms, On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise, An algorithm to analyze stability of gene-expression patterns, Near boundary behavior of primal-dual potential reduction algorithms for linear programming, On the convergence of primal-dual interior-point methods with wide neighborhoods, On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP