Dealing with degeneracy in reduced gradient algorithms

From MaRDI portal





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.




Cited in
(17)








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)