- Introduction
- Analytical Methods without Constraints
- Analytical Methods Applicable for Constraints
- Necessary and Sufficient Conditions for Constrained Problems
- Closure
- References
- Problems
To this point independent variables could take on any value. In actuality, the values of the independent variables are limited since they usually represent physical quantities such a flow rates, temperatures, pressures, process unit capacities and available resources. Consequently, there are constraints on variables, if nothing more than the fact that they must be non-negative. In many cases they are bounded within limits as dictated by the process equipment and related by equations such as material balances. The constraints on the variables can be of the form of equations and inequalities. Methods to locate the stationary points of functions (economic models) subject to equality constraints (e.g., material and energy balance equations) will be developed, and examples illustrating the techniques will be given. Inequality constraints can be converted to equality constraints, and then these procedures for equality constraints can be applied with some additional considerations.
Let us illustrate the conversion of an inequality constraint to an equality
constraint using a simple example to help visualize the concept of slack
variables. Figure 2-3 is an
example of an equality and an inequality constraint for a distillation
column. The material balance which says that the feed rate to the column
must equal the sum of the overhead and bottom products at steady state
is the quality constraint. The upperlimit on the capacity of the distillation
column, which was set when the equiptment was designed, is the inequality
constraint. This inequality constraint can be converted to an equality
constraint by adding a
The
term
We can now state a general optimization problem with n-independent variables
and m equality constraints where the objective is to optimize (maximize
or minimize) the economic model y(
There
must be fewer equality constraints than independent variables to be able
to optimize y(
There are three methods of locating the optimum points of the function
y(x
This simply means to solve the constraint equations for the independent variables and to substitute the constraint equations directly into the function to be optimized. This will give an equation (economic model) with (n-m) unknowns, and the previous techniques for unconstrained optimization are applicable. Unfortunately, it is not always possible to perform the algebraic manipulations required for these substitutions when the constraint equations are somewhat complicated. Consequently, it is necessary to resort to the following methods.
This method (3,14) is used infrequently, but furnishes a theoretical basis for important multivariable numerical search methods, such as the generalized reduced gradient. It is best illustrated for the case of two independent variables by considering the example shown in Figure 2-4. There is a local minimum of the constrained system at point a and a local maximum at point B. The maximum of the unconstrained system is at C.
At point A the curve y(x We will need the total derivatives of y and f to combine with equation (2-16) to obtain the final result. Using the first terms in a Taylor series expansion for y and f gives: At the minimum, point A, and the maximum, point B, dy is equal to zero; and the constraint is satisfied, i.e., f = 0 and df = 0. Combining equations (2-16) and (2-17) gives the following result. This is an algebraic
equation, and it is to be solved in combination with the constraint equation
to locate the stationary points. It should be remembered in this case
that dy/dx This technique is illustrated with the following example. Then the extension to the general case for n independent variables will be given.
Find the stationary points of the following function using the method of constrained variation
The first partial derivatives are: Substituting into equation (2-18) gives
for the values of the independent variables at the stationary points.
In general we are interested in finding the stationary points of a function
y(x
The Jacobian determinant for the first equation above is:
A total of n equations are solved for the stationary points, i.e., the
(n-m) equation generated by (2-20) above and the m constraint equations.
A derivation of these results is given by Beveridge and Schechter(6).
This involves using Cramer's rule and eliminating the dx To illustrate the use of the Jacobian determinants, consider the following example, which obtains equation (2-18).
For this problem there are 2 independent variables (n=2) and one constraint (m=1), so the evaluation of one Jacobian determinant is required. Expanding gives the following equation, gives: This is the same
as equation (2-18) which was solved with the constraint equation for the
stationary point values of x
The most frequently used method for constraints is to employ Lagrange multipliers. The technique will be presented using two independent variables and one constraint equation to illustrate the concepts. Then the procedure will be extended to the general case of n independent variables and m constraint equation. For the case of two independent variables, we have:
We want to show how the Lagrange Multiplier arises and that the constrained problem can be converted into an unconstrained problem. The profit function and the constraint equation are expanded in a Taylor series. Then, using the first order terms gives: This form of
the constraint equation will be used to eliminate dx This equation is substituted into the equation for dy to obtain: and rearranging gives: Now we can define
l as the
value of [-dy
/ dx At the stationary point dy = 0, and this leads to: Now if L is defined as L = y + lf, the above gives: This is one of
the necessary conditions to locate the stationary points of an unconstrained
function L which is constructed from the profit function y(x Therefore, the
constrained problem can be converted to an unconstrained problem by forming
the
Find the stationary points for the following constrained problem using the method of Lagrange multipliers.
Solving the previous equations simultaneously gives the following stationary points:
The type of stationary points, i.e., maxima, minima or saddle points were determined by inspection for this problem. Sufficient conditions for constrained problems will be discussed subsequently in this chapter.
The development of the Lagrangian function of the case of
The Lagrangian, or augmented, function is formed from the constrained problem as follows: To locate the
stationary points of the constrained problem, the first partial derivatives
of the Lagrangian function with respect to the x
It is sometimes said that the method of Lagrange multipliers requires
more work than the method of constrained variation, since an additional
For the process in Example 2-1 (2), it is necessary to maintain the product of the pressure and recycle ratio equal to 9000 psi. Determine the optimal values of the pressure and recycle ration and minimum cost within this constraint by direct substitution, constrained variation and Lagrange multipliers. Again, the problem is to minimize C.
However, C is subject to the following constraint equation.
Setting dC/dR = 0 and solving gives:
The corresponding cost is:
which is greater than the unconstrained system, as would be expected.
The first equation simplifies to:
which, when solved simultaneously with the second equation gives the same results as direct substitution.
Setting partial derivatives of L with respect to P, R, and l equal to zero gives:
Solving the above simultaneously gives the same results as the two previous methods and a value for the Lagrange Multiplier.
A further application of the method of Lagrange Multipliers is developing the method of steepest ascent (descent) for a function to be optimized. This result will be valuable when search methods are discussed.
To illustrate the direction of steepest ascent, a geometric representation
is shown in Figure 2-5. To
obtain the direction of steepest ascent, we wish to obtain the maximum
value of dy, and y(x The problem is: To obtain the maximum value of dy, the Lagrangian function is formed as follows: Differentiating
L with respect to the independent variables dx
and solving for
dx
If a constant k is used to represent the term in the brackets in equation (2-29), this equation can be written as: If a finite difference
approximation is used for dx This
equation can be written vector notation in terms of the gradient of y
evaluated at
Find the minimum
along the direction of steepest descent of the function given below starting
at the point
Gradient line (steepest descent):
or for two independent variables Evaluating the partial derivatives at the starting point (1,1) The gradient line is
Substituting the gradient line into the function to be minimized gives:
Computing dy/dk will locate the minimum along the gradient line, i.e., The corresponding
values of x
It turns out that the minimum along the gradient line is also the minimum for the function in this problem, because it is the sum of squares. The method of steepest ascent is the basis for several search techniques which are described in Chapter 6, e.g., Steep Ascent Partan. It should be noted that when dealing with physical systems, the direction of steepest ascent (descent) may be only a direction of steep ascent (descent) depending on the scales used to represent the independent variables. This is discussed and illustrated by Wilde (5), and Wilde and Beightler (4).
The values of
the Lagrange Multipliers at the optimum provide additional and important
information. If the constraint equations are written with parameters b The following brief derivation obtains the result that ¶y/¶b = - l for the case of one constraint and two independent variables, and the extension to m constraint equations with n independent variables is comparable.
First, we can obtain the following equation from the profit function by the chain rule. Also, we can obtain the next equation from the constraint equation written as f - b = 0 by the chain rule. Then the equation from the constraint is multiplied by the Lagrange Multiplier and added to the equation from the profit function to give: The values of
¶L/¶x In the next section, we will see that the Lagrange Multiplier is also a key factor in the analysis of problems with inequality constraints.
An additional complication arises when seeking the optimum value of a profit or cost function if inequality constraints are included. Although the same procedures are used, it will be necessary to consider two cases for each inequality constraint equation. One case is when the Lagrange Multiplier is zero, and the other is when the Lagrange Multiplier is not zero. This is best illustrated by the following example with one inequality constraint equation as shown below.
As described
previously, the procedure is to add a slack variable x
The result is
two cases, i.e., either l
= 0 and x
For the process the cost function is:
However, C is subject to the inequality constraint equation.
Adding the slack
variable S, as S
Setting the first partial derivatives of L with respect to P, R, S, and l equal to zero gives the following four equations: The two cases are l ¹ 0, S = 0 and l = 0, S ¹ 0. For the case of l ¹ 0, S = 0 the equality PR = 9000 holds, i.e., the constraint is active. This was the solution obtained in Example 2-6, and the results were:
For the case of l = 0, S ¹ 0, the constraint is an inequality, i.e., inactive. This was the solution obtained in Example 2-2 and the results were:
The example above had only one inequality constraint and two cases to consider. However, with several inequality constraints locating the stationary points can become time-consuming, for the possibilities must be searched exhaustively. A procedure for this evaluation has been given by Cooper (7) and Walsh (8) as follows: -
Solve the problem of optimizing: y( **x**), ignoring the inequality constraints, i.e., having all positive slack variables. Designate this solution**x**_{o}. If**x**_{o}satisfies the constraints as inequalities, an optimum has been found. -
If one or more constraints are not satisfied, select one of the constraints to be an equality, i.e., active (the slack variable for this constraint is zero), and solve the problem. Call this solution **x**_{1}. If**x**_{1}satisfies all of the constraints, an optimum has been found. -
If one or more constraints are not satisfied, repeat step 2 until every inequality constraint has been treated as an equality constraint (slack variable being zero) in turn. -
If step 3 did not yield an optimum, select combinations of two inequality constraints at a time to be equalities, and solve the problem. If one of these solutions satisfies all of the constraints, an optimum has been found. -
If step 4 did not yield an optimum, select combinations of three inequality constraints at a time to be equalities, and solve the problem. If one of these solutions satisfies all of the constraints, an optimum has been found. If not try combinations of four inequality constraints at a time to be equalities, etc.
The above procedure applies, assuming that the stationary point located is a maximum or a minimum of the constrained problem. However, there is a possibility that several stationary points will be located; some could be maxima, some minima, and others saddle points. In Problem 2.6, four stationary points were found; two are maxima, one a minimum, and one a saddle point. Also, from equation (2-40) for each inequality constraint where the strict inequality holds, the slack variable is positive, and the Lagrange Multiplier is zero. For each inequality constraint where the equality holds, the slack variable is zero, and the Lagrange Multiplier is not zero. In the next section necessary and sufficient conditions for constrained problems are described to determine the character of stationary points. This will be similar to and an extension of the previous discussion for unconstrained problems. |