On the convergence of the affine-scaling algorithm

DOI10.1007/BF01580904zbMath0762.90052MaRDI QIDQ1196183

Zhi-Quan Luo, Paul Tseng

Publication date: 17 December 1992

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

zbMATH Keywords

polynomial-time complexity; \(\varepsilon\)-complementary slackness condition

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C60: Abstract computational complexity for mathematical programming problems

90C05: Linear programming

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Related Items

The \(\ell_1\) solution of linear inequalities, Determination of an interior feasible point for a system of linear constraints, Degeneracy in interior point methods for linear programming: A survey, A simplified global convergence proof of the affine scaling algorithm, Global convergence of the affine scaling algorithm for primal degenerate strictly convex quadratic programming problems, Error bounds in mathematical programming, Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case, Trust region affine scaling algorithms for linearly constrained convex and concave programs, Convergence properties of Dikin's affine scaling algorithm for nonconvex quadratic minimization, 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, Superlinear convergence of the affine scaling algorithm, Affine scaling with degenerate linear programming problems, Loss and retention of accuracy in affine scaling methods, Interior-point methods for linear programming: a review

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A modification of Karmarkar's linear programming algorithm
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• Relaxation methods for monotropic programs
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• Computational experience with a dual affine variant of Karmarkar's method for linear programming
• Convergence results and numerical experiments on a linear programming hybrid algorithm
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Dual coordinate step methods for linear network flow problems
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• A polynomial-time algorithm for a class of linear complementarity problems
• Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
• Complexity analysis of a linear complementarity algorithm based on a Lyapunov function
• Affine-scaling for linear programs with free variables
• Bounds for error in the solution set of a perturbed linear program
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• A variation on Karmarkar’s algorithm for solving linear programming problems
• A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
• Relaxation Methods for Linear Programs
• Boundary Behavior of Interior Point Algorithms in Linear Programming
• A method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs
• Data Structures and Programming Techniques for the Implementation of Karmarkar's Algorithm
• Global Convergence Property of the Affine Scaling Methods for Primal Degenerate Linear Programming Problems
• Lipschitz Continuity of Solutions of Linear Inequalities, Programs and Complementarity Problems