Mathematics Source Library
C & ASM


Fibonacci Search

Fibonacci Search

If f(x) is a unimodal function on the interval [a,b], then the search for a local minimum of f on a fixed grid on [a,b] can be optimized so as to require the fewest number of function evaluations. The interval [a,b] is partitioned into N intervals [a,x1],[x1,x2],...,[xn-1,b]. At each stage, the indices of gridpoints corresponding to two successive Fibonacci numbers are chosen so that among the 3 subintervals, either the left-most or right-most subinterval is excluded. The subinterval that is excluded is that subinterval for which the function evaluated at the inner-most endpoint is a maximum. The process is then repeated with the current interval and two successive Fibonacci numbers, the maximum of the two Fibonacci numbers at this stage being the minimum of the two Fibonacci numbers of the previous stage. The process thus requires two function evaluations to start the process and one function evaluation at each stage thereafter.

Function List

  • void Min_Search_Fibonacci( double (*f)(double), double* a, double* fa, double *b, double *fb, double grid_size )

    This routine attempts to shorten the interval of uncertainty [*a,*b] which brackets a local minimum of the user-supplied function f(x) by virtually creating grid points starting at *a with a grid spacing grid_size and ending at *b and then only evaluating the function at those grid points given by the method described above. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

    On input the parameters *a and *b, with *a < *b, should bracket a local minimum and the parameters, *fa and *fb, should be the values of f(x) evaluated at *a and *b respectively. The function f should be unimodal on the interval [*a, *b].

  • void Max_Search_Fibonacci( double (*f)(double), double* a, double* fa, double *b, double *fb, double grid_size )

    This routine attempts to shorten the interval of uncertainty [*a,*b] which brackets a local maximum of the user-supplied function f(x) by virtually creating grid points starting at *a with a grid spacing grid_size and ending at *b and then only evaluating the function at those grid points given by the method described above. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

    On input the parameters *a and *b, with *a < *b, should bracket a local maximum and the parameters, *fa and *fb, should be the values of f(x) evaluated at *a and *b respectively. The function f should be unimodal on the interval [*a, *b].

  • void Min_Line_Search_Fibonacci( double (*f)(double*), double* base, double* direction, double* x, int n, double* a, double *fa, double *b, double *fb, double grid_size )

    Given the user-supplied real-valued function f of an n-dimensional vector and the line segment (base - λ direction) where a ≤ λ ≤ b this routine attempts to shorten the interval of uncertainty [*a,*b] which brackets a local minimum of
    g(λ) = f(base - λ direction) by virtually creating grid points starting at *a with a grid spacing grid_size and ending at *b and then only evaluating the function at those grid points given by the method described above. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

    On input the parameters *a and *b, with *a < *b, should bracket a local minimum of
    g(λ) = f(base - λ direction) with a ≤ λ ≤ b and the parameters, *fa and *fb, should be the values of f(x) evaluated at (base - *a direction) and (base - *b direction) respectively. The function f should be unimodal on the line segment
    (base - λ direction), *a ≤ λ ≤ *b.

  • void Max_Line_Search_Fibonacci( double (*f)(double*), double* base, double* direction, double* x, int n, double* a, double *fa, double *b, double *fb, double grid_size )

    Given the user-supplied real-valued function f of an n-dimensional vector and the line segment (base + λ direction) where a ≤ λ ≤ b this routine attempts to shorten the interval of uncertainty [*a,*b] which brackets a local maximum of
    g(λ) = f(base + λ direction) by virtually creating grid points starting at *a with a grid spacing grid_size and ending at *b and then only evaluating the function at those grid points given by the method described above. Upon return, *a is set to the left-most endpoint of the final interval, *fa is the value of the function there, *b is set to the right-most endpoint of the final interval and *fb is the value of the function there.

    On input the parameters *a and *b, with *a < *b, should bracket a local maximum of
    g(λ) = f(base + λ direction) with a ≤ λ ≤ b and the parameters, *fa and *fb, should be the values of f(x) evaluated at (base + *a direction) and (base + *b direction) respectively. The function f should be unimodal on the line segment
    (base + λ direction), *a ≤ λ ≤ *b.

C Source Code