Resolving Degeneracy in the Generalized Reduced Gradient Method

Abstract

The Generalized Reduced Gradient (GRG) method has proven to be one of the more robust and efficient algorithms currently available for solving nonlinear programming problems. The method divides the vector of design variables into two classes, nonbasic and basic variables, and employs the implicit function theorem to formulate a reduced, unconstrained problem in the nonbasic variables. In order to employ the implicit function theorem two assumptions are made: (1) The Jacobian matrix of the active constraints with respect to the basic variables is nonsingular; and (2) All basic variables are within their respective bounds. When the second condition is not satisfied then the current point is degenerate and further progress is not assured. Methods based on performing basis changes exist for resolving degeneracy. In this paper, we will describe a technique based on the method of feasible directions which has the advantage of requiring no basis changes to generate a new direction.