# Fibonacci search

### From Glossary

This finds the maximum of a
unimodal function on an interval, ,
by evaluating points placed according to a fibonacci sequence,
. If there are points in the interval, only
evaluations are needed. In the continuous case, we begin with
some *interval of uncertainty*, , and we reduce its
length to . The ratio, , is
the key to the placements.

Here is the method for the continuous case:

*Initialization*. Let and . Evaluate and and set .*Iteration*. If , reduce the interval to (i.e., set ), decrement to , and set and . If , reduce the interval to (i.e., set ), decrement to , and set and .

The fibonacci search method minimizes the maximum number of evaluations needed to reduce the interval of uncertainty to within the prescribed length. For example, it reduces the length of a unit interval to 1/10946 = 0.00009136 with only 20 evaluations. In the case of a finite set, fibonacci search finds the maximum value of a unimodal function on 10,946 points with only 20 evaluations, but this can be improved – see lattice search.

For very large , the placement ratio approaches the golden mean, and the method approaches the golden section search. Here is a comparison of interval reduction lengths for fibonacci, golden section and dichotomous search methods. In each case is the number of evaluations needed to reduce length of the interval of uncertainty to . For example, with 20 evaluations dichotomous search reduces the interval of uncertainty to of its original length (with separation value near ). The most reduction comes from fibonacci search, which is more than an order of magnitude better, at . Golden section is close (and gets closer as N gets larger).

Evaluations Fibonacci Dichotomous Golden section N 1/F_N 1/2^(N/2) 1/(1.618)^(N-1) ======================================================================== 5 0.125 0.25 0.146 10 0.0112 0.0312 0.0131 15 0.00101 0.00781 0.00118 20 0.0000914 0.000976 0.000107 25 0.00000824 0.0002441 0.0000096 ========================================================================