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 (12)

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

This page was built for publication: An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming