Fibonacci Search

    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   and   and 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.   

    If    and only one new function evaluation is to be made in the interval ,  then we select      for the subinterval  .   We already have relabeled  
    
        

and since   we will relabel it by  

        
        
then we will have

(1)        .   

The ratio is chosen so that    and   and subtraction produces

               
        
               
        
(2)          

And the ratio is chosen so that  

(3)        .  

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

(4)        .  

Also the length of the interval has been shrunk by the factor .  Thus   and using this in (4) produces  

(5)        .  

Cancel the common factor   in (5) and we now have  

(6)        .  

Solving (6) for produces  

(7)        .  

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

        

        
and

            for  .  

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    subinterval is obtained by reducing the length of the    subinterval by a factor of  .  After    steps the length of the last subinterval will be  

        .

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  

(8)        .  

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  .  

    The interior points    and    of the subinterval    are found, as needed, using the formulas  

(9)          ,  
        
(10)        .  

Note.  The value of  n  used in formulas (9) and (10) is found using inequality (8).

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  .

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  ,  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.