Todd's low-complexity algorithm is a predictor-corrector path-following method

DOI10.1016/0167-6377(92)90025-XMaRDI QIDQ1197903zbMATH OpenOpenAlexFDO

Authors Michael J. Todd, Jean-Philippe Vial

Publication date 16 January 1993

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(92)90025-x

zbMATH Keywords

interior-point methodpredictor-corrector path-following

Mathematics Subject Classification ID

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

Review text

A variant of Todd's low complexity algorithm, an interior-point method, which requires at most \(O(\sqrt nL)\) iteration steps for solving linear programming problems, is analyzed to be a predictor-corrector path- following method. It is shown that after an initial centering phase each time an affinely scaled Newton-step along an optimal trajectory is performed (predictor step), which is followed then by at most three so- called constant cost entering steps (corrector steps) in order to get back more closely to the trajectory before another affine scaling step is taken. Unfortunately, it is not possible so far to obtain the optimal convergence rate of the method within the proposed setting.

Recommendations

• Some variants of the Todd low-complexity algorithm
• Predictor-corrector Methods for a Class of Linear Complementarity Problems
• A Mehrotra-type predictor-corrector algorithm with \(O(\sqrt{n}L)\)-iteration complexity
• A Mehrotra type predictor-corrector interior-point algorithm for linear programming
• Complexity of Predictor-Corrector Algorithms for LCP Based on a Large Neighborhood of the Central Path

Cites work

• A Low Complexity Interior-Point Algorithm for Linear Programming
• A new polynomial-time algorithm for linear programming
• A Path-Following Projective Interior Point Method for Linear Programming
• A polynomial method of approximate centers for linear programming
• A variation on Karmarkar’s algorithm for solving linear programming problems
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• scientific article; zbMATH DE number 3301975 (Why is no real title available?)
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• Short Steps with Karmarkar’s Projective Algorithm for Linear Programming
• Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming

Cited in

(5)

• Strict monotonicity in Todd's low-complexity algorithm for linear programming
• A path-following version of the Todd-Burrell procedure for linear programming
• Some variants of the Todd low-complexity algorithm
• The implementation of linear programming algorithms based on homotopies
• Superlinear convergence of the affine scaling algorithm

This page was built for publication: Todd's low-complexity algorithm is a predictor-corrector path-following method

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