Chapter 3

GEOMETRIC PROGRAMMING

 

Optimization of Polynomials top

    For this case either the cost or profit can be represented by a polynomial. The same procedure employing classical methods (8) will be used to obtain the dual problem, and the techniques will be essentially the same to find the optimum. However, the main difference is that stationary points will be found, and there will be no guarantee that either a maximum or a minimum has been located. It will be necessary to use the methods of Chapter 2 or local exploration to determine their character.

It is convenient to group the positive terms and the negative terms together to represent a general polynomial. This is written as:

Equ3-17a.jpg (6115 bytes)

An example of this equation, given below, will be used to illustrate the solution technique for polynomials.

y = 3x10.25 - 3x11.1 x20.6 - 115x2-1x3-1 - 2x3                                                             (3-18)

and comparing equations (3-17) and (3-18) gives:

c1 = 3              c2 = 3            c3 = 115         c4 = 2

a11= 0.25        a21 = 1.1        c31 = 0            a41 = 0

a12 = 0            a22 = 0.6        a32 = -1          a42 = 0

a13 = 0            a23 = 0           a33 = -1          a43 = 1


     As done previously, the first partial derivatives of equation (3-17) with respect to the n independent variables are set equal to zero according to the necessary conditions. This gives the following set of equations:

Equ3-19.jpg (9989 bytes)

for i = 1, 2, 3, ..., N, which, after multiplying by xi /y can be written as:

Equ3-20.jpg (9420 bytes)

for i = 1, 2, ..., N.

The definition of the optimal weights (equation 3-7) can now be used to give the orthogonality conditions for polynomial optimization, i.e.:

Equ3-21.jpg (4667 bytes)

for n = 1, 2, ..., N, where the subscript n has been used in place of i for convenience.

     Also the normality condition is obtained the same way as equation (3-6) by dividing equation (3-17) by the optimal value of y, which is known in principle from the solution of the set of equations given by equatio (3-20). The result is:

Equ3-22.jpg (3959 bytes)

The only algebraic manipulations that remain are to obtain the equation comparable to equation (3-14) for a polynomial profit or cost function. The procedure is the same and uses equation (3-22) as follows:

Equ3-23.jpg (9045 bytes)

Again the definition of the optimal weights, equation (3-7), is used to eliminate y from the right-hand side of equation (3-23) and introduce ct and wt as:

Equ3-24.jpg (8036 bytes)

and the above can be written as

Equ3-25.jpg (10160 bytes)

The term in the second bracket can be written as

Equ3-26.jpg (6166 bytes)

Using equation (3-21) and performing the manipulations done to obtain equation (3-13), the result is comparable to equation (3-14) and is:

Equ3-27.jpg (5636 bytes)

The primal and dual problems for the method of geometric programming for polynomials can be stated as:

Equ3-17b.jpg (32163 bytes)

     The term optimize is used for both the primal and dual problems. A polynomial can represent a cost to be minimized or a profit to be maximized, since terms of both signs are used. The results obtained from the dual problem could be a maximum, a minimum, or a saddle point since stationary points are computed. Consequently, tests from Chapter 2 or local exploration would be required to determine the character of these stationary points. Before this is discussed further let us examine the geometric programming solution or equation (3-18) to illustrate the procedure.

 

Example 3-4

Obtain the geometric programming solution for equation (3-18).

y = 3x10.25 - 3x11.1x20.6 - 115x2-1x3-1 - 2x3

c1 = 3               c2 = 3            c3 = 115          c4  = 2

a11 = 0.25        a21 = 1.1         a31 = 0             a41 = 0

a12 = 0             a22 = 0.6         a32 = -1           a42 = 0

a13 = 0             a23 = 0            a33 = -1           a43 = 1

The normality and orthogonality conditions are:

       w1   -       w2  -   w3    - w4   =  1

0.25w1 -  1.1 w2                        =   0

   -   0.6w2   +  w3             =  0

    w3  -  w4   =  0

Solving simultaneously gives:

w1 = 2,           w2 = 5/11,           w3 = 3/11,           w4 = 3/11

The optimal of y, in this case, is a maximum.

y = (3/2)2 / [(3 11/5)5/11 (115 11/3)3/11 (2 11/3)3/11]  =  0.1067

and the optimal value of x1, x2, and x3 can be computed from the definitions of the optimal weights by selecting the most convenient form from among the following:

3x10.25/0.1067 = 2

3x11.1x20.6/ 0.1067 = 5/11

115x2-1x3-1/0.1067 = 3/11

2x3 /0.1067 = 3/11

Using the first, third and fourth, gives:

