Degeneracy in interior point methods for linear programming: A survey
From MaRDI portal
Publication:1312753
DOI10.1007/BF02096259zbMath0785.90067OpenAlexW2045867632MaRDI QIDQ1312753
Osman Güler, Tamás Terlaky, Cornelis Roos, Takashi Tsuchiya, Dick den Hertog
Publication date: 24 February 1994
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02096259
sensitivity analysisglobal and local convergencedegeneracyinterior point methodsnumerical performancebasis recoverypolynomial arithmetics
Related Items
On the identification of the optimal partition for semidefinite optimization, A stable primal-dual approach for linear programming under nondegeneracy assumptions, Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case, A polynomial arc-search interior-point algorithm for linear programming, A new proposal to improve the early iterations in the interior point method, Revisiting degeneracy, strict feasibility, stability, in linear programming, Non total-unimodularity neutralized simplicial complexes, A globally convergent Lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds, Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming, Two simple proofs for analyticity of the central path in linear programming., A weighted least squares study of robustness in interior point linear programming, Hessian Barrier Algorithms for Linearly Constrained Optimization Problems, 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, 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, The maximal descriptor index set for a face of a convex polyhedral set and some applications, Selected bibliography on degeneracy, The Cholesky factorization in interior point methods, Active-set prediction for interior point methods using controlled perturbations
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
- 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
- New purification algorithms for linear programming
- 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
