 # Golden section 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.