Limiting behavior of the affine scaling continuous trajectories for linear programming problems
From MaRDI portal
Publication:2640436
The authors discuss the limiting behaviour of the continuous trajectories of the primal affine scaling (PAS) algorithm given by \textit{E. R. Barnes} [Math. Program. 36, 174-182 (1986; Zbl 0626.90052)] and others, the dual affine scaling (DAS) algorithm given by the first author, \textit{M. Resende, G. Veiga} and \textit{N. Karmarkar} [ibid., Ser. A 44, No.3, 297- 335 (1989; Zbl 0682.90061)] and the primal-dual affine scaling (PDAS) algorithm introduced by the authors and \textit{M. Resende} [Math. Oper. Res. 15, No.2, 191-214 (1990; Zbl 0714.90060)]. In this paper they present a weighted PAS algorithm and characterize its trajectories as solutions to a logarithmic barrier family of problems. The authors present several results on PAS, DAS and PDAS trajectories and claim to extend the results already obtained by \textit{N. Megiddo} and \textit{M. Shub} [ibid. 14, No.1, 97-146 (1989; Zbl 0675.90061)] and others about the limiting behaviour of PAS and PDAS trajectories. It is mentioned that their approach does not require the non-degeneracy assumption.
Recommendations
- scientific article; zbMATH DE number 4197742
- A study of the dual affine scaling continuous trajectories for linear programming
- scientific article; zbMATH DE number 4195697
- scientific article; zbMATH DE number 4197743
- Convergence and Boundary Behavior of the Projective Scaling Trajectories for Linear Programming
Cites work
- A modification of Karmarkar's linear programming algorithm
- A new polynomial-time algorithm 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
- An implementation of Karmarkar's algorithm for linear programming
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- Computational experience with a dual affine variant of Karmarkar's method for linear programming
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- scientific article; zbMATH DE number 3301975 (Why is no real title available?)
- scientific article; zbMATH DE number 3307153 (Why is no real title available?)
- The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
Cited in
(51)- Global convergence of the affine scaling methods for degenerate linear programming problems
- Improving the rate of convergence of interior point methods for linear programming
- On the convergence of the affine-scaling algorithm
- Todd's low-complexity algorithm is a predictor-corrector path-following method
- Condition measures and properties of the central trajectory of a linear program
- Degeneracy in interior point methods for linear programming: A survey
- A simplified global convergence proof of the affine scaling algorithm
- Limiting behavior of weighted central paths in linear programming
- The discrete Radon transform and its approximate inversion via linear programming
- Trust region affine scaling algorithms for linearly constrained convex and concave programs
- The asymptotic optimal partition and extensions of the nonsubstitution theorem
- Examples of ill-behaved central paths in convex optimization
- On the -exponential trajectory of linear programming
- An implementation of Karmarkar's algorithm for linear programming
- Analyticity of the central path at the boundary point in semidefinite programming
- Differential-algebraic approach to linear programming
- Some properties of generalized proximal point methods for quadratic and linear programming
- Limit analysis with the dual affine scaling algorithm
- An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption
- The primal power affine scaling method
- Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm
- Uniform bounds on the limiting and marginal derivatives of the analytic center solution over a set of normalized weights
- An interior point parameterized central path following algorithm for linearly constrained convex programming
- Generalized affine scaling algorithms for linear programming problems
- Superlinear convergence of the affine scaling algorithm
- Shape-preserving approximation of multiscale univariate data by cubic \(L_1\) spline fits
- Asymptotic behavior of the central path for a special class of degenerate SDP problems
- Shape-preserving, first-derivative-based parametric and nonparametric cubic \(L_{1}\) spline curves
- Loss and retention of accuracy in affine scaling methods
- The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
- A new variant of the primal affine scaling algorithm for linear programs
- Convergence and Boundary Behavior of the Projective Scaling Trajectories for Linear Programming
- The convergent generalized central paths for linearly constrained convex programming
- A study of the dual affine scaling continuous trajectories for linear programming
- Primal-dual path-following methods and the trust-region updating strategy for linear programming with noisy data
- scientific article; zbMATH DE number 7305744 (Why is no real title available?)
- scientific article; zbMATH DE number 4195697 (Why is no real title available?)
- scientific article; zbMATH DE number 4197742 (Why is no real title available?)
- Analysis of some interior point continuous trajectories for convex programming
- scientific article; zbMATH DE number 6027003 (Why is no real title available?)
- Limiting behavior of the Alizadeh–Haeberly–Overton weighted paths in semidefinite programming
- Dual convergence of the proximal point method with Bregman distances for linear programming
- Two simple proofs for analyticity of the central path in linear programming.
- Shape-preserving, multiscale interpolation by bi- and multivariate cubic \(L_{1}\) splines
- Profit sharing mechanisms in multi-owned cascaded hydrosystems
- Doubly autoparallel structure and curvature integrals. Applications to iteration complexity for solving convex programs
- Hessian barrier algorithms for non-convex conic optimization
- On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm
- The affine-scaling direction for linear programming is a limit of projective-scaling directions
- The _1 solution of linear inequalities
- Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem
This page was built for publication: Limiting behavior of the affine scaling continuous trajectories for linear programming problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2640436)
