The golden section method in optimization: the divine proportion at the service of the minimum

Image by Hao Chen taken from Unsplash

The Golden Section Method (or Golden Section Search) is one of the most elegant and efficient direct sequential algorithms in one-dimensional numerical optimization. Like the Dichotomous Search Method, it leverages the information obtained at each step to discard part of the interval of uncertainty without calculating derivatives. However, instead of evaluating two new points at every iteration, it places the test points so precisely that one of them is reused in the next iteration, so that, after the first iteration, a single new evaluation per step is enough.

The secret behind this placement is the golden ratio $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618$, the famous proportion that Euclid described as the division of a segment in extreme and mean ratio and which, centuries later, became popular as the divine proportion.

In 1953, Jack Kiefer studied the optimal sequential strategies (in the minimax sense) for locating the maximum of a unimodal function (Kiefer, 1953), a work in which the Golden Section appears as a nearly optimal search strategy. Shortly afterwards, Douglass J. Wilde (1964) (Wilde, 1964) systematized these methods within the family of sequential algorithms, establishing the Golden Section as the reference method for derivative-free one-dimensional search.

The golden section algorithm

The goal of the algorithm is to minimize a continuous and unimodal function $f(x)$ within an initial interval $[a, b]$.

Where does the golden ratio come from?

Suppose that, in the current interval $[a_k, b_k]$ of length $L_k = b_k - a_k$, we place two test points symmetric with respect to the center of the interval:

\[x_1 = a_k + (1 - \tau) L_k \quad \text{and} \quad x_2 = a_k + \tau L_k, \qquad \text{with } \tfrac{1}{2} < \tau < 1\]

If $f(x_1) < f(x_2)$, we discard $[x_2, b_k]$ and the new interval is $[a_k, x_2]$, of length $L_{k+1} = \tau L_k$. In order to reuse the point $x_1$, we want it to become the right test point of the next iteration, that is:

\[a_k + (1 - \tau) L_k = a_k + \tau L_{k+1} = a_k + \tau^2 L_k\]

Which leads to the equation:

\[\tau^2 + \tau - 1 = 0 \quad \Longrightarrow \quad \tau = \frac{\sqrt{5} - 1}{2} = \frac{1}{\varphi} \approx 0.618\]

By symmetry, the reasoning is identical if the left part is discarded. Therefore, the only way to reuse one point at every iteration while keeping a constant reduction is to divide the interval according to the golden ratio: at each step the interval shrinks to $61.8\%$ of its length.

Steps of the algorithm

Initialization: Set $\tau = \frac{\sqrt{5} - 1}{2}$ and compute the two initial points: $x_1 = b - \tau (b - a) \quad \text{and} \quad x_2 = a + \tau (b - a)$ and their values $f(x_1)$ and $f(x_2)$.
Interval reduction rule:
- If $f(x_1) < f(x_2)$, unimodality guarantees that the minimum is not in $[x_2, b_k]$. The new interval is $[a_k, x_2]$. The old $x_1$ becomes the new $x_2$ and only a new $x_1 = b_{k+1} - \tau (b_{k+1} - a_{k+1})$ is computed.
- If $f(x_1) \geqslant f(x_2)$, the minimum is not in $[a_k, x_1]$. The new interval is $[x_1, b_k]$. The old $x_2$ becomes the new $x_1$ and only a new $x_2 = a_{k+1} + \tau (b_{k+1} - a_{k+1})$ is computed.
Stopping criterion: The previous step is repeated until the length of the interval is smaller than a tolerance $\varepsilon > 0$.

Unlike Dichotomous Search, there is no parameter $\delta$ limiting the achievable precision: the length of the interval tends to zero, so any tolerance $\varepsilon > 0$ can be reached.

Pseudocode

The structured algorithmic formulation is presented below:

\begin{algorithm}
\caption{Golden Section Search}
\begin{algorithmic}
\PROCEDURE{GoldenSection}{$$f, a, b, epsilon$$}
    \STATE $$tau = (sqrt(5) - 1) / 2$$
    \STATE $$ak = a$$
    \STATE $$bk = b$$
    \STATE $$x1 = bk - tau * (bk - ak)$$
    \STATE $$x2 = ak + tau * (bk - ak)$$
    \STATE $$f1 = f(x1)$$
    \STATE $$f2 = f(x2)$$
    \WHILE{$$(bk - ak) > epsilon$$}
        \IF{$$f1 < f2$$}
            \STATE $$bk = x2$$
            \STATE $$x2 = x1$$
            \STATE $$f2 = f1$$
            \STATE $$x1 = bk - tau * (bk - ak)$$
            \STATE $$f1 = f(x1)$$
        \ELSE
            \STATE $$ak = x1$$
            \STATE $$x1 = x2$$
            \STATE $$f1 = f2$$
            \STATE $$x2 = ak + tau * (bk - ak)$$
            \STATE $$f2 = f(x2)$$
        \ENDIF
    \ENDWHILE
    \STATE $$xopt = (ak + bk) / 2$$
    \RETURN $$xopt, f(xopt), [ak, bk]$$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

Numerical example

To study the behavior of the algorithm, let us consider the nonlinear function:

\[f(x) = x^2 - 3.2x + 3\]

on the interval $[a, b] = [0, 3]$, with $\tau \approx 0.618$.

Analytically, the exact minimum is located at $x^* = 1.6$ with $f(1.6) = 0.44$.

