|
MULTI VARIABLE OPTIMIZATION PROCEDURES
- Introduction
- Mutivariable Search Methods Overview
- Unconstrained Multivariable Search Methods
- Constrained Multivariable Search Methods
- Successive Linear Programming
- Successive Quadratic Programming
- Generalized Reduced Gradient Method
- Penalty, Barrier and Augmented Lagrangian Functions
- Other Multivariable Constrained Search Methods
- Comparison of Constrained Multivariable Search Methods
- Stochastic Approximation Procedures
- Closure
- FORTRAN Program for BFGS Search of an Unconstrained Function
- References
- Problems
| Stochastic Approximation Procedures | top |
All of the procedures described up to now have been for deterministic processes, and they can be confounded by random error. There are search techniques that converge to an optimum in the face of random error, and some of these will be discussed briefly following the approach of Wilde(10) who gives more details about these methods. Random (e.g., experimental) error clouds the preception of what is happening and greatly hampers the search for the optimum. Stochastic approximation procedures deal with random error as noise superimposed on a deterministic process. Therefore, convergence to the optimum must be considered first and then efficiency can be evaluated. The works of Dvoretzky, Kiefer and Wolfowitz in this area have been summarized in an excellent manner by Wilde(10). Consequently, only the most important of these techniques will be described. This is the Kiefer-Wolfowitz stochastic approximation procedure, and it is applicable for n independent variables.
With noise present a search technique is forced to creep to prevent being confounded by random error. However, for unimodal functions, it can be shown that stochastic approximation procedures converge to the optimum in the mean square and with probability one.
The Kiefer-Wolfowitz algorithm is given by the following equation. Beginning at a starting point xo, the method proceeds according to this equation:
(6-74)
For convergence, the parameters ak and ck must satisfy the following criteria:
The following example illustrates the use of the Kiefer-Wolfowitz procedure.
Example 6-13
Develop the procedure to obtain the minimum of a function of the form [Ax1(x1 - x1*)2 + Bx2(x2 - x2*)2] which is affected by experimental error. The value of the minimum is somewhere on the interval 1< x1* < 3, 1 < x1* < 3. Starting with the mid-point of the interval, give the equations for the second, third and last of twenty trials.
Solution: a k = 1/k, c k = 1/k 1/4
satisfies the criterion of the equation (6-75).
For x2 = (x1,2, x2,2), k = 1:
For x3 = (x1,3, x2,3), k = 2:
For x20 = (x1,20, x2,20), k = 19:
There are variations of the above procedure such as using only the sign of the approximation to the derivatives. This can be used effectively when there is difficulty with convergence which is being caused by the shape of the curve on either side of the optimum. Also, a forward difference approximation can be used in evaluating the derivative rather than the central difference form, but convergence is not as rapid.
| Closure | top |
In this chapter the important algorithms for optimizing a nonlinear economic model with nonlinear constraints have been described, and their performance has been reviewed. This required presenting methods for unconstrained problems first and outlining the strategy required to move from a starting point to a point near an optimum. It was not possible to discuss each of the many algorithms that have been proposed and employed as unconstrained multivariable search techniques, but the references at the end of the chapter will lead to comprehensive descriptions of those procedures. The texts by Avriel(9), Fletcher(4,5), Gill et al.(6), Himmelblau(8), McCormick(7) and Reklaitis et al.(15) are particularly recommended for this purpose. However, the more successful algorithms were described for both unconstrained and constrained optimization problems. It is recommended that the BFGS algorithm be used for unconstrained problems and a FORTRAN program for this procedure (Table 6-4) has been included at the end of the chapter. For constrained problems the three methods that have been more successful in comparison studies on industrial problems are successive linear and quadratic programming (SLP and SQP) and generalized reduced gradient (GRG). Advanced computation techniques for numerical derivatives and sparse matrix manipulations are required to have efficient codes, and sources to contact for these types of programs were referenced.
In addition to deterministic optimization methods, stochastic approximation procedures were described briefly based on material from Wilde's book(10). These methods are designed to locate the optimum in the face of experimental error, even though their movement is slowed to avoid being confounded.
This area of optimization is probably the most rapidly growing part of the subject. The growth of computers and applied mathematical techniques for large systems of equations promises to continue to allow significant developments to take place.
| References | top |
1. Simon, J. D. and H. M. Azma, "Exxon Experience with Large Scale Linear and Nonlinear Programming Applications", Computers and Chemical Engineering, Vol. 7, No. 5, p. 605 (1983).
2. Waren, A. D. and L. S. Lasdon, "The Status of Nonlinear Programming Software", Operations Research, Vol. 27, No. 3, p. 431 (May-June, 1979).
3. Lasdon, L. S., "A Survey of Nonlinear Programming Algorithms and Software", Foundations of Computer-Aided Chemical Process Design, Vol. 1, p. 185, American Institute of Chemical Engineers, New York (1981).
4. Fletcher, Roger, Practical Methods of Optimization, Vol. I, Unconstrained Optimization, John Wiley and Sons, Inc., New York(1981).
5. Fletcher, Roger, Practical Methods of Optimization, Vol. II, Constrained Optimization, John Wiley and Sons, Inc., New York (1981).
6. Gill, P. E., E. Murray and M. H. Wright, Practical Optimization, Academic Press, New York (1981).
7. McCormick, G. P., Nonlinear Programming: Theory, Algorithms and Applications, John Wiley and Sons, Inc., New York (1983).
8. Himmelblau, D. M., Applied Nonlinear Programming, McGraw-Hill Book Company, New York (1972).
9. Avriel, Mordecai, Nonlinear Programming: Methods and Analysis, Prentice-Hall, Inc., Englewood Cliffs, New Jersey (1976).
10. Wilde, D. J., Optimum Seeking Methods, Prentice Hall Inc., Englewood Cliffs, New Jersey (1964).
11. Avriel, M., "Nonlinear Programming", Chapter 11 in Mathematical Programming for Operations Researchers and Computer Scientists, Ed. A. G. Holtzman, Marcel Dekker, Inc., New York (1981).
12. Wilde, D. J. and C. S. Beightler, Foundations of Optimization, Prentice-Hall, Inc., Englewood Cliffs, New Jersey (1967).
13. Fletcher, Roger, op. cit. p. 57, Vol I.
14. Churchhouse, R. F., Handbook of Applicable Mathematics, Vol. III, Numerical Methods, John Wiley and Sons, Inc., New York (1981).
15. Reklaitis, G. V., A. Ravindran and K. M. Ragsdell, Engineering Optimization, Methods and Applications, John Wiley and Sons, Inc., New York (1983).
16. Kuester, J. L. and J. H. Mize, Optimization Techniques with Fortran, McGraw-Hill Book Company, New York (1973).
17. Smith, C. L., R. W. Pike and P. W. Murrill, Formulation and Optimization of Mathematical Models, International Textbook Company, Scranton, Pennsylvania (1970).
18. Griffith, R. E. and R. A. Stewart, " A Nonlinear Programming Technique for the Optimization of Continous Processing Systems", Management Science, Vol. 7, p. 379 (1961).
19. Lasdon, L. S., op. cit., p. 202.
20. Sandgren, Eric, The Utility of Nonlinear Programming Algorithms, Ph.D. dissertation, Purdue University, West Lafayette, Indiana (1977).
21. Colville, A. R., A Comparative Study of Nonlinear Programming Codes, IBM New York Scientific Center Report No. 320 - 2949, IBM Corporation, New York Scientific Center, 410 East 62nd Street, New York, NY 10021 (June, 1968).
22. Lasdon, L. S. and A. D. Waren, "Large Scale Nonlinear Programming," Computers and Chemical Engineering, Vol. 7, No. 5, p. 595 (1983).
23. Franklin, Joel, Methods of Mathematical Economies, Linear and Nonlinear Programming, Fixed Point Theorems, Springer-Verlag Inc., New York (1980).
24. Vanderplaats, G. N., Numerical Optimization Techniques for Engineering Design with Applications, McGraw - Hill Book Company, New York (1984).
25. Hillier, F. S. and G. J. Lieberman, Operations Research, Holden - Day, Inc., San Francisco (1974).
26. Walsh, G. R., Methods of Optimization, John Wiley & Sons Inc., New York (1975).
27. McMillan, Jr., Claude, Mathematical Programming: An Introduction to the Design and Application of Optimal Decision Machines, John Wiley & Sons, Inc., New York (1970).
28. Gottfried, B. S. and Joel Weisman, Introduction to Optimization Theory, Prentice - Hall, Inc., Englewood Cliffs, New Jersey (1973).
29. Wolfe, P., "Methods of Nonlinear Programming" in Recent Advances in Mathematical Programming, Ed. R. L. Graves and P. Wolfe, McGraw - Hill Book Company, New York (1963).
30. Abadie, J. and J. Carpentier, "Generalization of the Wolfe Reduced Gradient Method to the Case of Nonlinear Constraints," in Optimization, Ed. R. Fletcher, Academic Press, London (1969).
31. Pollack, A. W. and W. D. Lieder, "Linking Process Simulators to a Refinery Linear Programming Model" in Computer Applications to Chemical Engineering, Ed. R. G. Squires and G. V. Reklaitis, ACS Symposium Series No. 124, American Chemical Society, Washington, D. C. (1980).
32. O'Neil, R. P., M. A. Williard, Bert Wilkins and R. W. Pike, "A Mathematical Programming Model for Natural Gas Allocation," Operations Research, Vol. 27, No. 5, p. 857 - 873 (Sept./Oct., 1979).
33. Sargent, R. W. H., "A Review of Optimization Methods for Nonlinear Problems" in Computer Applications to Chemical Engineering, Ed. R.G. Squires and G. V. Reklaitis, ACS Symposium Series No. 124, American Chemical Society, Washington, D.C. (1980).
34. Cooper, Leon, and David Steinberg, Introduction to Methods of Optimization, W. B. Saunders Company, Philadelphia (1970).
35. Adby, P. R. and M. A. H. Dempster, Introduction to Optimization Methods, John Wiley and Sons, Inc., New York (1974).
36. Bracken, J. and G. P. McCormick, Selected Applications of Nonlinear Programming, p. 16f, John Wiley and Sons, Inc. New York (1968).
37. Ray, W. H. and J. Szekely, Process Optimization with Applications in Metallurgy and Chemical Engineering, John Wiley and Sons, Inc., New York (1973).
38. April, G. C. and R. W. Pike, "Modeling Complex Chemical Reaction Systems," Industrial and Engineering Chemistry, Process Design and Development, Vol. 13, No. 1, p.1 (January, 1974).
39. Fletcher, R., "Methods Related to Lagrangian Functions," Numerical Methods for Constrained Optimization, Ed. P. E. Gill and W. Murray, Academic Press, New York (1974).
40. Doering, F. J. and J. L. Gaddy, "Optimization of the Sulfuric Acid Process with a Flowsheet Simulator," Computers and Chemical Engineering, Vol. 4, p. 113 (1980).
41. Martin, D. L. and J. L. Gaddy, "Modeling the Maleic Anhydrate Process," Summer National Meeting, American Institute of Chemical Engineers, Anaheim (May 20 - 24, 1984).
42. Jirapongphan, S., J.F. Boston, H. I. Britt and L. B. Evans, "A Nonlinear Simultaneous Modular Algorithm for Process Flowsheeting Optimization," American Institute of Chemical Engineers Annual Meeting, Chicago (November, 1980).
43. Murtagh, B. A. and M. A. Saunders, MINOS 5.0 Users Guide, Technical Report SOL 83 - 20, Systems Optimization Laboratory, Department of Operations Research, Stanford University (December, 1983).
44. Beigler, L. T. and R. R. Hughes, "Process Optimization: A Comparative Case Study," Computers and Chemical Engineering, Vol. 7, No. 5, p.645 (1983).
45. Locke, M. H. and A. W. Westerberg, "The ASCEND-II System - A Flowsheeting Application of a Successive Quadratic Programming Methodology," Computers and Chemical Engineering, Vol. 7, No. 5, p. 615 (1983).
46. Locke, M. H. , A. W. Westerberg, and R. H. Edahl, "Improved Successive Quadratic Programming Optimization Algorithm for Engineering Design Problems," AIChE Journal, Vol. 29, No. 5, p.871 (September, 1983).
47. Palacios-Gomez, F., L. Lasdon and M. Engquist, "Nonlinear Optimization by Successive Linear Programming," Management Science, Vol. 28, No. 5, p.871 (September, 1983).
48. Chen, H. S. and M. A. Stadtherr, "Enhancements of the Han-Powell Method for Successive Quadratic Programming," Computers and Chemical Engineering, Vol. 8, No. 3/4, p. 229 (1984).
49. Biegler, L. T. and R. R. Hughes, "Infeasible Path Optimization with Sequential Modular Simulators," AIChE Journal, Vol. 28, No. 6, p. 994 (November, 1982).
50. Bertsekas, Dimitri P., Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York (1982).
51. Han, S. P., "A Globally Convergent Method for Nonlinear Programming," Journal of Optimization Theory and Applications, Vol. 22, No. 3, p. 297 (July, 1977).
52. Han, S. P., "Superlinearly Convergent Variable Metric Algorithms for General Nonlinear Programming Problems," Mathematical Programming, Vol. 11, p. 263, Noth-Holland Publishing Company (1976).
53. Biegler, L. T. and J. E. Cuthrell, "Improved Infeasible Path Optimization for Sequential Modular Simulators - II: The Optimization Algorithm," Computer and Chemical Engineering, Vol. 9, No. 3, p. 257 (1985).
54. Haftka, R. T. and M. P. Kamat, Elements of Structural Optimization, Martinus Nijhoff Publisher, Dordrecht, The Netherlands (1985).
55. Dennis, J. E., and R. B. Schnable, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice - Hall Inc., Englewood Cliffs, New Jersey (1983).
56. Bazaraa, M. S. and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, John Wiley and Sons, Inc., New York (1979).
57. Powell, M. J. D., "An Efficient Method for Finding the Minimum of a Function of Several Variables without Calculating Derivatives," The Computer Journal, Vol. 7, p. 155 (1964).
58. Drud, Arne, "CONOPT: A GRG Code for Large Sparce Dynamic Nonlinear Optimization Problems," Mathematical Programming, Vol. 31, p. 153 (1985).
59. Hadley, G. H., Nonlinear and Dynamic Programming, Addison - Wesley Publishing Company, Inc., Reading, Mass., p. 191 (1964).
| Problems | top |
6-1(10). A Fibonacci search can be used to find the point on a line in space where a function is maximum. For the two points (1,-1,0,2) and (-5,-1,3,1) use a Fibonacci search assuming perfect resolution and unimodality.
a. Give the coordinates of the points where the first two experiments would be placed assuming a total of five measurements will be used.
b. What is the final interval of uncertainty on the coordinate axis x1?
6-2(10). In the folowing table eight values of y are given, and y is a function of four independent variables.
a. Determine the line of steep ascent passing through the point (0,1,-1,3).b. Determine the contour tangent hyperplane passing through (0,1,-1,3).
6-3(17). Use the method of gradient partan to find the minimum of the following function starting at (2,1,3).
y = x12 + 3x22 + 5x32
6-4. For the following function draw contours on a graph for values of y of 20.0, 40.0, 60.0 and 80.0 in the region 0 < x1< 10 and 0 < x2 < 10.
y = x1x2
Starting at point xo(4,4) apply Pattern Search to move toward maximum and employ a step size d(1/2,1/2). Make local explorations and accelerations (pattern moves) to obtain the points through b5.
6-5. In Figure 6-12 a contour map is given for a function with a maximum located in the upper center. For the four multivariable search techniques, gradient search, sectioning, gradient partan and pattern search, sketch (precisely) the path these algorithms would take, beginning at the indicated starting point and going toward the maximum. For pattern search make the step-size equal to one-half of the width of the grid. The pattern search step size can be cut in half for the search to continue, if necessary. This will be the resolution limit, however. In addition, make brief comments about the effectiveness of these four techniques as applied to this function.
6-6. On the contour map given in Figure 6-13 sketch (precisely) the path of gradient partan, Powell's method and pattern search beginning at the starting point shown. For pattern search have the step size initially equal to the grid shown on the contour map and reduce the step size by one-half to have the search continue. Reduce the step size by one-half again if neccessary to have pattern search continue. Give a brief discussion of the performance of these methods on this function.
6-7. Newton's method is obtained from the Taylor series expansion for y(x), truncating the terms which are third order and higher, equation (6-8). Then equation (6-12) is obtained from the quadratic approximation, where x is the location of the minimum of the quadratic approximation. Discuss the iterative procedure that would be used to move to an optimum. To ensure convergence to a minimum (maximum), the value of dy(a)/da always must be negative (positive), where is the parameter of the line between points xk and xk+1 obtained from successive applications of the algorithm.
x = xk + a(xk+1 - xk)
Explain why this restriction is required for convergence to a local minimum (maximum).
6-8. Search for the minimum of the following function using gradient search starting at point xo(1,1,1).
y = x12 + x22 + x32
6-9. Develop and use a simplified version of Newton's method (quadratic fit) to search for the minimum of the function given in Problem 6-8 starting at the same point. Give the Taylor series expansion for three independent variables truncating third and higher order terms neglecting iteracting (mixed partial derivative) terms for simplicity. Differentiate the truncated Taylor series equation of with respect to x1, x2 and x3 to compute the optimum of the quadratic approximation, x, x and x. Then apply these results to minimize the function of the problem. Compare the effort required for one iteration of the linear algorithm in problem 6-8 to one iteration of the quadratic algorithm.
6-10. In problem 7-7 a simplified alkylation process with three identical reactors in series is described. The profit function for each reactor can be represented by an equation with elliptical contours, and the catalyst degradation function can be represented by a linear equation.
a. If the optimum of the profit function for an individual reactor is at F = 10 and C = 95, derive the profit function to be maximized and the constraint equations to be satisfied for the process. The profit function for one reactor is given by the following equation.
y = 150 - 6(F - 10)2 - 24(C-95)2
The constraint equations have the form y = mx + b, and the parameters m and b can be determined from Figure 7-32.
b. Form the penalty function for the above problem and discuss how this form will maximize the profit function and satisfy the constraint equations when a search technique is used to find the optimum.
6-11. Solve the following optimization problem by successive linear programming starting at xo(0,1/2) using limits of (1,1). Reduce the limits by one-half if infeasible points are encountered.
Minimize: (x1 - 2)2 + (x2 - 1)2
Subject to: (-1/4) x1 - x22 + 1 > 0
x1 - 2x2 + 1 = 0
6-12. Solve the following optimization problem by successive linear programming starting at point xo(1,1) using limits of (1,1). Reduce the limits by one-half if infeasible points are encountered.
Maximize : 4x1 + x2
Subject to: x12 + 2x22 < 20.25
x12 - x22 < 8.25
6-13. Solve the following optimization problem by successive linear programming starting at point xo(1,1) using limits of (1,1). Reduce the limits by one-half if infeasible points are encountered.
Minimize : y = 2x12 + 2x1x2 + x22 - 20x1 - 14x2
Subject to: x12 + x22 < 25
Solutionx12 - x22 < 7
6-14(26). Solve the following problem by successive linear programming starting at point (2,1) using limits of (1/2,1/2). Reduce the limits by one-half if infeasible points are encountered.
Maximize: 2x12 - x1x2 + 3x22
Subject to: 3x1 + 4x2 < 12
x12 - x22 > 1
6-15(34). Solve the following problem by successive linear programming starting at point xo(1,1) using limits of (2,2). Reduce the limits by one-half if infeasible points are encountered.
Maximize: 3x12 + 2x22
Subject to: x12 + x22 < 25
Solution9x1 - x22 < 27
6-16. The following multivariable optimization problem is shown in figure 6-7.
Minimize: -2x1 - 4x2 + x12 + x22 + 5
Subject to: - x1 + 2x2 < 2
x1 + x2 < 4
a. Give the successive linear programming algorithm for this problem in the form of equations (6-34). The upper and lower bounds are the same and are equal to 1.0.
b. For starting point xo = (0,0) apply the algorithm from part a to search for the optimum by successive linear programming.
6-17. Solve problem 6-16 by quadratic programming.
Solution
6-18(26). Solve the following problem by quadratic programming.
Maximize: -2x12 - x22 + 4x1 + 6x2
Subject to: x1 + 3x2 < 3
6-19(27). Solve the following problem by quadratic programming.
SolutionMaximize: 6x1 - 2x12 + 2x1x2 - 2x22
Subject to: x1 + x2 < 2
6-20(28). Solve the following problem by quadratic programming.
Maximize: 9x2 + x12
Subject to: x1 + 2x2 = 10
6-21. Solve the following problem by quadratic programming.
Minimize: 2x12 + 2x1x2 + x22 - 20x1 - 14x2
Subject to: x1 + 3x2 < 5
2x1 - x2 < 4
6-22. Solve the following problem by the generalized reduced gradient method starting at the feasible point xo(1,1,19) to find the optimum located at x*(4,3,0). Use the optimum point to determine the appropriate value of the parameter of the reduced gradient line for one line search to arrive at the optimum.
SolutionMaximize : 3x12 + 2x22 - x3
Subject to: x12 + x22 = 25
9x1 - x22 + x3 = 27
6-23(11). Solve the following problem by the generalized reduced gradient method. Start at the point xo = (2,1,3,1) and have x1 and x4 be the basic or dependent variables and x2 and x3 the nonbasic or independent variables.
Minimize : x12 + 4x22
Subject to: x1 + 2x2 - x3 = 1
Solution-x1 + x2 + x4 = 0
6-24. Solve the following problem by the generalized reduced gradient method starting at point xo(2,4,5). Show that the value of the parameters of the reduced gradient line 1 = -1/20 locates the minimum of the economic model and satisfies the constraints.
Minimize : 4x1 - x22 + x32 - 12
Subject to: -x12 - x22 + 20 = 0
Solutionx1 + x3 - 7 = 0
6-25(17). Find the minimum of the following function starting at the point xo(1,1,1). However, this time experimental error is involved; and the Kiefer-Wolfowitz procedure must be used, employing ak = 1/k and ck = 1/k1/4 with k = 1, 2, ...12. Simulate experimental error by flipping a coin and adding (subtracting) 0.1 from y if the coin turns up heads (tails).
y = x12 + 3x22 + 5x32
6-26. Solve the following problem by successive quadratic programming and the generalized reduced gradient method, starting at point xo(0,1/2), and compare these results to the solution given in Figure 6-8.
Minimize: (x1-2)2 + (x2-1)2
Subject to: - ¼ x12- x22 + 1 0
Solutionx1 - 2x2 + 1 = 0