Fibonacci search

From Glossary

Jump to: navigation, 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 
    ========================================================================
      


Views
Personal tools