Golden-section search

The golden-section search is a technique for finding the extremum (minimum or maximum) of a strictly unimodal function by successively narrowing the range of values inside which the extremum is known to exist. The technique derives its name from the fact that the algorithm maintains the function values for triples of points whose distances form a golden ratio. The algorithm is the limit of Fibonacci search (also described below) for a large number of function evaluations. Fibonacci search and golden-section search were discovered by Kiefer (1953) (see also Avriel and Wilde (1966)).

The discussion here is posed in terms of searching for a minimum (searching for a maximum is similar) of a unimodal function. Unlike finding a zero, where two function evaluations with opposite sign are sufficient to bracket a root, when searching for a minimum, three values are necessary. The golden-section search is an efficient way to reduce progressively the interval locating the minimum. The key is to observe that regardless of how many points have been evaluated, the minimum lies within the interval defined by the two points adjacent to the point with the least value so far evaluated.

The diagram above illustrates a single step in the technique for finding a minimum. The functional values of ${\displaystyle f(x)}$ are on the vertical axis, and the horizontal axis is the x parameter. The value of ${\displaystyle f(x)}$ has already been evaluated at the three points: ${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$, and ${\displaystyle x_{3}}$. Since ${\displaystyle f_{2}}$ is smaller than either ${\displaystyle f_{1}}$ or ${\displaystyle f_{3}}$, it is clear that a minimum lies inside the interval from ${\displaystyle x_{1}}$ to ${\displaystyle x_{3}}$.

...
Wikipedia