 # Fibonacci search

This finds the maximum of a unimodal function on an interval, $LaTeX: [a, b]$, by evaluating points placed according to a fibonacci sequence, $LaTeX: F_N$. If there are $LaTeX: F_N$ points in the interval, only $LaTeX: N$ evaluations are needed. In the continuous case, we begin with some interval of uncertainty, $LaTeX: [a,b]$, and we reduce its length to $LaTeX: (b-a)/F_N$. The ratio, $LaTeX: g_n = F_(n-1)/F_n$, is the key to the placements.

Here is the method for the continuous case:

1. Initialization. Let $LaTeX: x = a + (1 - g_N)(b-a)$ and $LaTeX: y = a + g_N(b-a)$. Evaluate $LaTeX: f(x)$ and $LaTeX: f(y)$ and set $LaTeX: n=N$.
2. Iteration. If $LaTeX: f(x) < f(y)$, reduce the interval to $LaTeX: (x, b]$ (i.e., set $LaTeX: a=x$), decrement $LaTeX: n$ to $LaTeX: n-1$, and set $LaTeX: x = y$ and $LaTeX: y = a + g_n(b-a)$. If $LaTeX: f(x) \ge f(y)$, reduce the interval to $LaTeX: [a, y)$ (i.e., set $LaTeX: b=y$), decrement $LaTeX: n$ to $LaTeX: n-1$, and set $LaTeX: y = x$ and $LaTeX: x = a + (1-g_n)(b-a)$.

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 $LaTeX: [0,1]$ 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 $LaTeX: N$, the placement ratio $LaTeX: (g_N)$ 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 $LaTeX: N$ is the number of evaluations needed to reduce length of the interval of uncertainty to $LaTeX: 1/F_N$. For example, with 20 evaluations dichotomous search reduces the interval of uncertainty to $LaTeX: 0.0009765$ of its original length (with separation value near $LaTeX: 0$). The most reduction comes from fibonacci search, which is more than an order of magnitude better, at $LaTeX: 0.0000914$. 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
========================================================================

```