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 (19)

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

This page was built for publication: A simplified global convergence proof of the affine scaling algorithm