Module for the Fibonacci Search


Bracketing Search Methods

An approach for finding the minimum of  [Graphics:Images/FibonacciSearchMod_gr_1.gif]  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  [Graphics:Images/FibonacciSearchMod_gr_2.gif]  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  [Graphics:Images/FibonacciSearchMod_gr_3.gif],  a special condition must be met to ensure that there is a proper minimum in the given interval.

Definition (Unimodal Function)  The function  [Graphics:Images/FibonacciSearchMod_gr_4.gif]  is unimodal on  [Graphics:Images/FibonacciSearchMod_gr_5.gif],  if there exists a unique number [Graphics:Images/FibonacciSearchMod_gr_6.gif]  such that  
[Graphics:Images/FibonacciSearchMod_gr_7.gif]  is decreasing on  [Graphics:Images/FibonacciSearchMod_gr_8.gif],  
[Graphics:Images/FibonacciSearchMod_gr_9.gif]  is increasing on  [Graphics:Images/FibonacciSearchMod_gr_10.gif].  

Fibonacci Search

    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
  [Graphics:Images/FibonacciSearchMod_gr_11.gif]  remains constant on each subinterval and the search is terminated at the [Graphics:Images/FibonacciSearchMod_gr_12.gif] subinterval, provided that  [Graphics:Images/FibonacciSearchMod_gr_13.gif]  or[Graphics:Images/FibonacciSearchMod_gr_14.gif]  where [Graphics:Images/FibonacciSearchMod_gr_15.gif] are the predefined tolerances.  The  Fibonacci search method differs from the golden ratio method in that the value of  [Graphics:Images/FibonacciSearchMod_gr_16.gif]  is not constant on each subinterval.  Additionally, the number of subintervals (iterations) is predetermined and based on the specified tolerances.  

    The Fibonacci search is based on the sequence of Fibonacci numbers which are defined by the equations

[Graphics:Images/FibonacciSearchMod_gr_18.gif]   for   [Graphics:Images/FibonacciSearchMod_gr_19.gif]  

Thus the Fibonacci numbers are  [Graphics:Images/FibonacciSearchMod_gr_20.gif]  

Exploration for Fibonacci Numbers


    Assume we are given a function  [Graphics:Images/FibonacciSearchMod_gr_86.gif]  that is unimodal on the interval  [Graphics:Images/FibonacciSearchMod_gr_87.gif].  As in the golden ratio search a value [Graphics:Images/FibonacciSearchMod_gr_88.gif] [Graphics:Images/FibonacciSearchMod_gr_89.gif] is selected so that both of the interior points  [Graphics:Images/FibonacciSearchMod_gr_90.gif] will be used in the next subinterval and there will be only one new function evaluation.  

    If  [Graphics:Images/FibonacciSearchMod_gr_91.gif],  then the minimum must occur in the subinterval [Graphics:Images/FibonacciSearchMod_gr_92.gif], and we replace  [Graphics:Images/FibonacciSearchMod_gr_93.gif] and [Graphics:Images/FibonacciSearchMod_gr_94.gif]  and continue the search in the new subinterval [Graphics:Images/FibonacciSearchMod_gr_95.gif].   If  [Graphics:Images/FibonacciSearchMod_gr_96.gif], then the minimum must occur in the subinterval [Graphics:Images/FibonacciSearchMod_gr_97.gif], and we replace  [Graphics:Images/FibonacciSearchMod_gr_98.gif]  and  [Graphics:Images/FibonacciSearchMod_gr_99.gif]  and continue the search in the new subinterval [Graphics:Images/FibonacciSearchMod_gr_100.gif].  These choices are shown in Figure 1 below.  

[Graphics:Images/FibonacciSearchMod_gr_101.gif]               [Graphics:Images/FibonacciSearchMod_gr_102.gif]

[Graphics:Images/FibonacciSearchMod_gr_103.gif], then squeeze from the right and               If [Graphics:Images/FibonacciSearchMod_gr_104.gif], then squeeze from the left and  
use the new interval  [Graphics:Images/FibonacciSearchMod_gr_105.gif].                           use the new interval  [Graphics:Images/FibonacciSearchMod_gr_106.gif].

                Figure 1.  The decision process for the Fibonacci ratio search.   


    If  [Graphics:Images/FibonacciSearchMod_gr_107.gif]  and only one new function evaluation is to be made in the interval [Graphics:Images/FibonacciSearchMod_gr_108.gif],  then we select  [Graphics:Images/FibonacciSearchMod_gr_109.gif]  [Graphics:Images/FibonacciSearchMod_gr_110.gif]  for the subinterval  [Graphics:Images/FibonacciSearchMod_gr_111.gif].   We already have relabeled  

and since  
[Graphics:Images/FibonacciSearchMod_gr_113.gif] we will relabel it by  

then we will have


The ratio [Graphics:Images/FibonacciSearchMod_gr_116.gif] is chosen so that  [Graphics:Images/FibonacciSearchMod_gr_117.gif]  and  [Graphics:Images/FibonacciSearchMod_gr_118.gif] and subtraction produces

