A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm

DOI10.1137/S1052623402416803zbMath1080.65049MaRDI QIDQ5317499

Renato D. C. Monteiro, Takashi Tsuchiya

Publication date: 16 September 2005

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

zbMATH Keywords

convergencelinear programminginterior-point algorithmscondition numberpolynomial complexitycentral pathpath-followingpredictor-correctorprimal-dual algorithmsaffine scalingscale-invariancecrossover eventslayered least squares steps

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Interior-point methods (90C51)

Related Items (5)

A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy ⋮ 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 ⋮ A path to the Arrow-Debreu competitive market equilibrium ⋮ Improved complexity results on solving real-number linear feasibility problems ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix

This page was built for publication: A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm