Golden section search

From Glossary

Jump to: navigation, search


This finds an interval, LaTeX: [a,b], that contains a maximum of a unimodal function whose domain is LaTeX: [0,1], such that the length of the final interval, LaTeX: [a,b], satisfies: LaTeX: b-a < e (where LaTeX: e > 0 is specified). The golden ratio is denoted below by LaTeX: g, which is approximately 0.618.

  1. Initially compute LaTeX: f(g) and LaTeX: f(1-g), and set the interval of uncertainty to the original endpoints, LaTeX: a=0 and LaTeX: b=1. In general, we have LaTeX: x and LaTeX: y placed in LaTeX: [a,b], such that the distances from the endpoints are the same:
                     g(b-a)
                |----------------|
                a------x---------y------b
                       |----------------|
                             g(b-a)
                 
    
  2. Given the interval LaTeX: [a, b] contains evaluations LaTeX: f(x) and LaTeX: f(y), with LaTeX: x < y, compare: if LaTeX: f(x) > f(y), replace LaTeX: b with LaTeX: y; if LaTeX: f(x) < f(y), replace LaTeX: a with LaTeX: x. (If LaTeX: f(x)=f(y), this leaves the interval LaTeX: [x,y], in which case evaluate LaTeX: f(x+g(y-x)).) One of the following cases prevail:

                  *                                          *
                            *                     *
           a------x---------y------b       a------x---------y------b
                            : drop :       : drop :
                f(x) > f(y)                           f(x) < f(y)
                  x=g(y-a)                              y=g(b-x)
    
                                 *         *
                          a------x---------y------b
                          : drop :         : drop :
                                 f(x) = f(y)
                 
    

The golden ratio is the limit of successive fibonacci numbers: (LaTeX: F_{N-1} / F_{N}) \rightarrow g. Thus, the golden section search approaches Fibonacci search as the number of functional evaluations (N) becomes large.


Views
Personal tools