Fibonacci Method

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.

The function is unimodal on , if there exists a unique number such that

is decreasing on ,
and
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.

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


for

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 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
use the new interval .

If , then squeeze from the left and
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).