The first iterations of the golden section method for this example are:

Iteration 1:

Initial interval: $[a_0, b_0] = [0, 3]$ (Length $L_0 = 3.0$).
Test points (both are evaluated):
- $x_1 = 3 - 0.618 \cdot 3 = 1.1459 \implies f(1.1459) = 0.6462$
- $x_2 = 0 + 0.618 \cdot 3 = 1.8541 \implies f(1.8541) = 0.5046$
Decision: Since $f(x_1) > f(x_2)$, we discard the region $[0, 1.1459]$.
New interval: $[a_1, b_1] = [1.1459, 3.0]$ (Length $L_1 = 1.8541$).

Iteration 2:

Current interval: $[a_1, b_1] = [1.1459, 3.0]$.
Test points:
- $x_1 = 1.8541$ (reused, it was the previous $x_2$) $\implies f(1.8541) = 0.5046$
- $x_2 = 1.1459 + 0.618 \cdot 1.8541 = 2.2918 \implies f(2.2918) = 0.9186$ (the only new evaluation)
Decision: Since $f(x_1) < f(x_2)$, we discard the region $[2.2918, 3.0]$.
New interval: $[a_2, b_2] = [1.1459, 2.2918]$ (Length $L_2 = 1.1459$).

Proceeding in the same way, the following iterations are obtained, where the function value computed at each iteration is shown in bold (the other one is reused from the previous iteration):

Iter.	$[a_k, b_k]$	$x_1$	$f(x_1)$	$x_2$	$f(x_2)$	New interval	$L_{k+1}$
1	$[0, 3]$	$1.1459$	$\mathbf{0.6462}$	$1.8541$	$\mathbf{0.5046}$	$[1.1459, 3]$	$1.8541$
2	$[1.1459, 3]$	$1.8541$	$0.5046$	$2.2918$	$\mathbf{0.9186}$	$[1.1459, 2.2918]$	$1.1459$
3	$[1.1459, 2.2918]$	$1.5836$	$\mathbf{0.4403}$	$1.8541$	$0.5046$	$[1.1459, 1.8541]$	$0.7082$
4	$[1.1459, 1.8541]$	$1.4164$	$\mathbf{0.4737}$	$1.5836$	$0.4403$	$[1.4164, 1.8541]$	$0.4377$
5	$[1.4164, 1.8541]$	$1.5836$	$0.4403$	$1.6869$	$\mathbf{0.4476}$	$[1.4164, 1.6869]$	$0.2705$

Result: With 6 function evaluations (two in the first iteration and one in each of the following four, excluding the final evaluation of $f(x_{opt})$ in the pseudocode), the initial interval of length $3$ has been reduced to $0.2705$, guaranteeing that the optimum $x^* = 1.6$ lies within $[1.4164, 1.6869]$.

These iterations are shown graphically in the following figure:

Technical analysis: Golden Section vs. Dichotomous Search

Since, after the first iteration, each evaluation reduces the interval by a factor $\tau$, after $N$ function evaluations the length of the final interval is:

\[L_N = (b - a)\, \tau^{N-1} \approx (b - a) \cdot 0.618^{N-1}\]

Therefore, for the final interval to have a width smaller than $\varepsilon$, it suffices to choose:

\[N > 1 + \frac{\ln\left(\varepsilon / (b - a)\right)}{\ln \tau}\]

Comparing the interval reduction per function evaluation:

Uniform Search (Simultaneous): linear reduction, with a ratio $R_N = \frac{2}{N-1}$.
Dichotomous Method (Sequential): each pair of evaluations approximately halves the interval, that is, a factor of $\sqrt{1/2} \approx 0.707$ per evaluation.
Golden Section (Sequential): each evaluation reduces the interval by a factor $\tau \approx 0.618$.

Thus, for example, to reach a tolerance $\varepsilon = 10^{-4}$ on the interval $[0, 3]$, the Golden Section needs only 23 evaluations, compared to approximately 30 for the Dichotomous Method and tens of thousands for Uniform Search.

Advantages and Limitations

Advantages:
- A single evaluation per iteration: After the first iteration, it reuses one of the two test points, which makes it especially suitable when evaluating $f(x)$ is expensive.
- Constant and predictable reduction: The interval is always reduced by the same factor $\tau$, so the number of required evaluations is known in advance.
- No derivatives or parameters: It requires neither derivatives nor tuning parameters such as the $\delta$ of the Dichotomous Method. However, the guarantee on the interval requires the function to be continuous and unimodal.
Limitations:
- Sequential nature: Each evaluation depends on the result of the previous one, so it cannot be parallelized.
- Rounding errors: Since $\tau$ is irrational, reusing points over many iterations accumulates small numerical errors that can break the symmetry of the test points. In practical implementations, the position of both points is usually recomputed periodically from the endpoints of the interval.
- Linear convergence: If the function is smooth, methods that use derivatives or interpolation (such as Newton’s method or parabolic interpolation) converge much faster near the optimum.

The Golden Section Method is the natural culmination of derivative-free sequential search. Where the Dichotomous Method wasted information by evaluating two new points at every step, the Golden Section places its points so precisely that nothing is lost, and it does so by resorting to a proportion that humanity has admired in art and nature for more than two thousand years. Yet another example that, in optimization, mathematical elegance and computational efficiency often go hand in hand.

Want to keep exploring the world of Operations Research? Discover more posts on the topic here.