such methods can be considerable for problems with many variables and con-
straints, as is the case here. Additionally, if an "optimum" is found by such a method,
there is no guarantee that it is a global optimum.
Methods have also been developed for general nonlinear problems. Perhaps the
method most commonly referred to is Lagrange's method of undetermined multi-
pliers (Wilde and Beightler 1967). This method requires that the solution to a set of
nonlinear equations be found. The number of unknowns is equal to the number of
variables (pipe diameters and consumer control valve pressure losses) plus the
number of constraints. In our case this would result in very large systems of
nonlinear equations for all but the most trivial problems. The solution of large
systems of nonlinear equations can be a very difficult task, usually done by adapting
methods for the solution of linear equations. For this reason, Lagrange's method is
felt to be impractical for this problem.
The Generalized Reduced Gradient (GRG) method is a popular one used for
nonlinear constrained problems (Reklaitis et al. 1983). It is based on extending
methods used for linear problems to nonlinear problems. The basic concept of the
GRG method is to follow along the direction of a constraint subset while seeking
improvement in the objective function. By requiring some subset of the constraints
to be satisfied, the number of degrees of freedom of the problem can be effectively
reduced. When inequality constraints are present in the problem, as is the case here,
either an active set strategy must be adopted or slack variables must be introduced
for each constraint. Gill et al. (1981) indicate that GRG methods can encounter
difficulties when highly nonlinear constraints are involved, as is the case here.
Because methods developed for linear problems are being used for nonlinear
problems, it is necessary to iterate at each step to achieve a feasible design. The
Newton-Rapson method is used for this iteration and it becomes the main compu-
tation burden of the GRG method (Arora 1989). Other quasi-Newton methods have
been proposed, but they can cause other problems with this method (Arora 1989).
Vanderplaats (1984) indicates that convergence of the Newton-Rapson method may
be a problem when using the GRG method for highly nonlinear problems.
Another class of methods for general nonlinear constrained problems is the
penalty function methods (Rao 1984). These methods reduce the constrained
problem to an unconstrained problem that can then be solved using any of the
various methods suitable for such problems. With many variables, as we have here,
the multidimensional optimization problem that results can be quite time consum-
ing to solve. In addition, it's usually necessary to solve the problem repeatedly for
different values of the penalty parameter until some convergence criterion has been
met. A feasible starting point is required as is an initial value for the penalty
parameter and the multiplication factor that is used to adjust the penalty parameter.
In this problem the diameters of the pipe segments must take on discrete values
in the final solution, while other variables such as the consumer control valve
pressure losses are continuous. Such a problem, which has both discrete and
continuous variables, can be formulated as what's called a "mixed integer" problem
(Reklaitis et al. 1983). The methods described above can not be applied directly to
integer or mixed integer problems. They must be used in combination with another
technique, most notably the "branch-and-bound" approach, to find the solution for
the discrete variables. The branch-and-bound approach will be discussed later.
In search of a simpler and more efficient method than those described above, we
will proceed by starting with our optimal independent (unconstrained) design and
identifying methods to move from this design to one that satisfies all the constraints.
We will attempt to conduct this process of modifying the solution so that it satisfies
the constraints in a manner that will keep us as close as possible to the true globally
optimal design.
41
Previous Page