x1 = 2.560 10-5,            x2 = 2.716 105,            x3 = 1.455 10-2

 

     A problem can be encountered from the formulation of a geometric programming problem where the result will be negative values for the optimal weights (3,6). The dual problem required that the optimum values of y be positive. If the economic model is formulated in such a way that the optimal value is negative when calculated from the primal problem, the result will be negative weights computed in the dual problem, and it will not be possible to compute the optimum value of the function using equation (3-27). However, the value of the weights will be correct in numerical value but incorrect in sign. The previous example will be used to illustrate this difficulty, and the proof and further discussion is given by Beightler and Phillips(6).

     In example 3-4 a maximum was found, and the value of the profit function was 0.1067. Had the example been to find the minimum cost, i.e., - y the result would have been -0.1067. However, this value could not have been calculated using equation (3-27). Reformulating the problem of -y with the positive terms first as:

y = 3x11.1x20.6 + 115x2-1x3-1+ 2x3 - 3x10.25


The normality and orthogonality conditions are:

     w1  +   w2  +  w3  -    w4   =  1

1.1w1  +                - 0.25w4   =  0

0.6w1  -  w2                           =   0

  -  w2  +  w3                 =   0

The solution to the equation set is:

w1 = -5/11,            w2 = -3/11,            w3 = -3/11,            w4 = -2

and unacceptable negative values of the optimal weights are obtained. Although not obvious, the cause of this is that the value of the function is negative at the stationary point, i.e., -0.1067. Reformulating the problem to find the stationary point of the negative of the function will give positive optimal weights and a positive value of the function as was illustrated in example 3-4.

     In the illustration, example 3-4, the degree of difficulty, T - (N+1), was zero. As in posynomial optimization, the degree of difficulty must be zero or greater to be able to solve the problem by geometric programming. Also if the degree of difficulty is one or more, then the dual problem is a constrained optimization problem, which has to be solved by the procedures of Chapter 2 or other methods. However, Agognio (18) has proposed a primal-dual, normed space (PDNS) algorithm which used the primal problem and the dual problem together to locate the optimum. This algorithm consists of operations within the primal and dual programs and two sets of mappings between them which depend on a least-squares solution minimizing the two-norm of the overdetermined set of linear equations. The PDNS algorithm was tested on a number of standard problems and performed essentially equally as well as other methods. Also, the dissertation of Agogino (18) describes multiobjective optimization applications of the algorithm.

Closure top

    In this example we have covered the geometric programming optimization of unconstrained posynomials and polynomials. Posynomials represented the cost function of a process, and the procedure located the global minimum by solving the dual problem for the global maximum. Polynomials represented the cost or profit function of a process, and the procedure of solving the dual problem located stationary points which could be maxima, minima, or stationary points. Their character had to be determined by the methods of Chapter 2 or by local exploration. Also, for polynomials if the numerical value of the function being optimized was negative at the stationary point, this caused the optimal weights of the dual problem to be negative. It was then necessary to seek the optimum of the negative of the function to have a positive value at the stationary point. This gave positive optimal weights, and then numerical value of the function at the stationary point was computed using equation (3-27).

     A complete discussion of geometric programming is given by Beightler and Phillips (6), which includes extensions to equality and inequality constraints. These extensions have the same complications as associated with the degrees of difficulty that occur with the unconstrained problems presented here. Because of these limitations the lengthy details for constraints will not be summarized here, and those who are interested in exploring this subject further are referred to the texts by Beightler and Phillips (6), and Reklaitis, et. al. (17).

The dual problem is solved when it is less complicated than the primal problem. An exponential transformation procedure for the dual problem has been described by Reklaitis et. al. (17) to make the computational problem easier when the degree of difficulty is greater than zero and also if constraints are involved. In addition, Reklaitis et. al. (17) reported on comparisons of computer codes for geometric programming optimization based on their research and that of others, including Dembo and Sarma. The testing showed that the best results were obtained with the quotient form of the generalized geometric programming problem, and second was the generalized reduced gradient solution of the exponential form of the primal problem. Also, results by Knopf, Okos, and Reklaitis (9) for batch and semicontinuous process optimization showed that the dual problem can be solved more readily than the primal problem using the generalized reduced gradient multidimensional search technique. Moreover, Phillips (10) has reported other successful applications with non-zero degrees of difficulty requiring multidimensional search methods, which are the topic of Chapter 6. In summary, if the economic model and constraints can be formulated as polynomials, there are many advantages of extensions of geometric programming which can be used for optimization.

References top

1. Zener, C. M. "A Mathematical Aid in Optimizing Engineering Designs" Proceeding of the National Academy of Science, Vol. 47, No. 4, 537-9 (April, 1961).

2. Duffin, R. J., E. L. Peterson and C. M. Zener, Geometric Programming, John Wiley and Sons, Inc., New York (1967).

3. Wilde, D. J. and C. S. Beightler, Foundations of Optimization Prentice-Hall, Inc., Englewood Cliffs, N.J. (1967).

