On the convergence of the affine-scaling algorithm
From MaRDI portal
An algorithm is described for linear programming which have polynomial- time complexity (also in the presence of degeneracy). Especially, it is shown that, for special stepsize choices, the algorithm generates iterates that converge at least linearly with a convergence ratio of \(1- \beta/\sqrt n\), where \(n\) is the number of variables and \(\beta\in(0,1]\) is a certain stepsize ratio. Moreover, using an adapted form of Barnes' stepsize choice it is proved that the sequence of iterates converges to a point satisfying a so-called \(\varepsilon\)-complementary slackness condition.
Recommendations
- Two-thirds is sharp for affine scaling
- scientific article; zbMATH DE number 4195696
- A simplified global convergence proof of the affine scaling algorithm
- Superlinear convergence of the affine scaling algorithm
- Global convergence of the affine scaling methods for degenerate linear programming problems
Cites work
- A method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs
- A modification of Karmarkar's linear programming algorithm
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- A polynomial-time algorithm, based on Newton's method, for linear programming
- A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
- A variation on Karmarkar’s algorithm for solving linear programming problems
- Affine-scaling for linear programs with free variables
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- Bounds for error in the solution set of a perturbed linear program
- Complexity analysis of a linear complementarity algorithm based on a Lyapunov function
- 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
- Data Structures and Programming Techniques for the Implementation of Karmarkar's Algorithm
- Dual coordinate step methods for linear network flow problems
- Ergodic convergence to a zero of the sum of monotone operators in Hilbert space
- Global Convergence Property of the Affine Scaling Methods for Primal Degenerate Linear Programming Problems
- scientific article; zbMATH DE number 4131946 (Why is no real title available?)
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 4202017 (Why is no real title available?)
- scientific article; zbMATH DE number 3961334 (Why is no real title available?)
- scientific article; zbMATH DE number 4112388 (Why is no real title available?)
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- scientific article; zbMATH DE number 3625108 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 3301975 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- Interior path following primal-dual algorithms. II: Convex quadratic programming
- Limiting behavior of the affine scaling continuous trajectories for linear programming problems
- Lipschitz Continuity of Solutions of Linear Inequalities, Programs and Complementarity Problems
- Relaxation Methods for Linear Programs
- Relaxation methods for monotropic programs
Cited in
(37)- Comparative analysis of affine scaling algorithms based on simplifying assumptions
- 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
- A partial first-order affine-scaling method
- Convergence properties of Dikin's affine scaling algorithm for nonconvex quadratic minimization
- Polynomial affine algorithms for linear programming
- Limit analysis with the dual affine scaling algorithm
- 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
- An interior point parameterized central path following algorithm for linearly constrained convex programming
- Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming
- 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
- scientific article; zbMATH DE number 4202017 (Why is no real title available?)
- scientific article; zbMATH DE number 4064763 (Why is no real title available?)
- On uniformization of affine dependence algorithms
- scientific article; zbMATH DE number 953048 (Why is no real title available?)
- A study of the dual affine scaling continuous trajectories for linear programming
- An affine scaling method using a class of differential barrier functions: primal approach
- scientific article; zbMATH DE number 4195696 (Why is no real title available?)
- Analysis of some interior point continuous trajectories for convex programming
- A first-order interior-point method for linearly constrained smooth optimization
- On the Convergence Behavior of Affine Projection Algorithm with Direction Error
- Statistical convergence behavior of affine projection algorithms
- Two-thirds is sharp for affine scaling
- Stochastic interior-point methods for smooth conic optimization with applications
- The _1 solution of linear inequalities
- On the relation between the AINV and the FAPINV algorithms
This page was built for publication: On the convergence of the affine-scaling algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1196183)