(2)        [Graphics:Images/FibonacciSearchMod_gr_121.gif]  

And the ratio [Graphics:Images/FibonacciSearchMod_gr_122.gif] is chosen so that  

(3)        [Graphics:Images/FibonacciSearchMod_gr_123.gif].  

Now substitute (2) and (3) into (1) and get  

(4)        [Graphics:Images/FibonacciSearchMod_gr_124.gif].  

Also the length of the interval [Graphics:Images/FibonacciSearchMod_gr_125.gif] has been shrunk by the factor [Graphics:Images/FibonacciSearchMod_gr_126.gif].  Thus  [Graphics:Images/FibonacciSearchMod_gr_127.gif] and using this in (4) produces  

(5)        [Graphics:Images/FibonacciSearchMod_gr_128.gif].  

Cancel the common factor  [Graphics:Images/FibonacciSearchMod_gr_129.gif] in (5) and we now have  

(6)        [Graphics:Images/FibonacciSearchMod_gr_130.gif].  

Solving (6) for [Graphics:Images/FibonacciSearchMod_gr_131.gif] produces  

(7)        [Graphics:Images/FibonacciSearchMod_gr_132.gif].  

Now we introduce the Fibonacci numbers  [Graphics:Images/FibonacciSearchMod_gr_133.gif]  for the subscript  [Graphics:Images/FibonacciSearchMod_gr_134.gif].  In equation (7), substitute  [Graphics:Images/FibonacciSearchMod_gr_135.gif] and get the following  




Reasoning inductively, it follows that the Fibonacci search can be begun with



        [Graphics:Images/FibonacciSearchMod_gr_141.gif]    for  [Graphics:Images/FibonacciSearchMod_gr_142.gif].  

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!  

    The  [Graphics:Images/FibonacciSearchMod_gr_145.gif]  subinterval is obtained by reducing the length of the  [Graphics:Images/FibonacciSearchMod_gr_146.gif]  subinterval by a factor of  [Graphics:Images/FibonacciSearchMod_gr_147.gif].  After  [Graphics:Images/FibonacciSearchMod_gr_148.gif]  steps the length of the last subinterval will be  


If the abscissa of the minimum is to be found with a tolerance of[Graphics:Images/FibonacciSearchMod_gr_150.gif],  then we want [Graphics:Images/FibonacciSearchMod_gr_151.gif].  It is necessary to use  n  iterations,  where  n  is the smallest integer such that  

(8)        [Graphics:Images/FibonacciSearchMod_gr_152.gif].  

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  [Graphics:Images/FibonacciSearchMod_gr_154.gif]  in order to calculate the ratios  [Graphics:Images/FibonacciSearchMod_gr_155.gif].  

    The interior points  [Graphics:Images/FibonacciSearchMod_gr_156.gif]  and  [Graphics:Images/FibonacciSearchMod_gr_157.gif]  of the [Graphics:Images/FibonacciSearchMod_gr_158.gif] subinterval  [Graphics:Images/FibonacciSearchMod_gr_159.gif]  are 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  [Graphics:Images/FibonacciSearchMod_gr_162.gif]  on the interval  [Graphics:Images/FibonacciSearchMod_gr_163.gif]  by using a Fibonacci search.  Proceed with the method only if  [Graphics:Images/FibonacciSearchMod_gr_164.gif]  is a unimodal function on the interval  [Graphics:Images/FibonacciSearchMod_gr_165.gif].  Terminate the process after  n iterations have been completed, where  [Graphics:Images/FibonacciSearchMod_gr_166.gif].

Computer Programs  Fibonacci Search  Fibonacci Search

Mathematica Subroutine (Fibonacci Search for a Minimum).


    Each iteration requires the determination of two new interior points, one from the previous iteration and the second from formula (9) or (10).   When  [Graphics:Images/FibonacciSearchMod_gr_168.gif],  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, [Graphics:Images/FibonacciSearchMod_gr_169.gif], is introduced. Thus when  [Graphics:Images/FibonacciSearchMod_gr_170.gif]  is used in formula (9) or (10), the coefficients of  [Graphics:Images/FibonacciSearchMod_gr_171.gif]  are  [Graphics:Images/FibonacciSearchMod_gr_172.gif]  or  [Graphics:Images/FibonacciSearchMod_gr_173.gif],  respectively.

Example 1.  Find the minimum of the unimodal function  [Graphics:Images/FibonacciSearchMod_gr_174.gif]  on the interval  [Graphics:Images/FibonacciSearchMod_gr_175.gif]  using the Fibonacci search method.  Use the tolerance of  [Graphics:Images/FibonacciSearchMod_gr_176.gif]  and the distinguishability constant  [Graphics:Images/FibonacciSearchMod_gr_177.gif]
Solution 1.


    Both the Fibonacci and golden ratio search methods can be applied in cases where [Graphics:Images/FibonacciSearchMod_gr_241.gif] 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.


Example 2. Find the minimum of  [Graphics:Images/FibonacciSearchMod_gr_243.gif]  on the interval  [Graphics:Images/FibonacciSearchMod_gr_244.gif].  
Solution 2.


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