|
GEOMETRIC PROGRAMMING
| Optimization of Posynomials | top |
It is typical to find cost equations for preliminary equipment design to be posynomials, a polynomial whose terms are all positive. The cost equation in example 2-2 of the previous chapter is an exmple of a posynomial. In general form, a posynomial can be written as:
where the ct's are the positive cost coefficients, the xn's are the independent variables, the atn's are the exponents on the independent variables, N is the total number of independent variables, and T is the total number of terms in the cost equation.
The cost equation from the simple process from example 2-2 is given below as an illustration of equation (3-1).
y = 1000x1 + 4 x 109 x1-1 x2-1 + 2.5 x 105 x2 (3-2)
In this case T = 3 and N = 2, with the values of the ct's and
atn's given below:
c1 = 1000 a11 = 1 a21 = -1 a31 = 0
c2 = 4 x 109 a12 = 0 a22 = -1 a32 = 1
c3 = 2.5 x 105
The classical theory of Chapter 2 will be used to develop the geometric programming method of optimizing posynomials. Also, some counterintuitive manipulations will be required to obtain the orthogonality and normality conditions of geometric programming. The result will be another problem to be solved that arises from the original problem. This will be encountered in other methods also, where the original or primal optimizations problem is converted into another related or dual optimizations problem. This dual problem should be easier to solve for the optimum for the procedure to be successful, and there will be a one-to-one correspondence between the optimal solution of the primal and dual problems.
To begin, the first partial derivatives of equation (3-1) with respect to each of the n independent variables, are set equal to zero according to the necessary conditions given in Chapter 2. This gives the following set of equations
which after multiplying by xi can be rewritten as:
This is a set of N nonlinear algebraic equations, and, if solved by the classical theory, there will be all of the problems associated with attempting to optimize equation (2-56) as described at the end of Chapter 2.
Another procedure was suggested (2) where a dual problem is developed using equations (3-1) and (3-4). We will say that equation (3-4) has been solved for the optimal values of the xi's and the minimum cost has been computed using equation (3-1). This is the counterintuitive part of the development where the optimal values of the xi's and y are used in principle, but their numerical values are not known specifically.
First, both sides of equation (3-1) are divided by the optimal value of y to give:
Then the terms in the brackets of equation 3-5 are defined as optimal weights wt, and equation (3-5) becomes
Now the equation set from the necessary conditions, equation (3-4), can be divided by the optimal value of y and written as:
for i = 1, 2, ..., N, and in terms of the optimal weights this equation becomes:
for n = 1,2,...,N, where the subscript n has been used in the place of i for convenience.
At
this point there is a set of N+1 linear algebraic equation which have
been obtained from the original problem. These equations are referred
to as the normality and orthogonality conditions of
geometric programming
It
will be necessary to pursue some additional algebraic manipulations to
obtain an equation that relates the optimal value of y with the optimal
weights wt and the cost coefficients ct. We begin
using equation (3-6) as an exponent on y as:
Equation (3-7) is now used to eliminate y from the right-hand side of equation (3-10), and introduce ct and wt as:
which can be written as:
The double-product term can be simplified using equation (3-9) as:
and equation (3-12) simplifies to the following:
which is the equation needed to relate the optimal value of y with the optimal weights wt and the cost coefficients ct.
The following example will illustrate the use of equation (3-6), (3-7), (3-9), and (3-14) to find the minimum cost of the simple process given in example 2-2. This will give the geometric programming solution for posynomials, and this computational procedure is different than other methods. First, the values of the optimal weights are computed using equations (3-6) and (3-9). Then the minimum cost is evaluated using equation (3-14). Finally the optimal values of the independent variables are calculated using the definition of the optimal weights, equation (3-7).
Example 3-1 (3)
Find the minimum cost of the simple process of example 2-2 by geometric programming. The cost function is:
y = 1000x1 + 4 × 109 x1-1x2-1 + 2.5 × 105 x2
Normality and orthogonality conditions from equations (3-6) and (3-9) are:
w1 + w2 + w3 = 1
w1 - w2 = 0
- w2 + w3 = 0
Solving simultaneously gives
w1 = w2 = w3 = 1/3
Solving for the minimum cost using equation (3-14) gives:
y = [1000/(1/3)]1/3 [4 × 109/(1/3)]1/3 [2.5 × 105/(1/3)]1/3 = 3 × 106
which is the same result as obtained previously. To calculate the optimal values of the independent variables using equation (3-7), there is a choice, i.e., three equations for the wt's and two xi's:
w1 = 1000x1 / 3 ×106 = 1/3 ® x1 = 1000
w2 = 4 ×109 x1-1x2-1 / 3 ×106 = 1/3
w3 = 2.5 ×105 x2 / 3 ×106 = 1/3 ® x2 = 4
The equations that most readily permit the evaluation of the optimal values of the independent variables are selected. In this case they were w1 and w3.
In
example 3-1 it turned out that the number of terms in the cost function,
T, was one more than the number of independent variables N. Consequently,
there were the same number of optimal weights as there were equations
from the normality and orthogonality conditions, and the values of the
optimal weights could be determined uniquely. Then these optimal weights
were used to compute the minimum cost and the optimal values of the independent
variables. However, if the number of terms T is greater than the number
of independent variables plus one, then the method of geometric programming
becomes a constrained optimization as stated below
The above is a statement of the dual problem of geometric programming
obtained from the primal problem which is to minimize equation (3-1).
The significance of this dual problem will be discussed further, but first,
let us examine the following example, which is a modification of example
3-1. It illustrates the effect of having an additional term in the cost
function.
Example 3-2 (3)
Find the minimum cost of the simple process where an additional annual cost of $9000x1x2 for a purifying device must be added. The cost function becomes:
y = 1000x1 + 4 ×109 x1-1x2-1 + 2.5 ×105x2 + 9000x1x2
Normality and orthogonality conditions from equations (3-6) and (3-9) are
w1 + w2 + w3 + w4 = 1
w1 - w2 + w4 = 0
- w2 + w3 + w4 = 0
which must be solved along with dual function of equation (3-14), i.e.:
y = (c1/w1)w1 (c2 /w2)w2 (c3 /w3)w3 (c4 /w4)w4
The methods of Chapter 2 for constrained optimization are required. All of those methods would require differentiating the dual function with respect to the wi's. The direct substitution approach (3) gives:
w1 = (1 - 2w4)/3
w2 = (1 + w4)/3
w3 = (1 - 2w4)/3
And the function to differentiate with respect to w4 to locate the minimum cost is:
y = [3000/(1-2w4)](1-2w4)/3 [12 ×109/(1+w4)](1+w4)/3 [7.5 ×105/(1-2w4)](1-2w4)/3 [9000/w4]w4
At this point it is only reasonable to return to the primal problem which in unconstrained, and solve it for the minimum cost rather than continuing with the dual problem which is significantly more complicated algebraically. (See Reference 3 for the solution.) It is said that this problem has a degree of difficulty of 1, i.e.
T - (N+1) = 4 - (2+1) = 1
and the problem of example 3-1 had a degree of difficulty of zero.
T - (N+1) = 3 - (2+1) = 0
Geometric programming problems can be classified by their degree of difficulty which can be determined prior to attempting to solve the optimization problem by this method. We will summarize the results obtained in terms of the degrees of difficulty as measured by T-(N+1), having seen that if the degree of difficulty is zero only a set of linear algebraic equations need be solved for the minimum cost. However, if the degree of difficulty is greater than zero a constrained optimization problem has to be solved.
The primal problem is:
The dual problem is:
There is a direct correspondence between the primal and dual problems, i.e., the dual problem is constructed from the primal problem. It has been shown (3) that the primal problem, a posynomial, has a global minimum and the dual problem has a global maximum. The numerical value of the minimum of the primal problem is the same as the maximum of the dual problem.
As has been seen if T - (N+1) is zero, the posynomial optimization problem is solved without difficulty; and if T - (N+1) is greater than zero, it may be easier to attempt the solution of the primal problem by a method other than geometric programming. Also, it is necessary to consider the case where T - (N+1) is less than zero, i.e., the number of terms is less than the number of variables plus one. In this situation the algebraic equation set from the normality and orthogonality conditions has more equations than variables, i.e., the equation set is overdetermined. Consequently, the primal problem can not be solved by geometric programming; and the dual problem is said not to be consistent with the primal problem, i.e., the primal problem does not give a dual problem with at least zero degrees of difficulty. However, it has been suggested (3) that a subset of the orthogonality equations could be selected to give several zero degree of difficulty problems to be solved. It was proposed that this would give some information about the optimization problem. This is equivalent to setting some of the independent variables in the primal problem equal to one, and, depending on the problem this might yield some useful information.
Before we move to optimization of polynomials by geometric programming, let us examine the solution of the economic model for the vapor condenser given at the end of Chapter 2. This will demonstrate the facility of the technique when fractional exponents are part of the economic model.
Example 3-3 (7)
The following cost equation was developed for the optimal design of a vapor condenser with a fixed heat load for use in a desalination plant and includes the cost of steam, fixed charges, and pumping costs.
C = aN-7/6D-1L-4/3 + bN-0.2D0.8L-1 + cNDL + dN-1.8D- 4.8L
where C is the cost in dollars per year; N is the number of tubes in the condenser; D is the nominal diameter of the tubes in inches; L is the tube length in feet and a, b, c and d, are coefficients that vary with the fluids involved and the construction costs. For a sea water desalination plan using low pressure steam for heating, these values are a = 3318.8, b = 1.1991, c = 3.4014 x 10-4 and d = 11.624.
The orthogonality and normality conditions are given below.
w1 + w2 + w3 + w4 = 1
-(7/6) w1 - 0.2w2 + w3 - 1.8w4 = 0
-w1 + 0.8w2 + w3 - 4.8w4 = 0
-(4/3) w1 - w2 + w3 + w4 = 0
The degree of difficulty for this problem is zero, and a unique solution for the optimal weights is obtained:
w1 = 2/5 w2 = 1/30 w3 = 8/15 w4 = 1/30
The minimum cost is computed using equation (3-16)
y = [1.724 × 105 × 5/2]2/5 [9.779 × 104 × 30]1/30 [1.57 × 15/8]8/15 [3.82 × 10-2 × 30]1/30 = $526.50/yr.
The optimal values of N, D, and L can be obtained by solving three of
the following equations.
(3318.8) N-7/6 D-1 L- 4/3/526.5 = 2/5
(1.199) N-0.2 D0.8 L-1/526.5 = 1/30
(3.4014 × 10-4) NDL/526.5 = 8/15
(11.624) N-1.8 D- 4.8 L/526.5 = 1/30
The solution of the above equations gives N = 112, D = 1.0 inch, and L = 14.0 ft. An extension to a more detailed design is given by Avriel and Wilde (7).