5.7 Fibonacci Method 263
5.7 Fibonacci Method
As stated earlier, theFibonacci methodcan be used to find the minimum of a function
of one variable even if the function is not continuous. This method, like many other
elimination methods, has the following limitations:
1.The initial interval of uncertainty, in which the optimum lies, has to be known.
2.The function being optimized has to be unimodal in the initial interval of uncer-
tainty.
3.The exact optimum cannot be located in this method. Only an interval known as
thefinal interval of uncertaintywill be known. The final interval of uncertainty
can be made as small as desired by using more computations.
4.The number of function evaluations to be used in the search or the resolution
required has to be specified beforehand.
This method makes use of the sequence of Fibonacci numbers,{Fn} for placing the,
experiments. These numbers are defined as
F 0 =F 1 = 1
Fn=Fn− 1 +Fn− 2 , n= 2 , 3 , 4 ,...
which yield the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,.. ..
Procedure. LetL 0 be the initial interval of uncertainty defined bya≤x≤bandn
be the total number of experiments to be conducted. Define
L∗ 2 =
Fn− 2
Fn
L 0 (5.5)
and place the first two experiments at pointsx 1 andx 2 , which are located at a distance
ofL∗ 2 from each end ofL 0 .†This gives‡
x 1 =a+L∗ 2 =a+
Fn− 2
Fn
L 0
x 2 =b−L∗ 2 =b−
Fn− 2
Fn
L 0 =a+
Fn− 1
Fn
L 0
(5.6)
Discard part of the interval by using the unimodality assumption. Then there remains
a smaller interval of uncertaintyL 2 given by§
L 2 =L 0 −L∗ 2 =L 0
(
1 −
Fn− 2
Fn
)
=
Fn− 1
Fn
L 0 (5.7)
†If an experiment is located at a distance of (Fn− 2 /Fn)L 0 from one end, it will be at a distance of
(Fn− 1 /Fn)L 0 from the other end. ThusL∗ 2 = (Fn− 1 /Fn)L 0 will yield the same result as withL∗ 2 =
(Fn− 2 /Fn)L 0.
‡It can be seen that
L∗ 2 =
Fn− 2
Fn
L 0 ≤
1
2
L 0 for n≥ 2
§The symbolLjis used to denote the interval of uncertainty remaining after conductingjexperiments,
while the symbolL∗jis used to define the position of thejth experiment.
