Golden section search

From DDWiki

Golden section search is a bracketing optimization method that can be used to find the maximum or minimum of a single unimodal function. It derives its name from the golden ratio which is used as an efficient means to define the two interior points used in the algorithm.

1 Golden Ratio
2 Example
3 External Links
4 References

Golden Ratio

The term "golden ratio" was coined by the Ancient Greeks who found that this ratio was aesthetically pleasing. The golden ratio is related to the Fibonaci sequence and shows up frequently in nature as well as science and engineering. The ratio can be defined as follows:

$R=\frac{\sqrt{5}-1}{2}=0.61803...$

Example

The Golden section search finds local extrema by successively narrowing the brackets that enclose the local extrema. The following will be demonstrated for the minimization problem pictured. The first step is to define the inital bracket interval that contains only one local minimum at $x = a$ and $x = b$ . Once this interval is selected, two interior points, $x 1$ and $x 2$ , must now be selected using the golden ratio $R$ .

$d=R(b-a)\,$
$x_{1}=b-d\,$
$x_{2}=a+d\,$

A simple comparison between $f (x 1)$ and $f (x 2)$ rules out one region where the minimum cannot exist. In this case because $f (x 2) > f (x 1)$ the minimum must exist to the left of $f (x 2)$ thus the region between $f (x 2)$ and $b$ can be removed from the bracket. Similarly in the case where $f (x 1) > f (x 2)$ , the region between $a$ and $f (x 1)$ would be removed from the bracket.

Because $x 1$ and $x 2$ were chosen using the golden ratio, they coincide with points needed in the next iteration, requiring only one function evaluation per iteration.

In the second iteration, the new outer brackets, $a'$ and $b'$ coincide with $a$ and $x 2$ of the previous iteration. Similarly one of the new interior points $f (x 2')$ coincides with $f (x 1)$ of the previous iteration. As a result of these coinciding points, only one new function evaluation needs to be made at the new interior point $f (x 1')$ where

$d'=R(b'-a')\,$
$x_{1}'=b'-d'\,$

Similarly if the bracket was truncated in the opposite direction, the new function evaluation would be at $f (x 2')$ where

$x_{2}'=a'+d'\,$

This process continues until the point converges close enough to the minima to trigger the termination criterion. Since the brackets shrink by a predictable amount each iteration, the terminination criteria can be as simple as ending after a predetermined number of iterations.

This algorithm can be used to find local maxima by reversing which region is removed from the bracket. In order to find the maximum, if $f (x 2) < f (x 1)$ remove the region between $f (x 2)$ and $b$ from the bracket, and if $f (x 1) < f (x 2)$ , remove the region between $a$ and $f (x 1)$ from the bracket. Once removed, the new points required can be found using the same method as for minimization.