Degeneracy in interior point methods for linear programming: A survey
From MaRDI portal
Publication:1312753
DOI10.1007/BF02096259zbMath0785.90067MaRDI QIDQ1312753
Cornelis Roos, Tamás Terlaky, Dick den Hertog, Takashi Tsuchiya, Osman Güler
Publication date: 24 February 1994
Published in: Annals of Operations Research (Search for Journal in Brave)
sensitivity analysis; global and local convergence; degeneracy; interior point methods; numerical performance; basis recovery; polynomial arithmetics
Related Items
A globally convergent Lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds, Two simple proofs for analyticity of the central path in linear programming., The Cholesky factorization in interior point methods, A weighted least squares study of robustness in interior point linear programming, Determination of an interior feasible point for a system of linear constraints, Balinski-Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces, Selected bibliography on degeneracy, Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case, The Gaussian hare and the Laplacian tortoise: computability of squared-error versus absolute-error estimators. With comments by Ronald A. Thisted and M. R. Osborne and a rejoinder by the authors
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- On the finite convergence of interior-point algorithms for linear programming
- Approaches to sensitivity analysis in linear programming
- A new polynomial-time algorithm for linear programming
- A potential-reduction variant of Renegar's short-step path-following method for linear programming
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- Asymptotic behaviour of Karmarkar's method for linear programming
- Shadow prices and sensitivity analysis in linear programming under degeneracy. State-of-the-art-survey
- An extension of Karmarkar's algorithm for linear programming using dual variables
- Karmarkar's algorithm and the ellipsoid method
- A multiplicative barrier function method for linear programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Linear programming and the Newton barrier flow
- On the convexity of the multiplicative version of Karmarkar's potential function
- Determining basic variables of optimal solutions in Karmarkar's new LP algorithm
- Interior path following primal-dual algorithms. I: Linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- On finding a vertex solution using interior point methods
- An optimal-basis identification technique for interior-point linear programming algorithms
- An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
- A unified approach to interior point algorithms for linear complementarity problems: A summary
- Global convergence of the affine scaling methods for degenerate linear programming problems
- A survey of search directions in interior point methods for linear programming
- A geometric view of parametric linear programming
- On the convergence of the affine-scaling algorithm
- A polynomial method of approximate centers for linear programming
- An analogue of Moreau's proximation theorem, with application to the nonlinear complementarity problem
- A proof of the polynomiality of the Iri-Imai method
- Pivot rules for linear programming: A survey on recent theoretical developments
- Finding an interior point in the optimal face of linear programs
- Recovering an optimal LP basis from an interior point solution
- Containing and shrinking ellipsoids in the path-following algorithm
- Polynomial affine algorithms for linear programming
- An implementation of Karmarkar's algorithm for linear programming
- Theoretical convergence of large-step primal-dual interior point algorithms for linear programming
- Search directions for interior linear-programming methods
- Limiting behavior of the affine scaling continuous trajectories for linear programming problems
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- A variation on Karmarkar’s algorithm for solving linear programming problems
- Quadratic Convergence in a Primal-Dual Method
- Local Convergence Properties of New Methods in Linear Programming
- A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
- A Centered Projective Algorithm for Linear Programming
- Recovering Optimal Basic Variables in Karmarkar's Polynomial Algorithm for Linear Programming
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
- The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- Convergence and Boundary Behavior of the Projective Scaling Trajectories for Linear Programming
- Large Step Path-Following Methods for Linear Programming, Part I: Barrier Function Method
- Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method
- Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods
- On the Continuous Trajectories for a Potential Reduction Algorithm for Linear Programming
- Path-Following Methods for Linear Programming
- A Complexity Reduction for the Long-Step Path-Following Algorithm for Linear Programming
- On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
- On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
- Implementation of a Dual Affine Interior Point Algorithm for Linear Programming
- Global Convergence Property of the Affine Scaling Methods for Primal Degenerate Linear Programming Problems
- On Finding Primal- and Dual-Optimal Bases
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- A Study of Indicators for Identifying Zero Variables in Interior-Point Methods
- Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming Problems
- Duality Theory of Linear Programs: A Constructive Approach with Applications
- Limiting Behavior of Trajectories Generated by a Continuation Method for Monotone Complementarity Problems
