Computer Aided Engineering Design

OPTIMIZATION 343

(c) Fibonacci and Golden Section Search
This method determines the maximum (or minimum) of a unimodal function that has only one
optimum in the search interval, xl≤x≤xu by evaluating the function at points placed as per the
Fibonacci sequence. Fibonacci numbers are related such that for two consecutive numbers F(n – 2)
andF(n– 1), the third is obtained by the relation

F(n) = F(n – 1) + F(n – 2), n = 2, 3, 4...

withF(0) = 1 and F(1) = 1. When using this search method, the final interval size ε may be specified
in advance. The number of evaluations N are computed such that F(N)≥ (xu – xl)ε. Thus, if xu – xl
= 1 and ε = 0.001, then (xu – xl)/ε = 1000. The Fibonacci number just greater than 1000 corresponds
toN = 16 (F(16) = 1597), that is, we would need to perform N= 16 evaluations to achieve the interval
size of 0.001.
With the number of iterations known, the interior points x 1 and x 2 both within the original
interval are placed such that x 1 = xl + g(N)(xu – xl) and x 2 = xu – g(N) (xu – xl), where g(N) is the
placement ratio defined as F(N – 2)/F(N). The function f (x) to be maximized is evaluated at the
two points which are compared. If f (x 1 )≥f (x 2 ), the upper limit xu is set to x 2 implying that the
search interval is reduced to [xl,x 2 ] and k (the iteration count with 0 initial value) is incremented
tok+ 1. For the subsequent iteration, assignments x 1 = xl + (F(N – k – 2)/F(N – k)) (xu – xl)
andx 2 = xu – (F(N – k – 2)/F(N – k)) (xu – xl) are performed. Otherwise, if f(x 1 ) < f(x 2 ), the
new interval is reduced to [x 1 ,xu] by setting xl = x 1 ,k is incremented by 1, and x 1 = xl + (F(N –
k – 2)/F(N – k)) (xu – xl) and x 2 = xu – (F(N – k – 2)/F(N – k)) (xu – xl) are assigned. The
procedure is continued until k=N – 1 and the optimal solution is taken as the midpoint of the final
interval.

f(x)

f(x 1 ) f(x^2 )

New search

interval

x

xl x 1 x 2 xu

Figure 12.5 Fibonacci and golden section search

The Fibonacci search method minimizes the maximum number of evaluations needed to reduce
the interval of uncertainty to within the prescribed length. For instance, an initial unit interval can
be reduced to 1/10946 (=0.00009136) with only 20 evaluations. For very large N, 1–g(N) approaches
the golden mean (0.618) and the method approaches the golden section search.

Example 12.3. Maximize 2 – x^2 using the Golden section and Fibonacci search method. We can
observe by inspection that the function is unimodal and that the optimum lies at x = 0. The following
tables show how the golden section and Fibonacci method determine this optimum. We choose the
interval as [–1, 6] and the number of function evaluations N as 20.