Module for the Fibonacci Search
An approach for finding the minimum of in a given interval is to evaluate the function many times and search for a local minimum. To reduce the number of function evaluations it is important to have a good strategy for determining where is to be evaluated. Two efficient bracketing methods are the golden ratio and Fibonacci searches. To use either bracketing method for finding the minimum of , a special condition must be met to ensure that there is a proper minimum in the given interval.
unimodal on , if
there exists a unique number such
is decreasing on ,
is increasing on .
In the golden ratio search two function evaluations are made at the first iteration and then only one function evaluation is made for each subsequent iteration. The value of remains constant on each subinterval and the search is terminated at the subinterval, provided that or where are the predefined tolerances. The Fibonacci search method differs from the golden ratio method in that the value of is not constant on each subinterval. Additionally, the number of subintervals (iterations) is predetermined and based on the specified tolerances.
search is based on the sequence of Fibonacci
numbers which are defined by the
Thus the Fibonacci numbers are
Exploration for Fibonacci Numbers
Assume we are given a function that is unimodal on the interval . As in the golden ratio search a value is selected so that both of the interior points will be used in the next subinterval and there will be only one new function evaluation.
If , then
the minimum must occur in the subinterval ,
and we replace
continue the search in the new subinterval . If ,
then the minimum must occur in the subinterval ,
and we replace and and
continue the search in the new subinterval . These
choices are shown in Figure 1 below.
If , then squeeze from the right and If , then squeeze from the left and
use the new interval . use the new interval .
Figure 1. The decision process for the Fibonacci ratio search.
only one new function evaluation is to be made in the interval
we select for
the subinterval . We
already have relabeled
and since we will relabel it by
then we will have
is chosen so that and
and subtraction produces
And the ratio
is chosen so that
Now substitute (2) and (3) into (1) and get
Also the length of the interval
has been shrunk by the factor . Thus
and using this in (4) produces
Cancel the common factor
in (5) and we now have
Solving (6) for
Now we introduce the Fibonacci numbers for
the subscript . In
equation (7), substitute
and get the following
Reasoning inductively, it follows that
the Fibonacci search can be begun with
Note that the last step will be
thus no new points can be added at this stage (i.e. the algorithm terminates). Therefore, the set of possible ratios is
There will be exactly n-2 steps in a Fibonacci search!
is obtained by reducing the length of
by a factor of . After steps
the length of the last subinterval will
If the abscissa of the minimum is to be
found with a tolerance of, then
we want . It
is necessary to use n iterations, where n is
the smallest integer such that
Note. Solving the above inequality requires either a trial and error look at the sequence of Fibonacci numbers, or the deeper fact that the Fibonacci numbers can be generated by the formula
Knowing this fact may be useful, but we still need to compute all the Fibonacci numbers in order to calculate the ratios .
points and of
found, as needed, using the formulas
Note. The value of n used in formulas (9) and (10) is found using inequality (8).
Proof Fibonacci Search Fibonacci Search
Algorithm (Fibonacci Search for a Minimum). To numerically approximate the minimum of on the interval by using a Fibonacci search. Proceed with the method only if is a unimodal function on the interval . Terminate the process after n iterations have been completed, where .
Computer Programs Fibonacci Search Fibonacci Search
Mathematica Subroutine (Fibonacci Search for a Minimum).
requires the determination of two new interior points, one from the
previous iteration and the second from formula (9) or
(10). When , the
two interior points will be concurrent in the middle of the
interval. In following example, to distinguish the last
two interior points a small distinguishability constant,
is introduced. Thus when is
used in formula (9) or (10), the
coefficients of are or , respectively.
Example 1. Find
the minimum of the unimodal function on
the interval using
the Fibonacci search method. Use the tolerance
the distinguishability constant
Fibonacci and golden ratio search methods can be applied in cases
is not differentiable. It should be noted that
when n is
small the Fibonacci method
is more efficient than the golden ratio method. However, for n large the two methods are almost identical.
Various Scenarios and Animations for the Fibonacci Search Method.
Find the minimum of on
the interval .
Animations (Fibonacci Search Fibonacci Search). Internet hyperlinks to animations.
Research Experience for Undergraduates
Fibonacci Search Fibonacci Search Internet hyperlinks to web sites and a bibliography of articles.
Download this Mathematica Notebook Fibonacci Search
(c) John H. Mathews 2004