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

DOI10.1137/S1052623402416803zbMATH Open1080.65049MaRDI QIDQ5317499FDOQ5317499

Authors: Renato D. C. Monteiro, Takashi Tsuchiya 

Publication date: 16 September 2005

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

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

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)

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 scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
• A path to the Arrow-Debreu competitive market equilibrium
• 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)