4. Zener, C. M., Engineering Design by Geometric Programming, John Wiley and Sons, Inc., New York (1971).

5. Nijhamp, P., Planning of Industrial Complexes by Means of Geometric Programming, Rotterdam Univ. Press, Rotterdam, Netherlands (1972).

6. Beightler, C. S. and D. T. Phillips, Applied Geometric Programming, John Wiley and Sons, Inc., New York (1976).

7. Avriel, M. and D. J. Wilde, "Optimal Condenser Design by Geometric Programming", Ind. and Engr. Chem., Process Design and Development, Vol.6, No. 2, 256 (April, 1967).

8. Chen, N. H., "A Simplified Approach to Optimization by Geometric Programming" Preprint 12b, 65th National Meeting, American Institute of Chemical Engineers, Cleveland, Ohio (May 4-7,1969).

9. Knopf, C. F., M. R. Okos, and G. V. Reklaitis, "Optimal Design of Batch/Semicontinuous Processes", Ind. Eng. Chem, Process Des. Dev., Vol 21, No.1, 79 (1982).

10. Phillips, D. T. Mathematical Programming for Operations Researchers and Computer Scientists, Ed. A. G. Holtzman, Marcel Dekker, Inc., New York (1981).

11. Stocker, W. F., Design of Thermal Systems, McGraw-Hill Book Co., New York (1971).

12. Sherwood, T. K., A Course in Process Design, MIT Press, Cambridge, Mass. (1963).

13. Beightler, C. S., D. T. Phillips and D. J. Wilde, Foundations of Optimization, 2nd Ed., Prentice-Hall, Inc., Englewood Cliffs, N.J. (1979).

14. Wilde, D. J., Globally Optimal Design, John Wiley and Sons, Inc., New York, (1978).

15. Ray, W. H. and J. Szekely, Process Optimization with Applications in Metallurgy and Chemical Engineering, John Wiley and Sons, Inc., New York (1973).

16. Beveridge, G. S. G. and R. S. Schechter, Optimization: Theory and Practice, McGraw-Hill Book Company, New York (1970).

17. Reklaitis, G. V., A. Ravindran and K. M. Ragsdell, Engineering Optimization: Methods and Applications, John Wiley and Sons, Inc., New York (1983).

18. Agogino, Alice M., A Primal-Dual Algorithm for Constrained Generalized Polynomial Programming: Application to Engineering Design and Multiobjective Optimization, Ph. D. Dissertation, Stanford University, Stanford, California (1984).

Problems top

3-1. Solve the following problem by geometric programming

minimize: y = x12 + 2x22 + 3/x1x2 + 2x1x2

Solution

3-2.(10) Solve the following problem by geometric programming.

minimize: y = 5x1-1x2-3 + 2x12x2x3-2 + 10x1x24x3-1 + 20x32

Solution

3-3.(13) Solve the following problem by geometric programming.

minimize: y = 60x1-3x2-2 + 50x13x2 + 20x1-3x23

Solution

3- 4   a. Solve the following problem by geometric programming.

minimize: y = 4x1 + x1/x22 + 4x2 /x1

b. If an additional term, 2x2, is added to the function being minimized, set up the necessary equations and discuss the procedure to find the optimum.

Solution

3-5. Solve the following problem by geometric programming.

minimize: y = 4x1-1x2-1x3-1 + 8x1x2 + 4x2x3 + 4x1x3

Solution

3-6.(16) Consider the following geometric programming problem.

minimize: y = x12 + x2 + 3/x1x2 + 2x1x2

a Show that the following is the dual problem

Prob3-6.jpg (6892 bytes)

subject to:      w1   +  w2  +  w3  +  w4   = 1

2w1             -  w3   +  w4  =  0

2w2  -  w3   +  w4  =  0

Discuss the method of solution to obtain the optimal value of y and x1 and x2. It is not necessary to carry out the calculations.

b. Two sets of values of the weights that satisfy the constraints w1 = (1/15, 2/15, 7/15, 1/3) and w2 = (1/10, 1/5, 9/20, 1/4). Calculate the optimal value of y for w1 and w2. What is your conclusion?

Solution

3-7.(11) Treatment of a waste is accomplished by chemical treatment and dilution to meet effluent code requirements. The total cost is the sum of the treatment plant, pumping power requirements, and piping cost. This cost is given by the following equation

Prob3-7.jpg (4747 bytes)

where C is in dollars, D in inches, and Q in cfs. Find the minimum cost and best vaues of D and Q by geometric programming.

Solution

3-8. The work done by a three stage compressor is given by the following equation.

W = (P1V1/e) [(P2/P1)e + (P3/P2)e + (P4 /P3)e - 3]

