|
Chapter 5 | 
|
SINGLE VARIABLE SEARCH TECHNIQUES
- Introduction
- Search Problems and Search Plans
- Sequential Search Methods
- Open Initial Interval
- Other Methods
- Closure
- References
- Problems
| Closure | top |
In this chapter we began by describing search problems for background to single-variable and multivariable search techniques. Then the conservative, minimax, single-variable search procedures were developed and illustrated for both simultaneous and sequential applications. Also, the use of single-variable methods with multivariable problems was described, and this included techniques for open intervals. The chapter closed by reviewing the nonminimax sequential procedure of a quadratic fit to profit function and an associated algorithm to bound the optimum.
In summary, both the minimax and quadratic methods have been used effectively in industrial applications, and both have advocates in the literature. The minimax procedures tend to require more complicated computer programs, but offer the guarantee of locating the final interval containing the optimum in a specified number of steps for a unimodal function. The quadratic method procedures tend to have less complicated computer programs, but this depends on stopping and oscillation-prevention logic. Also, there is no guarantee of locating a specific interval containing the optimum in a specified number of steps. However, a super-linear rate of convergence is claimed for them(8). As pointed out by Himmelblau (7), one of the more important evaluations of a single-variable method is how it performs when embedded in a multivariable procedure, and he presents some limited results that show no really significant advantage for either approach. Unfortunately, none of the multivariable procedures has been found clearly superior to the others, to let us extend these results for a comprehensive evaluation. For further information Avriel (3) has given a comprehensive, concise mathematical description of essentially all of the single-variable methods including the ones discussed here and others such as the cubic method, Newton's method, secant method, and the block search techniques. Also, the related theorems on rates of convergence are given and discussed. In addition, McCormick (9) reports a new method for continuous function with continuous derivatives that may become important as evaluations of methods continue.
| References | top |
1. Wilde, D. J., Optimum Seeking Methods, Prentice-Hall, Inc., Englewood Cliffs, New Jersey (1964).
2. Wilde, D. J., and C. S. Beightler, Foundations of Optimization, Prentice-Hall Inc., Englewood Cliffs, N. J. (1967).
3. Avriel, M., Nonlinear Programming, Analysis and Methods, Prentice Hall Inc., Englewood Cliffs, N. J. (1976).
4. Beightler, C. S., D. T. Phillips, and D. J. Wilde, Foundations of Optimization, Sec. Ed., Prentice-Hall Inc., Englewood Cliffs, N. J. (1969).
5. Kuester, J. L., and J. H. Mize, Optimization Techniques with FORTRAN, McGraw-Hill Book Company, New York (1973).
6. Beveridge, G. S., and R. S. Schechter, Optimization: Theory and Practice, McGraw-Hill Book Co., New York (1970).
7. Himmelblau, D. M., Applied Nonlinear Programming, McGraw-Hill Book Company, New York, (1972).
8. Box, M. C., D. Davies, and W. H. Swann, Nonlinear Optimization Techniques, Oliver & Boyd Ltd., Edinburgh, Great Britain (1969).
9. McCormick, G. P., Nonlinear Programming 4, Ed. O. L. Mangasarian, R. R. Myer, and S. M. Robinson, Academic Press, New York, p. 223 (1981).
10. Stoecker, W. F., Design of Thermal Systems, McGraw-Hill Book Company, New York (1971).
11. Armijo, L., "Minimization of Functions Having Lipschitz Continuous First Partial Derivatives," Pacific Journal of Mathematics, 16(1):1 (1966).
12. Biegler, L. T. and J. E. Cuthrell, "Improved Infeasible Path Optimization for Sequential Modular Simulators-II:2 The Optimization Algorithm," Computers & Chemical Engineering, 9(3):257 (1985).
| Problems | top |
5-1. In Figure 5-10 the profit function is given for a sulfuric acid alkylation reactor as a function of feed rate and catalyst concentration. Plot the profit function as a function of feed rate for a constant catalyst concentration of 95%. Place six golden section experiments on the interval giving their location, the corresponding value of the profit function and the length and location of the final interval of uncertainty.
Figure 5-10. Profit Function for the Operation of a Sulfuric Acid Alkylation Reactor as a Function of Catalyst Concentration and Feed Rate
5-2. Show that equation (5-43) for x2 can be put in the following form in terms of and Io.
x2 = [ 1 + e(An-1 - An-2 An+1 /An)] (An /An+1) Io
5-3. Derive equation (5-65) from equation (5-64).
5-4. Compare the final intervals of uncertainty (initial being 1.0) for simultaneous elimination, Fibonacci search, and golden section search using 2, 5, and 10 experiments. Assume perfect resolution. Give conclusions from this comparison.
5-5. Compare the anticipated performance of Fibonacci search and the quadratic method for the following types of unimodal, single-variable functions: quadratic, continuous, arbitrary, and discrete.
5-6. In Bolzano's method (2) both the value of the function y(x) and the first derivative of the function y'(x) are evaluated at a point to eliminate the part of the line that does not contain the optimum. For a unimodal function the final interval In is given by the following equation for this method:
In = Io /2n
where n is the number of combined evaluations of y(x) and y'(x) that are made, and Io is the initial interval of uncertainty. Compare Bolzano's method with Fibonacci search and golden section search by computing the ratio of the final to the intial interval of uncertainty, In /Io, for each of the three techniques using 5 and 10 for n with Bolzano's method and 10 experiments each with Fibonacci and golden section searches.
5-7.(1) The results of an eight experiment simultaneous search plan for the interval 2 < x* < 12 is given below.
y - 1.0 1.5 3.2 3.0 2.6 2.3 1.9 1.4 -
x 2 3.1 4.2 5.0 6.5 7.1 8.8 9.5 10.5 12
What are the possible final intervals of uncertainty, the maximum one and the one that contains the maximum values of y?
5-8. For Examples 5-2 and 5-3 determine the final interval by placing a fifth experiment by Fibonacci and golden section searches.
5-9.(10) Determine the maximum of the following function using golden section search on the initial interval shown:
y = 12x - 2x2 on 0 < x* < 10
Conduct the search until the difference between the two largest values of y is 0.01 or less. Give this largest value of y and the corresponding value of x. Compare this with the result obtained by using the classical theory of maxima and minima.
5-10(10) An economic analysis of a proposed facility is being conducted in order to select an operating life such that the maximum uniform annual income is achieved. A short life results in high annual amortization costs, but the maintenance costs become excessive for a long life. The annual income after deducting all operating costs, except maintenance costs, is $180,000. The installed cost of the facility, C, is $500,000 borrowed at 10% interest compounded annually. The maintenance charges on an annual basis are evaluated using the product of the gradient present-worth factor and the capital-recovery factor. In the gradient present-worth method, there are no maintenance charges the first year, a cost M for the second year, 2 M for the third year, 3 M for the fourth year, etc. The second year cost, M, for the problem is $10,000. The annual profit is given by the following equation:
P = 180,000 - {[(i+1)N -1 - iN] / i[(1+ i)N -1]}M - {i(1+ i)N / [(1+ i)N -1]}C
where i is the interest rate and N is the number of years. Determine the number of years, N, that give the maximum uniform annual income, P. For your convenience the following table gives the values of the coefficients of M and C for i = 0.1 as a function of N:
Coefficient of Coefficient of
Year M C Year M C
1 0 1.10 11 4.05 0.154
2 0.476 0.576 12 4.39 0.147
3 0.909 0.403 13 4.69 0.141
4 1.30 0.317 14 5.00 0.136
5 1.80 0.264 15 5.28 0.131
6 2.21 0.230 16 5.54 0.128
7 2.63 0.205 17 5.80 0.125
8 2.98 0.188 18 6.05 0.122
9 3.38 0.174 19 6.29 0.120
10 3.71 0.163 20 6.51 0.117
5-11. Find the maximum of the following open-ended function which represents a line in space from a multivariable search method using seven golden section search measurements including the last two that bound the function. Begin the bounding of the function with the first experiment at a = 1.0, and continue until the function is bounded. Then proceed with five more golden section measurements to locate the maximum. Compare the best value found in the seven experiment golden section search with the exact value of the maximum computed using the classical theory of maxima and minima.
y = 2 - a½ 2 on 0 < a < ¥
5-12. It is proposed to recover the waste heat from exhaust gases leaving a furnace (flow rate, m = 60,000 lb/hr; heat capacity, cp = 0.25 BTU/lboF) at a temperature of Tin = 500oF by installing a heat exchanger (overall heat transfer coefficient, U = 4.0 BTU/hr,ft2,oF) to produce steam at Ts = 220oF from saturated liquid water at 220oF. The value of heat in the form of steam is p = $0.75 per million BTU's, and the installed cost of the heat exchanger is c = $5.00 per ft2 of gas side area. The life of the installation is n = 5 years, and the interest rate is i = 8.0%. The following equation gives the net profit P for the 5 year period from the sale of the steam and the cost of the heat exchanger. The exaust gas temperature Tout can be between the upper and lower limits of 500oF and 220oF.
P = pqn - cA(1 + i)n
where
q = mcp(Tin - Tout) = UADTLM
a. Derive the following equation for this design.
P = 91,137 - 492.75Tout + 27550ln(Tout - 220)
b. Use a Fibonacci search with seven experiments to locate the optimal outlet temperature Tout to maximize the profit P on the interval of Tout from 220oF to 500oF. Find the largest value of the profit and the size and location of the final interval of uncertainty for the fractional resolution based on the initial interval of e = 0.01.
c. Use analytical methods to determine the optimal profit and temperature.
5-13. a. The need to be able to distinguish between outcomes of experiments gives a relation between the final interval of uncertainty In and the fractional resolution e based on the initial interval of uncertainty Io. Referring to Figure 5-8, the experiments xn, xn-1, and xn-2 must all be separated by a distance of no less than eIo to be able to distinguish among their outcomes y(xn), y(xn-1), and y(xn-2). This can be expressed as:
In = xn-2 - xn = (xn-2 - xn-1) + (xn-1 - xn) > 2eIo
Using equations (5-39) and (5-41), show that the following inequality is obtained to relate the Fibonacci numbers and the fractional resolution e.
An-2 < 1 / e
b. If a fractional resolution e = 0.01 is required, how many experiments are needed according to the results in part a.
c. Search for the maximum of the following function using a Fibonacci search with a fraction resolution of 0.05 on the interval 0 < x* < 1 using the criterion developed in part (a) and (b):
y(x) = ex - 2x2
5-14. Demonstrate your understanding of the minimax principle by solving the following problems given by Wilde(1).
a. "You are convinced that your optimization professor is trying to fail you if he can get enough evidence to do so. You are trying to decide whether or not to read the assignment for next Thursday. If you read it and the professor gives a ten minute quiz, you can expect to gain 10 points toward your final average. If there is no quiz, the knowledge you gained by reading the assignment will probably give you an extra five points on the next hour exam. You may go to the movies instead, and if there is no optimization quiz you will have three points worth of relaxation. But if there is a quiz and you haven't studied, your score will be zero for the day and the movie will be no consolation. What should be your mimimax decision? If your professor is really out to get you what will he do?"
b. "Suppose that you have a third alternative, namely to study for an exam in another course. If then there is no optimization quiz, you can at least pick up eight points in your other course. But if your optimization professor gives a quiz, your zero in optimization will bring your average for the day down to four points. What should be your minimax strategy?"