Golden section search for a minimum

(a) Golden section search

It is an interval-reduction method for a unimodal function (one minimum in the interval). Two interior points are placed at

$$x_1 = b - 0.618(b-a), \qquad x_2 = a + 0.618(b-a)$$

• If $f(x_1) < f(x_2)$, the minimum lies in $[a, x_2]$, so set $b = x_2$.
• Otherwise it lies in $[x_1, b]$, so set $a = x_1$.

The old interior point is reused as one new interior point, so each iteration needs only one new function evaluation and shrinks the interval by 0.618. Exhaustive search needs many evaluations for the same accuracy, so golden section is much cheaper. It needs no derivative.

(b) Numerical

Initial $[a,b] = [1,5]$, length 4.

After four iterations the interval is $[2.889, 3.472]$ (length 0.583, which is $4\times0.618^4$).

Estimated minimum at the mid-point: $x^* \approx 3.18$, $f \approx 27.09$.

Check by calculus: $f' = 2x - 54/x^2 = 0 \Rightarrow x^3 = 27 \Rightarrow x = 3$, $f_{min} = 27$. The search interval contains this point.

Answer: final interval $[2.89,\ 3.47]$; $x^* \approx 3.2$ (true minimum $x=3$, $f=27$).