The Fibonacci Method for Function Optimization
Fibonacci method
As stated earlier, the
Fibonacci method
can be used to find
the minimum of a function of one variable even if the
function is not continuous. The limitations of the method
are:
•
The initial interval of uncertainty, in which the optimum
lies, has to be known.
•
The function being optimized has to be unimodal in the
initial interval of uncertainty.
Fibonacci method
The limitations of the method (cont’d):
•
The exact optimum cannot be located in this method. Only
an interval known as the final interval of uncertainty will
be known. The final interval of uncertainty can be made as
small as desired by using more computations.
•
The number of function evaluations to be used in the
search or the resolution required has to be specified before
hand.
Fibonacci method
This method makes use of the sequence of Fibonacci
numbers, {F
n
}, for placing the experiments. These numbers
are defined as:
which yield the sequence 1,1,2,3,5,8,13,21,34,55,89,...
Fibonacci method
Procedure:
Let L
0
be the initial interval of uncertainty defined by
a
x
b
and
n
be the total number of experiments to be
conducted. Define
and place the first two experiments at points
x
1
and
x
2
,
which are located at a distance of L
2
*
from each end of L
0
.
Fibonacci method
Procedure:
This gives
Discard part of the interval by using the unimodality
assumption. Then there remains a smaller interval of
uncertainty
L
2
given by:
Fibonacci method
Procedure:
The only experiment left in will be at a distance of
from one end and
from the other end. Now place the third experiment in the interval
L
2
so that the current two experiments are located at a distance of:
Fibonacci method
Procedure:
•
This process of discarding a certain interval and placing a new
experiment in the remaining interval can be continued, so that the
location of the
j
th experiment and the interval of uncertainty at the end
of
j
experiments are, respectively, given by:
Fibonacci method
Procedure:
•
The ratio of the interval of uncertainty remaining after conducting
j
of the
n
predetermined experiments to the initial interval of
uncertainty becomes:
and for
j = n
, we obtain
Fibonacci method
•
The ratio
L
n
/L
0
will permit us to determine
n,
the required number
of experiments, to achieve any desired accuracy in locating the
optimum point.Table gives the reduction ratio in the interval of
uncertainty obtainable for different number of experiments.
Fibonacci method
Position of the final experiment:
•
In this method, the last experiment has to be placed with some
care. Equation
gives
•
Thus, after conducting
n
-1 experiments and discarding the
appropriate interval in each step, the remaining interval will
contain one experiment precisely at its middle point.
Fibonacci method
Position of the final experiment:
•
In this method, the last experiment has to be placed with some
care. Equation
gives
•
Thus, after conducting
n
-1 experiments and discarding the
appropriate interval in each step, the remaining interval will
contain one experiment precisely at its middle point.
Fibonacci method
Position of the final experiment:
•
However, the final experiment, namely, the
n
th
experiment, is also to be placed at the center of the
present interval of uncertainty.
•
That is, the position of the
n
th experiment will be the
same as that of (
n
-1)th experiment, and this is true for
whatever value we choose for
n.
•
Since no new information can be gained by placing the
n
th
experiment exactly at the same location as that of
the
(
n-1
)th
experiment, we place the
n
th
experiment
very close to the remaining valid experiment, as in the
case of the dichotomous search method.
Fibonacci method
Example:
Minimize
f(x)=0.65-
[
0.75/
(
1+x
2
)]
-0.65 x tan
-1
(
1/x
) in the interval [0,3]
by the Fibonacci method using
n=6
.
Solution:
Here
n=6
and
L
0
=3.0,
which yield:
Thus, the positions of the first two experiments are given by
x
1
=
1.153846
and
x
2
=
3.0-1.153846=1.846154 with
f
1
=f
(
x
1
)
=-
0.207270 and
f
2
=f
(
x
2
)=-0.115843
.
Since
f
1
is less than
f
2
,
we
can delete the interval [
x
2
,
3] by using the unimodality
assumption.
Fibonacci method
Solution:
Fibonacci method
Solution:
The third experiment is placed at
x
3
=
0
+
(
x
2
-x
1
)=1.846154-
1.153846=0.692308, with the corresponding function value of
f
3
=-
0.291364. Since
f
1
is greater than
f
3
, we can delete the interval [
x
1
,x
2
]
Fibonacci method
Solution:
The next experiment is located at
x
4
=
0
+
(
x
1
-x
3
)=1.153846-
0.692308=0.461538, with
f
4
=-0.309811. Noting that
f
4
is less than
f
3
, we
can delete the interval [
x
3
,x
1
]
Fibonacci method
Solution:
The location of the next experiment can be obtained as
x
5
=
0
+
(
x
3
-
x
4
)=0.692308-0.461538=0.230770, with the corresponding objective
function value of
f
5
=-0.263678. Since
f
4
is less than
f
3
, we can delete the
interval [
0,x
5
]
Fibonacci method
Solution:
The final experiment is positioned at
x
6
=x
5
+
(
x
3
-x
4
)=0.230770+(0.692308-
0.461538)=0.461540 with
f
6
=-0.309810. (Note that, theoretically, the
value of
x
6
should be same as that of
x
4
;
however,it is slightly different
from
x
4
due to the round off error).
Since
f
6
>
f
4
, we delete the interval
[
x
6
,
x
3
] and obtain the final interval of uncertainty as
L
6
= [
x
5
,
x
6
]=[0.230770,0.461540].
Fibonacci method
Solution:
The ratio of the final to the initial interval of uncertainty is
This value can be compared with
which states that if
n
experiments
(n=6)
are planned, a resolution
no finer than 1/
F
n
=
1/
F
6
=1/13=
0.076923 can be expected from
the method.
The Fibonacci method offers a systematic approach to finding the minimum of a function even if it's not continuous. By utilizing a sequence of Fibonacci numbers, this method helps in narrowing down the interval of uncertainty to determine the optimal solution through a series of experiments. Despite some limitations, including known initial uncertainty intervals and unimodality assumptions, this method provides a structured process for optimization tasks.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Fibonacci method As stated earlier, the Fibonacci method can be used to find the minimum of a function of one variable even if the function is not continuous. The limitations of the method are: The initial interval of uncertainty, in which the optimum lies, has to be known. The function being optimized has to be unimodal in the initial interval of uncertainty.
Fibonacci method The limitations of the method (cont d): The exact optimum cannot be located in this method. Only an interval known as the final interval of uncertainty will be known. The final interval of uncertainty can be made as small as desired by using more computations. The number of function evaluations to be used in the search or the resolution required has to be specified before hand.
Fibonacci method This method makes use of the sequence of Fibonacci numbers, {Fn}, for placing the experiments. These numbers are defined as: = = 1 + F F 0 1 = = , , 4 , 3 , 2 F F F n 1 2 n n n which yield the sequence 1,1,2,3,5,8,13,21,34,55,89,...
Fibonacci method Procedure: Let L0be the initial interval of uncertainty defined by a x b and n be the total number of experiments to be conducted. Define F L n = n * 2 2 L 0 F and place the first two experiments at points x1and x2, which are located at a distance of L2*from each end of L0.
Fibonacci method Procedure: This gives F = + = + * 2 2 n x a L a L 1 0 F n F F = = = + * 2 2 1 n n x b L b L a L 2 0 0 F F n n Discard part of the interval by using the unimodality assumption. Then there remains a smaller interval of uncertainty L2given by: F F = = = * 2 2 1 n n 1 L L L L L 2 0 0 0 F F n n
Fibonacci method Procedure: The only experiment left in will be at a distance of F F = = * 2 2 2 n n L L L 0 2 F F 1 n n from one end and F F = = * 2 3 3 n n L L L L 2 0 2 F F 1 n n from the other end. Now place the third experiment in the interval L2so that the current two experiments are located at a distance of: F L F n n F = = * 3 3 3 n n L L 0 2 F 1
Fibonacci method Procedure: This process of discarding a certain interval and placing a new experiment in the remaining interval can be continued, so that the location of the jth experiment and the interval of uncertainty at the end of j experiments are, respectively, given by: F n j = * L L 1 j j F ) 2 ( n j F ) 1 ( n j = L L 0 j F n
Fibonacci method Procedure: The ratio of the interval of uncertainty remaining after conducting j of the n predetermined experiments to the initial interval of uncertainty becomes: L F ) 1 ( j n j = L F 0 n and for j = n, we obtain 1 L F = = 1 n L F F 0 n n
Fibonacci method The ratio Ln/L0will permit us to determine n, the required number of experiments, to achieve any desired accuracy in locating the optimum point.Table gives the reduction ratio in the interval of uncertainty obtainable for different number of experiments.
Fibonacci method Position of the final experiment: In this method, the last experiment has to be placed with some care. Equation F L n j = * L 1 j j F ) 2 ( n j gives * n 1 L F = = 0 for all n 2 L F 1 2 n Thus, after conducting n-1 experiments and discarding the appropriate interval in each step, the remaining interval will contain one experiment precisely at its middle point.
Fibonacci method Position of the final experiment: In this method, the last experiment has to be placed with some care. Equation F L n j = * L 1 j j F ) 2 ( n j gives * n 1 L F = = 0 for all n 2 L F 1 2 n Thus, after conducting n-1 experiments and discarding the appropriate interval in each step, the remaining interval will contain one experiment precisely at its middle point.
Fibonacci method Position of the final experiment: However, the final experiment, namely, the nth experiment, is also to be placed at the center of the present interval of uncertainty. That is, the position of the nth experiment will be the same as that of ( n-1)th experiment, and this is true for whatever value we choose for n. Since no new information can be gained by placing the nth experiment exactly at the same location as that of the (n-1)th experiment, we place the nth experiment very close to the remaining valid experiment, as in the case of the dichotomous search method.
Fibonacci method Example: Minimize f(x)=0.65-[0.75/(1+x2)]-0.65 x tan-1(1/x) in the interval [0,3] by the Fibonacci method using n=6. Solution: Here n=6 and L0=3.0, which yield: ) 0 . 3 ( 13 F n 5 F = = 153846 . 1 = L 2 * n L 2 0 Thus, the positions of the first two experiments are given by x1=1.153846 and x2=3.0-1.153846=1.846154 with f1=f(x1)=- 0.207270 and f2=f(x2)=-0.115843. Since f1is less than f2, we can delete the interval [x2,3] by using the unimodality assumption.
Fibonacci method Solution:
Fibonacci method Solution: The third experiment is placed at x3=0+ (x2-x1)=1.846154- 1.153846=0.692308, with the corresponding function value of f3=- 0.291364. Since f1is greater than f3, we can delete the interval [x1,x2]
Fibonacci method Solution: The next experiment is located at x4=0+ (x1-x3)=1.153846- 0.692308=0.461538, with f4=-0.309811. Noting that f4is less than f3, we can delete the interval [x3,x1]
Fibonacci method Solution: The location of the next experiment can be obtained as x5=0+ (x3- x4)=0.692308-0.461538=0.230770, with the corresponding objective function value of f5=-0.263678. Since f4is less than f3, we can delete the interval [0,x5]
Fibonacci method Solution: The final experiment is positioned at x6=x5+ (x3-x4)=0.230770+(0.692308- 0.461538)=0.461540 with f6=-0.309810. (Note that, theoretically, the value of x6should be same as that of x4; however,it is slightly different from x4due to the round off error). Since f6 > f4, we delete the interval [x6, x3] and obtain the final interval of uncertainty as L6= [x5, x6]=[0.230770,0.461540].
Fibonacci method Solution: The ratio of the final to the initial interval of uncertainty is 230770 . 0 . 0 461540 L = = 6 076923 . 0 0 . 3 L 0 This value can be compared with 1 L F = = 1 n L F F 0 n n which states that if n experiments (n=6) are planned, a resolution no finer than 1/Fn= 1/F6=1/13=0.076923 can be expected from the method.