where P1 is the inlet pressure to stage 1, P2 is the discharge pressure from stage 1 and inlet pressure to stage 2, P3 is the discharge pressure from stage 2 and inlet pressure to stage 3, P4 is the discharge pressure from stage 3, and e is equal to (k-1)/k where k is the ratio of specific heats, a constant.

For specified inlet pressure P1 and volume V1 and exit pressure P4, determine intermediate pressures P2 and P3 which minimize the work by geometric programming.

Solution
3-9.(11) Determine the optimal pipe diameter for the minimum installed plus operating costs by geometric programming for 100 ft. of pipe conveying a given flow rate of water.

The installed cost in dollars is 150 D and the lifetime pumping cost in dollars is 122,500/D5. The diameter D is in inches.

Solution

3-10. Sherwood (12) considered the optimum design of a gas transmission line, and obtained the following expression for annual charges (less fixed expenses).

Prob3-10.jpg (8029 bytes)

where L is equal to pipe length between compressors in feet, D is the diameter in inches, F = r 0.219-1, where r is the ratio of inlet to outlet pressure. Determine the minimum cost, and the optimal values of L, F, D and r.

Solution

3-11.(15) The economic model for the annual cost is given below for a furnace in which a slag-metal reaction is to be conducted.

C  =  1 1013 / L3T 2  +  100L2  +  5 10-11L2 T 4

In this equation L is the characteristic length of the furnace in feet and T is the temperature in oK.

a. Determine the minimum cost and the corresponding best value of L and T by geometric programming

b If an additional term, 1000L3 is added to the cost function, give the geometric programming problem to be solved, i.e., dual problem; and indicate how the solution could be obtained.

c. If the cost function only contained the first two terms, deleting the third term, indicate the effect on the solution by geometric programming.

Solution

3-12. The profit function for each of three chemical reactors operating in parallel with the same feed is given by the three equations below. Each reactor is operating with a different catalyst and conditions of temperature and pressure. The profit function for each reactor has the feed rates x1, x2, and x3 as the independent variable, and the parameters in the equation are determined by the catalyst and operating conditions.

P1 = 0.2x1 - 2(x1 /100)2

P2 = 0.2x2 - 4(x2 /100)2

P3 = 0.2x3 - 6(x3 /100)2

a. For the equation for the total profit (P = P1 + P2 + P3) from operating the three reactors, give the geometric programming dual problem with the normality and orthogonality conditions. Compute the optimal weights.

b. Calculate the maximum profit.

c. Calculate the values of the three flow rates of feed to the reactors using the definition of the optimal weights.

Solution

3-13. A batch process has major equipment components which are a reactor, heat exchanger, centrifuge, and dryer. The total cost in dollars per batch of feed processed is given by the following equation, and it is the sum of the costs associated with each piece of equipment.

C  =  315 V0.57t1-1    +   370 V-0.22t1    +     460 VO.54t2-1   +     450 V-0.72t2

           reactor              heat exchanger          centrifuge                     dryer

where V is the volume of feed to be processed per batch in ft3, and t1 and t2 are residence times in hours for the two sections of the process.

a. Find the optimum values of the volume of feed to be processed per batch, V; and the residence times, t1 and t2, by geometric programming.

b. If packaging costs are added as 12OV0.52, set-up this geometric programming problem; and discuss the procedure for finding the minimum cost.

c. Obtain the equations to be solved for the minimum cost by analytical methods, and discuss the feasibility of solving the problem by this method (not with the packaging costs).

Solution

3-14.(6) A total of 400 cubic yards of gravel must be ferried across a river. The gravel is to be shipped in an open box of length x1, width x2, and height x3. The ends and bottom of the box cost $20/sq.yd. to build, the sides, $5/sq.yd. Runners cost $2.50/yd., and two are required to slide the box. Each round trip on the ferry cost $0.10. The problem is to find the optimal dimensions of the box that minimized the total costs of construction and transportation. This total cost is given by:

y  =  40x1-1x2-1x3-1   +  20x1x2  +  10x1x3   +  40x2x3  +  5x1

a. Give the orthorgonality and normality equations to solve this problem by Geometric Programming. Discuss how the problem would be solved and any difficulties that would be encountered. Beightler and Phillips(6) give the following results:

w1 = 0.3858           y* = $108.75           x1* = 1.542 yd.

w2 = 0.1575                                           x2* = 0.561 yd.

w3 = 0.1575                                           x3* = 1.107 yd.

w4 = 0.2284

w5 = 0.0709

b. Neglect the runner's cost, 5x1, and give the orthogonality and normality equation set. Show that the solution to this equation set is:

w1 = 2/5,         w2 = 1/5,         w3 = 1/5,         w4 = 1/5

c. Compute the minimum cost.

d. Compute the values of the independent variables and compare with the results obtained in part a.

Solution

top