A simplified global convergence proof of the affine scaling algorithm

DOI10.1007/BF02023109zbMath0804.90091OpenAlexW1986984076MaRDI QIDQ1312779

Renato D. C. Monteiro, Takashi Tsuchiya, Yan-Hui Wang

Publication date: 7 February 1994

Published in: Annals of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

affine scaling algorithmglobal convergence proofdegenerate linear programming

Mathematics Subject Classification ID

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

Related Items

Superlinear convergence of the affine scaling algorithm, Unnamed Item, Interior Point Algorithms in Linear Optimization, Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming, A simple proof of a primal affine scaling method, An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption, A convergence analysis for a convex version of Dikin's algorithm, The primal power affine scaling method, Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm, An affine scaling method using a class of differential barrier functions: primal approach, Trust region affine scaling algorithms for linearly constrained convex and concave programs, The \(\ell_1\) solution of linear inequalities, A first-order interior-point method for linearly constrained smooth optimization, Convergence properties of Dikin's affine scaling algorithm for nonconvex quadratic minimization, A weighted least squares study of robustness in interior point linear programming, Interior point method: history and prospects, Affine scaling algorithm fails for semidefinite programming, Generalized affine scaling algorithms for linear programming problems, An interior point parameterized central path following algorithm for linearly constrained convex programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A modification of Karmarkar's linear programming algorithm
• Two-thirds is sharp for affine scaling
• A new polynomial-time algorithm for linear programming
• Computational experience with a dual affine variant of Karmarkar's method for linear programming
• Global convergence of the affine scaling methods for degenerate linear programming problems
• On the convergence of the affine-scaling algorithm
• An implementation of Karmarkar's algorithm for linear programming
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• A variation on Karmarkar’s algorithm for solving linear programming problems
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• Boundary Behavior of Interior Point Algorithms in Linear Programming
• Global Convergence Property of the Affine Scaling Methods for Primal Degenerate Linear Programming Problems