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

DOI10.1007/BF02592094zbMath0853.90084OpenAlexW2037593698MaRDI QIDQ1919098

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 analysispolynomial time algorithminterior point methodprojective scaling algorithmlong-step affine scaling algorithm

Mathematics Subject Classification ID

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

Related Items

Superlinear convergence of the affine scaling algorithm, The \(\ell_1\) solution of linear inequalities

Cites Work

• Unnamed Item
• Unnamed Item
• A monotonic projective algorithm for fractional linear programming
• A modification of Karmarkar's linear programming algorithm
• A new polynomial-time algorithm for linear programming
• On the improvement per iteration in Karmarkar's algorithm for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• Conical projection algorithms for linear programming
• A simplified global convergence proof of the affine scaling algorithm
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• A variation on Karmarkar’s algorithm for solving linear programming problems
• A variant of Karmarkar's linear programming algorithm for problems in standard form
• Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The Worst-Case Step in Karmarkar's Algorithm
• On the Performance of Karmarkar’s Algorithm over a Sequence of Iterations
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming Problems