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

DOI10.1137/S1052623402416803MaRDI QIDQ5317499zbMATH OpenFDO

Authors Renato D. C. Monteiro, Takashi Tsuchiya

Publication date 16 September 2005

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

zbMATH Keywords

linear programmingconvergencecondition numberpolynomial complexitycentral pathpath-followingpredictor-correctorprimal-dual algorithmsaffine scalingscale-invarianceinterior-point algorithmscrossover eventslayered least squares steps

Mathematics Subject Classification ID

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

Recommendations

• Quadratic Convergence in a Primal-Dual Method
• A new predictor-corrector algorithm for SDP with polynomial convergence
• A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
• The iteration-complexity upper bound for the Mizuno-Todd-Ye predictor-corrector algorithm is tight
• On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms
• Complexity of Mehrotra's predictor-corrector algorithms for monotone linear complementarity problems
• 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 linear programming instance with many crossover events
• A new Mehrotra-type predictor-corrector algorithm for linear programming
• An improved predictor-corrector interior-point algorithm for linear complementarity problems with \(O(\sqrt{n}L)\)-iteration complexity

Cited in

(7)

• The iteration-complexity upper bound for the Mizuno-Todd-Ye predictor-corrector algorithm is tight
• 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
• Avoiding anomalies in the \(MT2\) algorithm by Martello and Toth
• A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy
• A path to the Arrow-Debreu competitive market equilibrium
• A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• Improved complexity results on solving real-number linear feasibility problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317499)