|
SINGLE VARIABLE SEARCH TECHNIQUES
- Introduction
- Search Problems and Search Plans
- Sequential Search Methods
- Open Initial Interval
- Other Methods
- Closure
- References
- Problems
| Introduction | top |
In this and the next chapter, techniques are presented which are applicable to complex problems where the economic model and constraints can be in the form of a computer program or the process itself, in contrast to previous methods which required specific equations. The optimization problem is illustrated in Figure 5-1, where specifying inputs will produce outputs. The figure shows the general names associated with the inputs and outputs. Specifying the values of the independent variables determines the dependent variables. However, the values of the dependent variables could be affected by random error and parameters of the system. Also, a process example is given in the figure to illustrate these inputs and outputs. The dependent variable of product conversion is determined by the feed rate of the raw material and the temperature and pressure of the process. In addition, the parameter of feed composition and the random error associated with measuring the process inputs and outputs affect the value of this dependent variable. Other examples for different disciplines are given by Wilde(1).
In this chapter the effective interval elimination procedures for single-variable search methods will be emphasized. These methods rapidly reduce the interval containing the location of the optimum, using the minimax principle as the experiments are placed either sequentially or simultaneously. First, it will be necessary to define and describe search problems, search plans, unimodality, and the minimax principle briefly to establish foundation for these techniques. In addition, other well-known single-variable methods will be presented, and they will be compared with the interval elimination procedures. Moreover, it will be seen that multivariable search techniques of Chapter 6 will incorporate single-variable methods. Also, a listing of a computer program for the most important method is given in this chapter.
| Search Problems and Search Plans |
A search problem has been represented in Figure 5-1 as a "black box" for the process where the values of the economic model are computed by specifying inputs. Consequently, a search problem can be defined as an investigation that seeks the optimal value of a function. Search problems can be classified by the number of independent variables and by the absence or presence of random or experimental error.
Deterministic problems have no experimental error or random factors present. An example is the mathematical model of a process, where the outputs are calculated by a computer program from specified inputs. Stochastic problems have random error present, usually in the form of experimental errors from measurement of the process variables. An example is a plant where there are experimental errors associated with laboratory and instrument measurements of the process flow rates and compositions.
For the solution of single-variable problems that do not have random error, there are powerful techniques based on the minimax principle. Unfortunately, comparable results are not available for multivariable problems except in the special case where the economic model is rectangular unimodal (2). To optimize stochastic problems, they are treated as deterministic with noise superimposed. The effect is to slow the search for the optimum, as discussed by Wilde (1).
To find the optimum of a search problem, a search plan is needed. A search plan is a set of instructions for performing n sets of experiments; x1, x2, ..., xn, (values of the independent variables). An experiment consists of specifying one set of values of the independent variables, e.g., temperature, pressure, and raw material feed rate for a process, and determining the values of the outputs, e.g., product conversion. This could be done using the process itself or using a computer program of the mathematical model of the process for the evaluation of the dependent variables.
Search plans can be classified as either simultaneous or sequential. In a simultaneous search plan the locations of all of the experiments are specified, and the outcome of the measurements is obtained at the same time. An example is the location of a set of thermocouples installed along the length of a fixed-bed reactor to determine the position of the hot spot (maximum temperature) in the catalyst bed while the process is in operation. In a sequential search plan the outcome of an experiment is determined before another experiment is made. Being able to base future experiments on past outcomes is a significant advantage. In fact, it can be shown that the advantage of sequential search plans over simultaneous search plans increases exponentially with the number of experiments (1).
We will begin by describing simultaneous search plans, and use these results to obtain sequential search plans. These plans, which are based on the minimax principle, are completely conservative, do not depend on luck, and rapidly reduce the interval that contains the optimum with relatively few measurements. Also, with the minimax principle the optimal search plan can be selected to find the optimum of the search problem.
| Unimodality | top |
A function is unimodal if it has only one maximum or minimum in the region to be searched. Examples of unimodal functions are shown in Figure 5-2. As shown in the figure, an unimodal function can be continuous or discontinuous, have discontinuous first derivatives, or be defined only at discrete values of the dependent variable.
An unimodal function can be defined without using derivatives as follows. Let x1 and x2 (> x1) be two experiments placed in the interval a < x < b, and y1 and y2 be the results obtained from the profit function having a maximum at y* = y(x*). Then y is unimodal if x2 < x* implies that y1 < y2, and if x1 > x* implies that y1 > y2. In other words, if the points are both on the same side of the optimum, then the one near the optimum has the higher values of y (1). This definition does not require a continuous function, and it will allow a search technique to be developed for unimodal discrete functions. Moreover, while search techniques are developed for unimodal functions, they will work on multimodal functions also. However, they will only locate one of the maxima or minima. In the following discussion all of the functions are considered to be unimodal, and they have one maximum and one minimum either in the interval or on the boundary.
| Reducing the Interval of Uncertainty | top |
Generally, we know the initial interval on the independent variable to be searched for the maximum of the profit function (or the minimum of the cost function). This interval is called the initial interval of uncertainty, and we need a systematic procedure to reduce the size of this interval. This can be accomplished by placing experiments and eliminating parts of the initial interval that do not contain the optimum.
Eliminating part of the initial interval of uncertainty is illustrated in Figure 5-3 for the three possible outcomes of two experiments placed on the interval 0 < x < 1. If y1 > y2 the maximum of the unimodal function could lie between 0 and x1 or x1 and x2, as the dotted lines illustrate. However, it can not lie in the interval between x2 and 1.0, and consequently, this part of the initial interval can be eliminated. Had the results of the experiments been y1 < y2, then the part of the interval between 0 and x1 could be eliminated. In the unlikely but lucky event that y1 = y2, then the maximum must lie between x1 and x2, and the parts of the initial interval between 0 and x1 and x2 and 1.0 are eliminated, as shown in the figure.
If the numerical values of x1 and x2 had been given, this would have specified a two-experiment search plan. We would like to search with the best search plan and reduce the interval of uncertainty as much as possible with a specified numb
er of experiments. Consequently, a measure of the effectiveness of search plans is needed, so the best one among all of those possible can be selected, i.e., the optimal search plan to optimize the function.
| Measuring Search Effectiveness(1) | top |
To compare search plans, the measure of effectiveness must be independent of functions being optimized. This is required to eliminate functional dependence, bias, and luck. Consequently, it is necessary to have the measure of the effectiveness of search plans depend on the placement of the experiments, but not on the outcomes of those experiments. Therefore, the criterion to be used in comparing search plans is the size of the largest interval of uncertainty possible, having determined the location of the experiments. This does not depend on the outcome of the experiments.
To illustrate this idea, let us compare the two search plans shown in Figure 5-4 for their effectiveness based on the largest interval of uncertainty having specified the location of the experiments. In the first search plan three experiments are located at x1 = 0.1, x2 = 0.4, x3 = 0.8, on an initial unit interval. The possible outcomes of the function at these values are shown on Figure 5-4. Also shown in this figure is the second search plan with experiments located at x1 = 0.25, x2 = 0.5, x3 = 0.75 on the same initial unit interval and the corresponding possible results of evaluating the function.
For the first search plan, the location of final intervals of uncertainty, i1, i2, and i3, depends on the outcome of the experiments. Let K be the index of the best of the three results, and we have:
If K = 1, then 0 < x* < x2 i1 = 0.4 luckiest
If K = 2, then x1 < x* < x3 i2 = 0.7 unluckiest
If K = 3, then x1 < x* < 1 i3 = 0.6 intermediate
In other words, if x1 (K = 1) has the largest value of y(x), then the final interval of uncertainty having placed three experiments would be i1 = 0.4. This would be a lucky outcome compared to having the largest value of y(x) be at x2, (K = 2) where the final interval would be i2 = 0.7. An intermediate result is obtained for K = 3 where i3 = 0.6. These results can be written as:
i = [0.4, 0.7, 0.6] for 1 < K < 3 (5-1)
For the second search plan the three points are equally spaced in the interval a distance 0.25 apart. Consequently, i1, i2, i3 = 0.5 regardless of the location of the largest value of y(x), whether it be at x1 (K=1), x2 (K=2) or x3 (K=3). This can be written as:
i = [0.5, 0.5, 0.5] for 1 < K < 3 (5-2)
If the two search plans are compared, based on their largest possible final interval of uncertainty, the selection would eliminate luck and not depend on the outcome of the experiments for a particular function. For the first search plan the largest final interval of uncertainty, I3, is:
and for the second search plan:
Consequently, the second search plan would be designated as the better of the two, since it has the smaller of the largest final intervals of uncertainty, i.e., I3 = 0.5.
This discussion has illustrated that search plans should be compared on their largest final interval of uncertainty to have a consistent and conservative measure for comparison. This eliminates functional dependence and luck as factors in comparing search plans. Also, the example has served to define a nomenclature that can be used to discuss search plans with n experiments.
In general, a search plan with n experiments, xn, specifies the size of all of the possible final intervals of uncertainty, as shown in Figure 5-5. This can be written as:
iK = (xK+1 - xK-1) for 1 < K < n (5-5)
and generates the iK values for n experiments that are comparable to those of equations (5-1) and (5-2) for the two, three-experiment search plans. In equation (5-5) xK-1 and xK+1 are the two experiments on either side of the experiment xK when it is considered to be the one to have the largest value of y(x).
EDIT Figure 5-5. Diagram of a search plan with n experiments showing the possible final intervals of
uncertainty.
The results of the experiments determine the value of the best outcome y(xK) (and the index K) and the location and size of the final interval of uncertainty, i.e., the specific iK that contains the best outcome xK. However, we need to compare search plans, xn, based on the largest final interval of uncertainty, In, which is independent of the outcome of the experiments. This can be written as:
This equation is a generalization of equations (5-3) and (5-4) for n experiments. It states that for a search plan xn, consider that each one of the n experiments could be the largest outcome, i.e., 1 < K < n. This defines n possible final intervals of uncertainty in. From those values of iK the largest one, In, is selected. This largest final interval of uncertainty is unique to this search plan and is independent of the outcome of the experiments.
| Minimax Principle(1) | top |
Having decided to compare search plans based on their largest final interval of uncertainty, we want to select the best search plan, xn*, i.e., the one search plan that has the smallest of the largest final intervals of uncertainty. This is a statement of the minimax principle which can be written as:
and substituting equation (5-6) into (5-7) gives:
Equation (5-8) is the mathematical statement of the minimax principle. It requires searching over all possible search plans xn having n experiments to evaluate their largest final intervals of uncertainty In. Then the search plan with the smallest one is selected as best. To evaluate the largest final interval of uncertainty for each search plan, it is necessary to consider that each of the n experiments x1, x2, ..., xn may have the largest possible outcome (1 < K < n). This will then enumerate the possible final intervals of uncertainty, in, from which the largest one can be selected.
This procedure sounds like a formidable task. However, it turns out to be relatively straightforward, and it is best illustrated by describing the cases of two and three experiments, first. The procedure can then be extended to n experiment search plans where the experiments are all placed at the same time (simultaneously) or placed one at a time (sequentially).
In Figure 5-6 two experiments are shown located on an initial unit interval. Using equation (5-6), we can write the largest final interval of uncertainty I2 as:
I2 = max [x2, 1 - x1] (5-9)
The smallest value of I2 can be obtained by having x1 and x2 as near the center of the interval as possible. For example, if x1= 0.4 and x2 = 0.8, then I2 = 0.8, and if x1 = 0.49 and x2 = 0.51, then I2 = 0.51. It is not possible to have x1 = x2 = 0.5 for I2 = 0.5, because x1 = x2 = 0.5 is the same point. There would be only one outcome, and it would not be possible to tell which segment of the interval to eliminate. Consequently, to have the minimum value of I2, we place the two experiments as close together as possible and still be able to detect a difference in the outcomes y1 and y2. This least separation between the experiments is called resolution and is indicated on the diagram in Figure 5-6 as e. Consequently, the best search plan for two experiments is to place them symmetrically in the interval separated by the resolution, and the final interval will be obtained from equation (5-9) having x1 = 0.5 - e/2 and x2 = 0.5 + e/2.
I*2 = 0.5 + e/2 (5-10)
In Figure 5-6 three experiments are shown located on an initial unit interval. Using equation (5-6), we can write the largest final interval of uncertainty I3 as
I3 = max [x2, x3 - x1, 1 - x2] (5-11)
Inspecting the above equation, it is seen that the value selected for x2 controls the value of I3. For example if x2 = 0.5, then 1 - x2 = 0.5, and I3 would have a value of 0.5, as long as the value of (x3 - x1) was less than or equal to 0.5. In fact, the value of 0.5 for x2 is the best in a minimax sense for the location of x2. Then the minimum value of I3 is 0.5, and x1 and x3 can be located at any position as long as their difference does not exceed 0.5. A convenient way to place the three points is equally spaced in the interval with a separation of 0.25, i.e., uniform search.
If the two minimax search plans with two and three experiments are compared, the final intervals are as follows:
I2* = 0.5 + e/2 (5-10)
I3* = 0.5 (5-12)
From these two equations we can see that placing one additional experiment reduces the final interval of uncertainty only by the amount of e/2. This is usually an insignificant interval reduction compared to the cost of placing another experiment. We will see that similar results will be obtained when n experiments are placed simultaneously.
| Simultaneous Search Methods(2) | top |
We will now extend the results to include k experiments placed simultaneously in an initial interval using the minimax principle. It will be necessary to consider the two cases of an odd and even number of experiments. It will be seen that only a small reduction in the final interval will be obtained with an additional experiment when going from an even number of experiments to an odd number. However, the spacing of an odd number of experiments uniformly in the interval will be attractive from the point-of-view of computational simplicity.
Beginning with the case of an odd number of experiments, it is convenient to use p pairs of experiments and have k = 2p + 1 total experiments. This is shown in Figure 5-7, where the initial interval is Io, and it contains x2p+1 as the last one of k experiments. The possible final intervals of uncertainty are indicated on the figure also; and they consist of (x2 - 0), (x3 - x1), (x4 - x2), ..., (x2p - x2p-2), (x2p+1 - x2p-1), (Io -x2p).
EDIT Figure 5-7. Minimax search plans for an odd and even number of experiments.
The following set of equations can be written that relate the intervals that contain the odd experimental points and the largest final interval of uncertainty Ik that is to be minimized.
i1 = x2 - 0 < Ik
i3 = x4 - x2 < Ik
i5 = x6 - x4 < Ik
. (5-13)
.
i2p-1 = x2p - x2p -2 < Ik
i2p+1 = Io - x2p < Ik
These (p + 1) inequalities can be added to give the following equation:
Io < (p + 1)Ik (5-14)
This equation can be written as:
To satisfy the minimax principle, the minimum value of Ik must be selected, and this requires the equality be used in equation (5-15), i.e.:
I*k = Io / (p+1) (5-16)
The optimal spacing
of experiments requires that the even ones be placed an equal distance
apart, i.e.:
x2h = h I*k for h = 1,2,...,p (5-17)
The odd experiments can be located between the even ones at any position, as long as they are no farther apart than I*k. Consequently, there is not a unique minimax search plan for an odd number of experiments. However, a computationally simple one is to distribute the experiments uniformly in the interval as given by the following equation.
xj = j I*k / 2 for j = 1,2,3,...,k (5-18)
or
xj = j Io / 2(p+1) for j = 1,2,...,k (5-19)
This procedure is called uniform search.
For the case of an even number of experiments, a unique search plan will be obtained, search by uniform pairs. In this case there will be p pairs of experiments and a total of 2p experiments. This is shown in Figure 5-7 also, where the initial interval is Io, and it contains x2p, the last one of 2p experiments. Also, the possible final intervals of uncertainty I2p are indicated in the figure and consist of (x2 - 0), (x3 - x1), ..., (x2p - x2p-2), (Io - x2p-1).
The following set of equations can be written that relate the intervals that contain the odd experimental points, as was done previously.
i1 = x2 - 0 < I2p
i2 = x4 - x2 < I2p (5-20)
.
.
i2p-1 = x2p - x2p-2 < I2p
These p inequalities can be added
to give the following equation.
x2p < p I2p (5-21)
The equation which includes the final interval Io involving the odd point, x2p-1 is:
i2p = Io - x2p-1 < I2p (5-22)
Adding equation (5-21) and (5-22) gives:
Io + x2p - x2p-1 < (p+1) I2p (5-23)
To satisfy the minimax principle, the minimum value of I2p must be selected. To have the minimum value of I2p, not only must the quality be selected, but the distance between the two experiments x2p and x2p-1 must be as small as possible. This means that x2p and x2p-1 must be separated by the resolution as shown in Figure 5-7. The resolution is eIo, and e is a fraction of the initial interval. Thus, equation (5-23) becomes:
Io + eIo = (p+1) I*2p (5-24)
Solving for I*2p gives:
I*2p = (1 + e) Io /(p + 1) (5-25)
which is comparable to equation (5-16) for the case of an odd number of experiments.
A unique search plan is obtained for an even number of experiments. For this search by uniform pairs, the even experiments are located throughout the interval according to equation (5-25) as:
x2h = h (1 + e) Io / (p + 1) for h = 1,2,3,...,p (5-26)
and the odd experiments are placed to the left of the even ones separated by a distance equal to the resolution, as shown below:
x2h-1 = x2h - eIo for h = 1,2,3,...,p (5-27)
Substituting for x2h gives a convenient formula to compute the location of the odd experiments, which is comparable to equations (5-26) for the even experiments.
x2h-1 = [h - (p + 1 - h)e] Io / (p + 1) for h = 1,2,3,...,p (5-28)
A comparison of the equations for the final intervals of uncertainty for an even number of experiments and one additional experiments is given by rewriting equations (5-25) for an even number and equation (5-16) for an odd number as:
Even: I*2p = Io / (p + 1) + eIo / (p + 1) (5-29)
Odd: I*2p+1 = Io / (p + 1) (5-30)
The placing of the additional experiment reduces the final interval by the amount of eIo /(p + 1). This normally would be a small number, and the additional experiment could involve significant expense. This must be weighed against the convenience of the use of uniform search, i.e., the odd minimax plan of distributing the experiments uniformly in the initial interval.
The following simple example illustrates the use of the results obtained for these minimax search plans.
Example 5-1
Search for the maximum of the following function using search by uniform pairs with four experiments and uniform search with five experiments. The initial interval is Io = 1.0, and the resolution is e = 0.05. Compare the lengths and locations of the final intervals of uncertainty. Also compare the maximum values obtained with the optimum computed using the classical theory of maxima and minima.
max: y = 3 + 6x - 4x2 on 0 < x < 1.0
For four simultaneous experiments their location is determined by equations (5-26) and (5-28), and for h = 1:
x2 = (1 + e) Io / (p + 1) = (1 + 0.05)(1) / (2 + 1) = 0.35
x1 = [1 - (2 + 1 - 1)0.05](1) / (2 + 1) = 0.30
and x1 and x2 are separated by the resolution eIo = 0.05. The values of x3 and x4 are computed similarly and are:
x3 = 0.65 x4 = 0.70
Evaluating the function gives:
y(0.30) = 4.44
y(0.35) = 4.60
y(0.65) = 5.21
y(0.70) = 5.24
and the length and the location of the final interval of uncertainty are:
I4* = 0.35 0.65 < x* < 1
For five simultaneous experiments, their location is determined by equation (5-19).
x1 = Io / 2(p + 1) = 1/2(2 + 1) = 1/6 for j = 1
The other values are computed similarly to give:
x2 = 1/3
x3 = 1/2
x4 = 2/3
x5 = 5/6
Evaluating the function gives:
y(1/6) = 3.89
y(1/3) = 4.56
y(1/2) = 5.00
y(2/3) = 5.2222
y(5/6) = 5.2222
and the length and location of the final interval of uncertainty are:
I5* = 1/3 2/3 < x* < 1
The difference in the final intervals of uncertainty between four and five experiments is 0.350 - 0.333 = 0.017, and this is equal to eIo/(p + 1) = 0.05(1)/3 = 0.017 from equations (5-29) and (5-30). Also using the classical theory of maxima and minima, the optimum is located at x* = 3/4 with a value of y(3/4) = 5.25, which is compared with y(0.70) = 5.24, the largest value for four experiments, and y(5/6) = 5.22, the largest value for five experiments.
The preceding simple example has illustrated the use of the equations for simultaneous search. A more detailed discussion of these methods has been given by Wilde and Beightler (2) and includes a mathematical elaboration of resolution, distinguishability, and scaling. The topic of fictitious points will be discussed subsequently associated with lattice search. Now we will move to the subject of sequential search methods, using the concepts that have been developed for simultaneous search methods.