Slide 1:Topic 3: Optimization Methods for Unconstrained Functions of Single Variable In this topic, we will cover some of the most widely used search methods. Starting from a point that is not optimal, we need to find the optimal solution. All the search methods are iterative; i.e. we apply certain steps repeatedly until we reach the optimum.


Slide 2:REGION-ELIMINATION METHODS Region-elimination methods are search methods that eliminate successively subintervals so as to reduce the remaining interval of search. All the methods require the function to be unimodal at least in the search interval.


Slide 4:Using the theorem, we can develop a search in which the optimum is found by recursively eliminating sections of the initial bounded interval. When the remaining subinterval is reduced to a sufficiently small length, the search is terminated. These methods are put together in four groups: zero-order, interpolation, first-order, and second-order. Results


Slide 5:Interval Refinement Phase Fibonacci Method (see the handouts) The Fibonacci method is best used when the interval containing the minimum (the interval of uncertainty) is to be reduced to a given length in the least number of function evaluations. The Fibonacci numbers F0, F1, F2, …, Fn are generated using the sequence F0 = 1 F1 = 1 Fi = Fi-1 + Fi-2 i = 2 to n


Slide 6:Consider the starting interval of uncertainty 1-4 in the figure. Introduce two points inside the interval, points 2 and 3. It is desirable that points 2 and 3 be placed symmetrically with respect to the center of the interval. If f2 f3 (case 2) then 2-4 is the new interval of uncertainty.


Slide 7:If case 1 occurs, let us rename points 1 and 3 as 4 and 1, respectively; if case 2 occurs, let us rename points 2 and 3 as 1 and 2, respectively. We now seek to introduce a new point 3 and be able to reduce the interval of certainty further. This requires that the new point 3 be located such that length 1-3 is the same as length 4-2. Assume that the original interval is of length I1 and the final interval after n - 1 interval reductions is In.


Slide 9:Clearly the intervals are related in the following way: I1 = I2 + I3 I2 = I3 + I4 Ij = Ij+1 + Ij+2 In-2 = In-1 + In In-1 = 2 In


Slide 10:By proceeding in the reverse order and expressing each interval in terms of In: In-1 = 2 In In-2 = In-1 + In = 3 In In-3 = In-2 + In-1 = 5 In In-4 = In-3 + In-2 = 8 In etc The coefficients 2, 3, 5,… are the Fibonacci numbers.


Slide 11:Using the Fibonacci numbers, we can write In-j = Fj+1 In j = 1, 2, …, n-1 For j = n-1 and n-2, I1 = Fn In I2 = Fn-1 In The length of the final interval is given by Given I1, I2 is computed as


Slide 12:Now that we know I1 and I2, we can find I3 = I1 – I2. I4, I5, … are computed in a similar manner.


Slide 13:Fibonacci Algorithm Start with the interval [x1, x4]. Find n such that  > 1/Fn, for a given accuracy level . Set i = 1. Set  = Fn-1 / Fn. Let x2 =  x1 + (1- ) x4. Evaluate f2. Let x3 =  x4 + (1- ) x1. Evaluate f3. Compare f2 and f3: If f2 f3, set x1 = x2, x2 = x3, and f2 = f3. Go to step 7. Let i = i + 1. If i = n, stop. Set  =Fn-i /Fn+1-i and go to step 5.


Slide 14:Example See the example and the solution in the handout.


Slide 15:Example Minimize f(x) = (100 – x)2 over 60 ≤ x ≤ 150. Apply Fibonacci method for n = 5. Solution Set  = F4 / F5 = 0.625. Set i = 1 Set x2 =  (60) + (1- ) (150) = 93.75, f2 = 39.1. Set x3 =  (150) + (1- ) (60) = 116.25, f3 = 264.1. Since f2 < f3, set x4 = 60 and x1 = 116.25. Set i = 2 (< 5). Set  = F3 / F4 = 0.6 Set x3 =  (60) + (1- ) (116.25) = 82.5, f3 = 306.25.


Slide 16:The rest of the computations are shown in the following table. The interval of uncertainty is reduced to [93.75, 116.25].


Slide 17:Example See the example and the solution in the handout.


Slide 18:Golden Section Method (see the handouts) With the golden section search, the interval reduction strategy is independent of the number of trials. Just like the Fibonacci method, this method maintains a uniform reduction strategy: Define  as


Slide 19:From this, we can write I2 =  I1 and I3 =  I2 = 2 I1 We have now 2 +  - 1 =0 The positive solution of this equation is This number is referred to as the golden section ratio. The golden section method is the limiting form of Fibonacci method when n = ∞.


Slide 20:The final interval In can be expresses in terms of I1: From this relationship, we can write which is the number of intervals required to go from the initial interval I1 to the final desired interval In.


Slide 21:Golden Section Algorithm


Slide 22:Example Minimize f(x) = (100 – x)2 for x1 = 60, x4 = 130, and =15. Solution


Slide 23:The rest of the calculations are summarized in the table below.


Slide 24:Polynomial Approximation Region elimination methods require only the function to be unimodal (whether continuous, discontinuous, discrete). They involve the comparison of function values, no attempt to involve the magnitude of the difference. The methods discussed in this section take into account the relative magnitudes of the function values. But, they require the function to be sufficiently smooth. The basic idea is that a smooth function can be approximated by a polynomial which is used to predict the location of the optimum.


Slide 25:Quadratic Estimation We approximate the function by a quadratic (second order) polynomial. Given three points (x1, f(x1)), (x2, f(x2)), and (x3, f(x3)), determine a0, a1, and a2 such that q(x) = a0 + a1(x-x1) + a2(x-x1)(x-x2) passes through these points. The values of the constants are


Slide 26:The minimum of q(x) is found by setting q'(x) = 0 yielding:


Slide 27:Example See the solution in the book.


Slide 28:Successive Quadratic Estimation Method


Slide 29:Successive Quadratic Estimation Method (simplified)


Slide 30:Example See the example and the solution in the book.


Slide 31:METHODS REQUIRING DERIVATIVES If the function being optimized is differentiable, more efficient methods can be developed. The methods in this section seek to estimate the stationary points of the function, i.e., estimate z such that Thus, we seek to estimate the zero of the first derivative.


Slide 32:Newton-Raphson Method This method requires the function to be twice differentiable. The method works by approximating the first derivative by a linear function and the zero of the linear function is sought. Given xk, the linear approximation of f '(x) at xk is Set this equation to zero and solve for xk+1:


Slide 33:Example See the example and the solution in the book.


Slide 34:Bisection Method It is a region-elimination method. It requires the computation of a single point inside the interval. The interval is reduced by half in each application of the method.


Slide 35:Steps of the method:


Slide 36:Example Solution The interval of uncertainty is reduced to [1.5625, 1.625].