research: Golden section search

From Wikipedia, the free encyclopedia.

Diagram of a golden section search

The Golden section search is a technique for finding the extremum (minimum or maximum) of a mathematical function, by successively narrowing brackets by upper bounds and lower bounds.

The diagram on the right illustrates the technique for finding a minimum. The functional values of $f (x)$ are on the vertical axis, and the horizontal axis is the x parameter. The value of $f (x)$ has been evaluated at the three points: $x 1$ , $x 2$ , and $x 3$ .

Since $f 2$ is smaller than either $f 1$ or $f 3$ , it is clear that a minimum lies inside the interval from $x 1$ to $x 3$ .

The next step in the minimization process is to evaluate the function at a new value of x, namely $x 4$ . It is most efficient to choose $x 4$ somewhere inside the largest interval, i.e. between $x 2$ and $x 3$ . From the diagram, it is clear that if the function yields $f 4 a$ then a minimum lies between $x 1$ and $x 4$ and the new triplet of points will be $x 1$ , $x 2$ , and $x 4$ . However if the function yields the value $f 4 b$ then a minimum lies between $x 2$ and $x 3$ , and the new triplet of points will be $x 2$ , $x 4$ , and $x 3$ . The question is, how to choose the value of $x 4$ ?

Whatever choice method is in use, it was also used to pick the position of x₂. We postulate that we would like the same proportions of spacing as we have before the choice. In other words, if $f (x 4)$ is $f 4 a$ and our new triplet of points is $x 1$ , $x 2$ , and $x 4$ then we want: