|
Chapter 6 | 
|
MULTIDIMENSIONAL SEARCH
Problems 6.1 to 6.10 | Problems 6.11 to 6.20 | Problems 6.21 to 6.25
problem6.1 | problem6.2 | problem6.3 | problem6.4 | problem6.5
problem6.6 | problem6.7 | problem6.8 | problem6.9 | problem6.10
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?
Solution:
a. The parametric representation of the line in the x1, x2, x3 and x4 hyperplane is:
xj = aj + a(bj - aj) for j = 1, 2, 3, 4.
where aj and bj are as follows for the two points given in the problem
a1 = 1 b1 = -5
a2 = -1 b2 = -1
a3 = 0 b3 = 3
a4 = 2 b4 = 1
Substituting into the equation for a line in space gives:
x1 = 1 - 6a a = 0 generates a
x2 = -1 a = 1 generates b
x3 = 3a
x4 = 2 - a
A Fibonacci search is performed with as the independent variable, and the initial interval of uncertainty is 0 < a < 1.
Using equation (5-41) with Î = 0 and n = 5 to compute the final interval of uncertainty gives:
The location of the first two experiments are obtained using equations (5-43) and (5-44).
a1 = x1 = An-1In = (3)(0.125) = 0.375
a2 = x2 = AnIn = (5)(0.125) = 0.625
The coordinates of the first two point are obtained using a1 = 0.375 and a2 = 0.625
x1,1 = 1 - 6(0.375) = -1.25 x1,2 = 1- 6(0.625) = -2.75
x2,1 = -1 x2,2 = -1
x3,1 = 3(0.375) = 1.125 x3,2 = 3(0.625) = 1.875
x4,1 = 2 - 0.375 = 1.625 x4,2 = 2 - (0.625) = 1.375
x1 (-1.25, -1, 1.125, 1.625) x2 (-2.75, -1, 1.875,1.375)
b. To find the final interval of uncertainty on axis x1, use In = Io/An+1 = Io/8.
Io = 1 - (-5) = 6
I5 = 6/8 = 0.75
The final intervals of uncertainty on the other axes are computed the same way.
6-2(10). In the following 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 countour tangent hyperplane passing through (0, 1, -1, 3).
Solution:
a. The line of steep ascent is given by equation (6-7).
x = xk + a Ñy(xk)
The partial derivatives are calculated as follows:
Substituting into the equation for the gradient line gives:
x1 = 2a
x2 = 1 - a
x3 = -1 + a
x4 = 3
b. The contour tangent hyperplane is given by the following equation.
Ñy (xo)(x - xo) = 0
Substituting into the above equation gives:
2(x1 - 0) - (x2 - 1) + (x3 + 1) = 0
Simplifying gives the equation for the contour tangent hyperplane
2x1 - x2 + x3 + 2 = 0
6-3(17). Using the method of gradient partan to find the minimum of the following function starting at (2,1,3) y = x12 + 3x22 + 5x32
Solution:
It is convenient to determine the values of the partial derivatives in terms of a general point a(a1, a2, a3).
Gradient partan consists of a series of line searches along the gradient line and an acceleration line as given by equations (6-25) and (6-26)
xk+1 = xk + a Ñy(xk) xk+1 = xk-3 + a(xk - xk-3)
At a point a, the gradient line can be represented by
x1 = a1 + 2a1a
x2 = a2 + 6a2 a
x3 = a2 + 10a3 a
Then starting at xo(2, 1, 3) the next point x2 can be located by a gradient search as follows. Evaluate the gradient line at xo to give x1 = 2 + 4a, x2 = 1 + 6a; and x3 = 3 + 30a. Substituting into the cost function reduces it to a function with one independent variable.
y = (2 + 4a)2 + 3(1 + 6a)2 + 5(3 + 30a)2
Differentiating y with respect to and setting the result equal to zero gives the optimum value of a as shown below.
dy/da = 2(2 + 4a)(4) + 6(1 + 6a)(6) + 10(3 + 30a)(30) = 0
a = -0.10294
This value of a is used to calculate x2.
x1,2 = 2 + 4(-0.10294) = 1.5882
x2,2 = 1 = 6(-0.10294) = 0.3824
x3,2 = 3 + 30(-0.10294) = -0.0882
A gradient search is used to locate point x3 according to the table given on page 229 of the text. The gradient line is determined using x2 = a as follows:
x1 = 1.5882 + 2(1.5882)a = 1.5882 + 3.1764a
x2 = 0.3824 + 6(0.3824)a = 0.3824 + 2.2944a
x3 = -0.0882 + 10(-0.0882)a = -0.0882 - 0.8820a
The search for the minimum along the gradient line to locate point x3 is performed as follows:
y = (1.5882 + 3.1764a)2 + 3(0.3824 + 2.294a)2 + 5(-0.0882-0.8820a)2
dy/da = 16.079 + 59.544a = 0
a = -0.2700
Then a is used to calculate x3.
x1,3 = 1.5882 + 6.352(-0.2700) = 0.73057
x2,3 = 0.3823 + 2.298(-0.2700) = - 0.23709
x3,3 = -0.0882 - 0.882(-0.2700) = 0.14994
Next an acceleration is performed from xo through x3 to locate the minimum of y at x4.
x4 = xo + a(x3 - xo)
and
x1 = 2 + a(-0.73057 - 2) = 2 - 1.2694a
x2 = 1 + a(-0.23709 - 1) = 1 - 1.23709a
x3 = 3 + a(0.14994 - 3) = 3 - 2.8501v
The search for the minimum along the acceleration line to locate point x4 is performed as follows
y = (2 - 1.269a)2 + 3(1 - 1.237a)2 + 5(3 - 2.8501a)2
dy/da = -98.003 + 93.634a = 0
a = 1.0467
Then a is used to calculate x4.
x1,4 = 2 - 1.2694(1.0467) = 0.67138
x2,4 = 1 - 1.2370(1.0467) = - 0.29471
x3,4 = 3 - 2.8501(1.0467) = 0.01693
A gradient search is used to locate x5, and the gradient line at x4 is:
x1 = 0.67138 + 2(0.67138)a = 0.67138 + 1.3428a
x2 = - 0.29471 + 6(-0.29471)a = -0.29471 - 1.7683a
x3 = 0.01693 + 10(0.01693)a = 0.01693 + 0.1693a
The search along the gradient line to locate point x5 is as follows.
y = (0.67138 + 1.3428a)2 + 3(-0.29471 - 1.7683a)2 + 5(0.01693 + 1.1693a)2
dy/da = 4.9585 + 22.654a = 0
a = -0.2189
Then a is used to calculate x5.
x1,5 = 0.67138 + 1.3428(-0.2189) = 0.3774
x2,5 = -0.29471 - 1.7683(-0.2189) = -0.09237
x3,5 = 0.01693 + 0.169(-0.2189) = -0.02006
Next, an acceleration is performed from x2 through x5 to locate the minimum of y at x6.
x6 = x2 + a(x5 - x2)
x1 = 1.5882 + a(0.3774 - 1.5882) = 1.5882 - 1.2108a
x2 = 0.3824 + a(-0.09237 - 0.3824) = 0.3824 - 0.2900a
x3 = -0.0882 + a(-0.02006 + 0.0882) = -0.0882 + 0.06814a
A search along the acceleration line for the minimum at x6 is performed as follows:
y = (1.5882 - 1.2108a)2 + 3(0.3824 - 0.2900a)2 + 5(-0.0882 + 0.06814a)2
dy/da = -4.5655 + 3.4831a = 0
a = 1.3108 2
Then is used to compute point x6.
x1 = 1.5882 - 1.2108(1.3108) = 0.0011
x2 = 0.3824 - 0.2900(1.3108) = -0.0023
x3 = -0.0882 + 0.06814(1.3108) = -0.0011
For a quadratic function with three independent variables, there is convergence to the minimum at x6. (quadratic termination property). The computed minimum of (0.001, 0.002, 0.001), is a reasonable approximation to the exact minimum of (0, 0, 0).
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 (½,½). Make local explorations and accelerations (pattern moves) to obtain the points through b5.
Solution:
a. Draw the contours of the function:
y = x1x2
in the region 0 < x1 < 10 and 0 < x2 < 10 for values of y = 20, 40, 60, 80. Some values of x1 and x2 are computed for the specified values of y and these serve as the basis for drawing the curves shown on page 6-12.
b. Apply Pattern Search to move toward the maximum starting at point (4,4) with a step size of d (½,½).
b1 = (4,4) y(b1) = (4)(4) = 16
Make local explorations about (4,4) as shown below:
t11 = (4½,4) y(t11) = (4½)(4) = 18
t12 = (4½,4½) y(t12) = (4½)(4½) = 20¼
b2 = (4½,4½) y(b2) = 20¼
A pattern move to t20 is made as shown below:
t20 = b1 + 2(b2 - b1) = b2 + (b2 - b1)
t20,1 = 4 + 2(4½ - 4) = 5
t20,2 = 4 + 2(4½ - 4) = 5
t20 = (5,5) y(t20) = (5)(5) = 25
and y(t20) > y(b2) so local exploration is conducted with
t21 = (5½,5) y(t21) = (5½)(5) = 27½
t22 = (5½,5½) y(t22) = (5½)(5½) = 30¼
b3 = (5½,5½) y(b3) = 20¼
The results of this move are shown on the diagram on page 6-12. A pattern move to t30 is made as shown below:
t30 = b2 + 2(b3 - b2) = b3 + (b3 - b2)
t30,1 = 4½ + 2(5½ - 4½) = 6½
t30,2 = 4½ + 2(5½ - 4½) = 6½
t30 = (6½,6½) y(t30) = (6½)(6½) = 42¼
and y(t30) > y(b3) so local exploration is continued with
t31 = (7,6½) y(t31) = (7)(6½) = 45½
t32 = (7,7) y(t32) = (7)(7) = 49
b4 = (7,7) y(b4) = 49
The results of this move are shown on the diagram on page 6-12. A pattern move to t40 is made as shown below.
t40 = b3 + 2(b4 - b3) = b4 + (b4 - b3)
t40,1 = 5½ + 2(7 - 5½) = 8½
t40,2 = 5½ + 2(7 - 5½) = 8½
t40 = (8½,8½) y(t40) = (8½)(8½) = 72¼
and y(t40) > y(b4) so local exploration is to be conducted.
t41 = (9,8½) y(t41) = (9)(8½) = 76½
t42 = (9,9) y(t42) = (9)(9) = 81
b5 = (9,9) y(b5) = 81
The results of this move are shown on the diagram in Soln 6-4a. A pattern move to t50 is made as shown below.
t50 = b4 + 2(b5 - b4)
t50,1 = 7 + 2(9 - 7) = 11
t50,2 = 7 + 2(9 - 7) = 11
The value of t50 is out of bound. At this point a modification must be made in the unconstrained search technique to insure that it remains in bounds, i.e. in the feasible region. Penalty functions or Lagrange multipliers have been used for this purpose.
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.
Solution:
The trajectories of gradient partan and sectioning are shown on the diagram in Soln 6-5a and pattern search and gradient search are shown on the diagram in Soln 6-5b. As shown on the first diagram gradient partan moves rapidly to optimum while sectioning in confounded by the resolution ridge. As shown on the second diagram pattern search moves relatively rapidly toward the optimum and gradient search moves in a typical zig-zag pattern.
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 again if necessary to have pattern search continue. Reduce the step size by one-half to have the search continue. Reduce the step size by one-half again if necessary to have pattern search continue. Give a brief discussion of the performance of these methods on this function.
Solution:
The trajectory of gradient partan is shown on the diagram in Soln 6-6a, Powell's method on the diagram in Soln 6-6b, and pattern search on the diagram in Soln 6-6c.
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 insure convergence to a minimum (maximum), the value of dy(x)/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 algorithms.
x = xk + a(xk+1 - xk)
Explain why this restriction is required for convergence to a local minimum (maximum).
Solution:
Equation (6-12), the Newton's method algorithm is:
x = xk - H-1 Ñy(xk)
The iterative procedure to move toward the optimum is:
1. Select a starting point xo
2. Evaluate the partial derivative at this point.
¶y(xo)/¶xi and ¶ 2y(xo)/¶xi¶xj for i =1,2,...,n and j =1,2...,n.
3. Compute the inverse of the Hessian matrix H-1 and the gradient, Ñy at xo. Then use equation (6-12) to determine the minimum of the quadratic approximation, x.
4. Use the minimum of the quadratic approximation as the next point if it gives a lower value of the cost function. Then repeat step 2, 3 and 4. If the cost function increased, go to step 5.
5. As the optimum is approached, oscillations can occur with the value of the objective function. To be sure the optimum is approached let xk+1 = xk + a(xk+1 - xk) where a is the parameter of the line between the newly calculated optimum at xk+1 and the previously calculated optimum of the quadratic approximation, xk. The objective function y(x), not the quadratic approximation, can be written as a function of a as y[xk + a(xk+1 - xk)]. In a search for the minimum along the line between xk and xk+1, dy/da must be negative to insure that y(xk+1) < y(xk). Therefore, select a value of a where 0 < a < 1 such that y[xk + a(xk+1 - xk)] < y(xk) to compute the next point for the quadratic approximation. Then return to step 2.
6. A convergence test is incorporated in the logic to stop the computation, e.g.|yk+1 - yk| < Î, a small specified value.
6-8. Search for the minimum of the following function using gradient search starting at point xo(1,1,1)
y = x12 + x22 + x32
Solution:
The equation for the gradient line is equation (6-25)
xk+1 = xk + a Ñy(xk)
Evaluating partial derivatives gives:
¶y/¶x1 = 2x1
¶y/¶x2 = 2x2
¶y/¶x3 = 2x3
The gradient line at (1, 1, 1) is:
x1 = 1 + 2a
x2 = 1 + 2a
x3 = 1 + 2v
Substituting into the cost function gives:
y = (1 + 2a)2 + (1 + 2a)2 + (1 + 2a)2 = 3(1 + 2a)2
Locating the minimum along the gradient line gives:
dy/da = 6(1 + 2a)(2) = 0
a = -1/2
Calculating x1 using the value of a gives:
x1 = 1 - 2(1/2) = 0
x2 = 1 - 2(1/2) = 0
x3 = 1 - 2(1/2) = 0
The components of x1 are all zero, and referring to the equations for the partial derivatives it is seen that they are zero also at x1. Consequently, there will be no movement from x1 if another gradient search is performed; and the minimum has been located.
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 interacting (mixed partial derivative) terms for simplicity. Then differentiate the truncated Taylor series equation with respect to x1, x2 and x3 to compute the optimum of the quadratic approximation, x*1, x*2 and x*3. Then apply these results to minimize the function of the problem. Compare the effort required for one iteration of the linear algorithm to one iteration to the quadratic algorithm.
Solution:
The Taylor series expansion is:
The partial derivatives are evaluated at xo, and the third and higher order terms have been neglected. Also, neglecting the interacting term i.e. the one with k ¹ j and differentiating partially with respect to x1, x2 and x3 gives:
Solving these equations for x1, x2 and x3 gives:
These equations are an algorithm for optimization. Applying it to the equation given in Problem 6-8, the partial derivatives needed are:
Evaluating the partial derivatives at the starting point (1,1,1) and substituting the algorithm gives:
x1 = 1 - 2/2 = 0
x2 = 1 - 2/2 = 0
x3 = 1 - 2/2 = 0
The optimum has been reached in one application of the algorithm.
The quadratic algorithm requires the additional effort of evaluating the second partial derivatives in addition to the first partial derivatives compared to the linear 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.
Solution:
a. For the figure shown, in Soln 6-10 the optimum lies at C = 95 and F = 10. For one reactor, the profit function is:
y = 150 - 24(C - 95)2 - 6(F - 10)2
The profit function for the three reactors is the same for each reactor.
For the constraint equations:
DCi = aFi + b for i = 1, 2, 3.
and
DCi = 2 Fi = 5
DCi = 4 Fi = 20
Solving for a and b:
20a + b = 4 a = 2/15
5a + b = 2 b = 1 1/3
and
DCi = 2/15 Fi + 4/3
Applying the equation to each reactor gives:
Reactor 1: DC1 = C2 - C1 = 2/15 F1 + 4/3
Reactor 2: DC2 = C3 - C2 = 2/15 F2 + 4/3
Reactor 3: DC3 = CF - C3 = 2/15 F3 + 4/3
where CF = 98, the initial catalyst concentration. The problem becomes:
subject to: C1 - C2 + 2/15F1 + 4/3 = 0
C2 - C3 + 2/15F2 + 4/3 = 0
C3 + 2/15F3 - 96 2/3 = 0
C1 - 88 > 0
where the independent variables are C1, C2, C3, F1, F2 and F3.
b. Penalty mixed function form is:
The first terms are the profit function. The term with 1/r½ as a coefficient contains the equality constraints. The term with r as a coefficient is the inequality constraint. Negative signs are required on the terms with the constraints because the function is being maximized. To obtain a solution, a value of r is selected and then a search technique is used to locate a point near the maximum. Then a smaller value of r is used and the search technique continues from the point near the maximum to one that is close to the maximum. Smaller and smaller values of r are used such that the terms containing the constraint equations become insignificantly small compared to the values of the profit function at the optimum; and the constraint equations are satisfied, i.e.:
