Dealing with degeneracy in reduced gradient algorithms
Many algorithms for linearly constrained optimization problems proceed by solving a sequence of subproblems. In these subproblems, the number of variables is implicitly reduced by using the linear constraints to express certain 'basic' variables in terms of other variables. Difficulties may arise, however, if degeneracy is present; that is, if one or more basic variables are at lower or upper bounds. In this situation, arbitrarily small movements along a feasible search direction in the reduced problem may result in infeasibilities for basic variables in the original problem. For such cases, the search direction is typically discarded, a new reduced problem is formed and a new search direction is computed. Such a process may be extremely costly, particularly in large-scale optimization where degeneracy is likely and good search directions can be expensive to compute. This paper is concerned with a practical method for ensuring that directions that are computed in the reduced space are actually feasible in the original problem. It is based on a generalization of the 'maximal basis' result first introduced by the authors [Math. Program. Study 15, 125-147 (1981; Zbl 0477.90025)] for large nonlinear network optimization problems.
- scientific article; zbMATH DE number 123740
- A general technique for dealing with degeneracy in reduced gradient methods for linearly constrained nonlinear programming
- scientific article; zbMATH DE number 3948008
- scientific article; zbMATH DE number 4001345
- scientific article; zbMATH DE number 4202038
- scientific article; zbMATH DE number 3930257
- Applying a reduced gradient in quadratic programming
- A reduced subgradient algorithm
- Shrinking generalized gradients
- A Deflated Version of the Conjugate Gradient Algorithm
- A Newton method for convex separable network flow problems
- A scaled reduced gradient algorithm for network flow problems with convex separable costs
- Conjugate gradient methods for linearly constrained nonlinear programming
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 3402374 (Why is no real title available?)
- Large-scale linearly constrained optimization
- New Finite Pivoting Rules for the Simplex Method
- The Constrained Gradient Method of Linear Programming
- A degenerate extreme point strategy for the classification of linear constraints as redundant or necessary
- On degeneracy in linear programming and related problems
- A general technique for dealing with degeneracy in reduced gradient methods for linearly constrained nonlinear programming
- A smooth penalty function algorithm for network-structured problems
- Implementation of reduced gradient with bisection algorithms for non-convex optimization problem via stochastic perturbation
- A unified approach to the feasible point method type for nonlinear programming with linear constraints under degeneracy and the convergence properties
- Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization
- scientific article; zbMATH DE number 5899260 (Why is no real title available?)
- A Review of Sensitivity Results for Linear Networks and a New Approximation to Reduce the Effects of Degeneracy
- Reduced gradient computation in prediction error identification
- scientific article; zbMATH DE number 13594 (Why is no real title available?)
- scientific article; zbMATH DE number 123740 (Why is no real title available?)
- Approximating reduced costs under degeneracy in a network flow problem with side constraints
- New crash procedures for large systems of linear constraints
- Hybrid-LP: finding advanced starting points for simplex, and pivoting LP methods
- A polynomial algorithm for minimum quadratic cost flow problems
- The complex interior-boundary method for linear and nonlinear programming with linear constraints
This page was built for publication: Dealing with degeneracy in reduced gradient algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3691433)