Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm

DOI10.1007/BF02592094MaRDI QIDQ1919098zbMATH OpenOpenAlexFDO

Authors Masakazu Muramatsu, Takashi Tsuchiya

Publication date 6 January 1997

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02592094

zbMATH Keywords

convergence analysisinterior point methodlong-step affine scaling algorithmpolynomial time algorithmprojective scaling algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming Problems
• scientific article; zbMATH DE number 4197743
• Convergence and Boundary Behavior of the Projective Scaling Trajectories for Linear Programming
• Superlinear convergence of the affine scaling algorithm

Cites work

• A modification of Karmarkar's linear programming algorithm
• A monotonic projective algorithm for fractional linear programming
• A new polynomial-time algorithm for linear programming
• A simplified global convergence proof of the affine scaling algorithm
• A variant of Karmarkar's linear programming algorithm for problems in standard form
• A variation on Karmarkar’s algorithm for solving linear programming problems
• An extension of Karmarkar's algorithm for linear programming using dual variables
• Conical projection algorithms for linear programming
• Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming Problems
• scientific article; zbMATH DE number 4202017 (Why is no real title available?)
• 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 the improvement per iteration in Karmarkar's algorithm for linear programming
• On the Performance of Karmarkar’s Algorithm over a Sequence of Iterations
• Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The Worst-Case Step in Karmarkar's Algorithm

Cited in

(5)

• Superlinear convergence of the affine scaling algorithm
• Convergence and Boundary Behavior of the Projective Scaling Trajectories for Linear Programming
• Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming Problems
• scientific article; zbMATH DE number 4197743 (Why is no real title available?)
• The _1 solution of linear inequalities

This page was built for publication: Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm

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