Lesson 40: Golden Section Search¶
40.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Derive the golden ratio from the requirement that one probe be reusable at every stage.
- State the reduction law \(L_n=(0.618)^{\,n-1}L_0\) and use it to size a search.
- Execute golden section search by hand and verify the reduction at each stage.
- Compare golden section with Fibonacci search on cost, accuracy and convenience.
- Choose sensibly between the elimination methods of Lessons 38–40.
40.2 Deriving the Golden Ratio¶
Fibonacci search is optimal but requires \(n\) to be fixed in advance, because the first placement depends on \(F_{n-2}/F_n\). Golden section removes that restriction by asking a different question:
Is there a single, constant fraction \(\tau\) such that placing the probes at \(\tau\) of the way in from each end lets one probe be reused for ever?
The derivation¶
Let the interval be \([0,1]\) and place probes at \(x_1=1-\tau\) and \(x_2=\tau\) (with \(\tau>\tfrac12\)). Suppose the right portion is discarded, leaving \([0,\tau]\) of length \(\tau\).
The surviving probe \(x_1=1-\tau\) must land exactly where the new stage wants its right-hand probe, which by the same rule is at \(\tau\) of the way along the new interval, i.e. at \(\tau\cdot\tau=\tau^{2}\) from the left end. Therefore
The golden ratio. $\(\boxed{\ \tau=\frac{\sqrt5-1}{2}=0.618034,\qquad 1-\tau=0.381966,\qquad \tau^{2}=1-\tau\ }\)$ The reciprocal \(1/\tau=1.618034=\tau+1\) is denoted \(\phi\).
The self-reproducing property \(\tau^2=1-\tau\) is exactly what makes the inheritance work at every stage, with no reference to how many stages remain.
Connection to Fibonacci¶
so golden section is the limiting form of Fibonacci search as \(n\to\infty\). Fibonacci uses the exact ratios for a known finite \(n\); golden section uses the limiting ratio for all stages, giving up a little efficiency for complete flexibility.
40.3 The Algorithm¶
Step 1. On \([a,b]\) with \(L=b-a\), set $\(x_1=a+0.382L,\qquad x_2=a+0.618L\)$ and evaluate \(f(x_1)\), \(f(x_2)\). (2 evaluations)
Step 2. Compare: - If \(f(x_1)<f(x_2)\): set \(b\leftarrow x_2\), then \(x_2\leftarrow x_1\) and \(f_2\leftarrow f_1\) (inherited), and compute the new \(x_1=a+0.382(b-a)\). (1 evaluation) - Else: set \(a\leftarrow x_1\), then \(x_1\leftarrow x_2\) and \(f_1\leftarrow f_2\) (inherited), and compute the new \(x_2=a+0.618(b-a)\). (1 evaluation)
Step 3. Repeat until \(b-a<\epsilon\). Report \(x^{*}\approx(a+b)/2\).
The reduction law¶
Each stage multiplies the interval by \(\tau=0.618\), and the first stage costs two evaluations while each later one costs one. Hence after \(n\) evaluations there have been \(n-1\) reductions:
To reach an accuracy \(\epsilon\):
Comparison with Fibonacci¶
| Fibonacci | Golden section | |
|---|---|---|
| Final interval after \(n\) evaluations | \(L_0/F_n\) | \(L_0(0.618)^{n-1}\) |
| \(n=5\) | \(L_0/8=0.1250L_0\) | \(0.1459L_0\) |
| \(n=10\) | \(L_0/89=0.01124L_0\) | \(0.01316L_0\) |
| \(n=20\) | \(L_0/10946=9.14\times10^{-5}L_0\) | \(1.07\times10^{-4}L_0\) |
| Must fix \(n\) in advance? | yes | no |
| Ratios needed | a Fibonacci table | one constant, \(0.618\) |
| Degenerate final step? | yes (\(\varepsilon\)-perturbation) | no |
Golden section is about \(17\,\%\) worse per interval, which costs roughly ONE extra evaluation — and that gap does not grow with \(n\). In exchange it can be stopped at any moment, needs no table, and has no awkward final step. In practice golden section is almost always the right choice; Fibonacci is studied because it establishes the theoretical bound.
40.4 Solved Problems¶
Problem 1 — A complete golden section search¶
Minimise \(f(x)=x^{2}+\dfrac{54}{x}\) on \([1,5]\) using \(7\) evaluations. (Exact: \(x^{*}=3\), \(f=27\).)
Solution. \(L_0=4\).
Stage 1. \(x_1=1+0.382(4)=2.52786\), \(x_2=1+0.618(4)=3.47214\).
\(f_1\ge f_2\Rightarrow\) discard \([1,\,2.52786]\); new interval \([2.52786,\ 5]\), and \(x_2=3.47214\) becomes the new \(x_1\).
Stage 2. \(L=2.47214\); new \(x_2=2.52786+0.618(2.47214)=4.05573\).
\(f_1<f_2\Rightarrow\) discard \([4.05573,\,5]\); new interval \([2.52786,\ 4.05573]\).
Stage 3. \(L=1.52786\); new \(x_1=2.52786+0.382(1.52786)=3.11146\).
\(f_1<f_2\Rightarrow\) discard \([3.47214,\,4.05573]\); new interval \([2.52786,\ 3.47214]\).
Stage 4. \(L=0.94427\); new \(x_1=2.52786+0.382(0.94427)=2.88854\).
\(f_1\ge f_2\Rightarrow\) discard \([2.52786,\,2.88854]\); new interval \([2.88854,\ 3.47214]\).
Stage 5. \(L=0.58359\); new \(x_2=2.88854+0.618(0.58359)=3.24922\).
\(f_1<f_2\Rightarrow\) discard \([3.24922,\,3.47214]\); new interval \([2.88854,\ 3.24922]\).
Stage 6. \(L=0.36068\); new \(x_1=2.88854+0.382(0.36068)=3.02631\).
\(f_1<f_2\Rightarrow\) discard \([3.11146,\,3.24922]\); new interval \([2.88854,\ 3.11146]\).
Summary table.
| Stage | \([a,b]\) | \(L\) | \(x_1\) | \(x_2\) | \(f_1\) | \(f_2\) | Discard |
|---|---|---|---|---|---|---|---|
| 1 | \([1.00000,\ 5.00000]\) | 4.00000 | 2.52786 | 3.47214 | 27.75202 | 27.60812 | left |
| 2 | \([2.52786,\ 5.00000]\) | 2.47214 | 3.47214 | 4.05573 | 27.60812 | 29.76344 | right |
| 3 | \([2.52786,\ 4.05573]\) | 1.52786 | 3.11146 | 3.47214 | 27.03638 | 27.60812 | right |
| 4 | \([2.52786,\ 3.47214]\) | 0.94427 | 2.88854 | 3.11146 | 27.03823 | 27.03638 | left |
| 5 | \([2.88854,\ 3.47214]\) | 0.58359 | 3.11146 | 3.24922 | 27.03638 | 27.17680 | right |
| 6 | \([2.88854,\ 3.24922]\) | 0.36068 | 3.02631 | 3.11146 | 27.00206 | 27.03638 | right |
| — | \([2.88854,\ 3.11146]\) | 0.22291 |
Checks. Every consecutive pair of lengths is in the ratio \(0.618\): \(2.47214/4=0.61804\), \(1.52786/2.47214=0.61804\), and so on ✓. The formula (2.1) gives \(L_7=4(0.618)^{6}=0.22291\) ✓.
Interpretation. Notice the middle column of the table: at each stage one of \(x_1,x_2\) is copied from the row above — the inheritance that makes each stage cost one evaluation. The midpoint estimate \(\hat x=3.00000\) is exact to five decimals here, far better than the interval width of \(0.22\) suggests. The interval is a guarantee; the midpoint is usually much better than the guarantee.
Problem 2 — Golden section against Fibonacci on the same problem¶
Compare the result of Problem 1 with Fibonacci search (Lesson 39, Problem 1) on the same function and interval.
Solution.
| Fibonacci, \(n=6\) | Golden section, \(n=7\) | |
|---|---|---|
| Final interval | \([2.84615,\ 3.15485]\) | \([2.88854,\ 3.11146]\) |
| Width | 0.30869 | 0.22291 |
| Midpoint estimate | 3.00050 | 3.00000 |
| Evaluations | 6 | 7 |
| Interval per evaluation | \(L_0/F_6=0.30769\) | \(L_0(0.618)^6=0.22291\) |
Like-for-like at \(n=6\). Golden section with \(6\) evaluations would give \(4(0.618)^{5}=0.36068\) against Fibonacci's \(0.30769\) — Fibonacci is \(14.7\,\%\) better.
Like-for-like at a target of \(0.30\). Fibonacci needs \(F_n\ge4/0.3=13.33\), so \(F_7=21\) and \(n=7\). Golden section needs \((0.618)^{n-1}\le0.075\), i.e. \(n-1\ge5.38\), so \(n=7\). A dead heat.
Interpretation. The gap is one evaluation at most, and often zero because both must round up to a whole number. Set against that, golden section:
- needs no decision about \(n\) before starting, so the search can simply run until the answer is good enough;
- has no degenerate last step and no \(\varepsilon\) to choose;
- can be stopped early if the outer algorithm no longer needs precision — which, as Lesson 39 Problem 5 argued, is the normal situation inside a multivariable method.
Golden section wins on every practical criterion and loses only on the theoretical one.
Problem 3 — Sizing a search¶
How many evaluations does golden section need to locate the minimum of a function on \([0,\,50]\) to within \(\pm0.01\) (an interval of \(0.02\))?
Solution. Require \(L_n=(0.618)^{n-1}(50)\le0.02\), i.e. \((0.618)^{n-1}\le4\times10^{-4}\).
Verify: \((0.618)^{17}=2.798\times10^{-4}\) and \(50(2.798\times10^{-4})=0.0140\le0.02\) ✓, while \(n=17\) gives \(50(0.618)^{16}=0.0226>0.02\) ✗.
Comparison.
| Method | Evaluations for \(L=0.02\) on \([0,50]\) |
|---|---|
| Exhaustive | \(2(50)/0.02-1=4999\) |
| Interval halving | \((0.5)^{(n-1)/2}\le4\times10^{-4}\Rightarrow (n-1)/2\ge11.29\), so 25 (n odd) |
| Golden section | 18 |
| Fibonacci | \(F_n\ge2500\Rightarrow F_{17}=2584\), so 17 |
Interpretation. Golden section needs 18 evaluations where exhaustive search needs 4999 — a factor of \(278\). The reason is structural: exhaustive search discards nothing, so its interval falls like \(1/n\), while every sequential method discards a fixed fraction each stage and so falls like \(c^{n}\). Linear versus exponential is the whole story of Lessons 38–40.
Problem 4 — Golden section inside steepest descent¶
Minimise \(f(x_1,x_2)=(x_1-2)^{2}+(x_2-3)^{2}\) from \(\mathbf{x}_0=(0,0)\): find the descent direction, set up the line search, run three stages of golden section on \(\alpha\in[0,1]\), and compare with the exact step.
Solution.
Step 1 — direction.
Step 2 — the line-search function. With \(\mathbf{x}(\alpha)=(4\alpha,\ 6\alpha)\):
Step 3 — three stages of golden section on \([0,1]\).
| Stage | \([a,b]\) | \(L\) | \(x_1\) | \(x_2\) | \(\phi_1\) | \(\phi_2\) | Discard |
|---|---|---|---|---|---|---|---|
| 1 | \([0.00000,\ 1.00000]\) | 1.00000 | 0.38197 | 0.61803 | 0.72447 | 0.72447 | tie — break either way (here, left) |
| 2 | \([0.38197,\ 1.00000]\) | 0.61803 | 0.61803 | 0.76393 | 0.72447 | 3.62233 | right |
| 3 | \([0.38197,\ 0.76393]\) | 0.38197 | 0.52786 | 0.61803 | 0.04037 | 0.72447 | right |
| — | \([0.38197,\ 0.61803]\) | 0.23607 |
Step 4 — the exact answer. \(\phi'(\alpha)=104\alpha-52=0\Rightarrow \alpha^{*}=0.5\), \(\phi(0.5)=13-26+13=0\).
The interval \([0.38197,\ 0.61803]\) contains \(0.5\) and its midpoint is exactly \(0.5\) ✓.
which is the exact minimum of \(f\), reached in one steepest-descent step.
Interpretation — two points.
- The tie at stage 1 is not an accident. \(\phi\) is symmetric about \(\alpha=0.5\), and the golden probes \(0.382\) and \(0.618\) are symmetric about \(0.5\) too, so the two values are equal. A tie is resolved either way without harm, since the minimum lies in the overlap; a good implementation should test for it explicitly rather than let floating-point noise decide.
- One step sufficed because the contours of \(f\) are perfect circles, so the negative gradient points straight at the minimum. Lesson 42 shows that as soon as the contours become elongated ellipses, steepest descent starts to zig-zag and needs many steps — the failing that conjugate gradient methods were invented to cure.
Problem 5 — Choosing among the elimination methods¶
A colleague must minimise each of the following. Recommend a method for each, with a reason.
| Case | Recommendation | Reason |
|---|---|---|
| (a) Smooth cheap analytic function, high accuracy wanted | Interpolation (L41), safeguarded by golden section | Quadratic/Newton methods converge superlinearly on smooth functions; the safeguard covers the cases where they diverge |
| (b) Each evaluation is a 6-hour simulation; budget 12 runs | Fibonacci with \(n=12\) | With a hard, known budget, the optimal method is worth the inconvenience: \(L_0/F_{12}=L_0/233\) against golden section's \(L_0/198\) |
| (c) Function known only from a table of measurements | Exhaustive over the tabulated points | No derivatives exist and the points are fixed; nothing else applies |
| (d) Function possibly multi-modal | Coarse exhaustive first, then golden section on each promising bracket | Only exhaustive search does not assume unimodality; refine locally afterwards |
| (e) Line search inside a steepest-descent code | Inexact search (a few golden-section stages, or an Armijo backtrack) | The direction changes next iteration, so precision here is wasted |
| (f) Noisy function (measurement error \(\pm0.01\)) | Golden section, stopped when the interval reaches the noise scale | Never resolve below the noise: comparisons become meaningless. Dichotomous search is especially dangerous here |
The general rule. Match the method to the cost structure and the smoothness, not to a preference. The three questions to ask are: How expensive is one evaluation? Is the function smooth? Is it unimodal? The table above is simply those three questions applied six times.
40.5 Practice Problems¶
- Perform three stages of golden section on \(f(x)=(x-4)^{2}\) over \([0,10]\). (Answer: stage 1 \(x_1=3.81966\), \(x_2=6.18034\), \(f_1=0.03252<f_2=4.75388\), keep \([0,\ 6.18034]\); stage 2 \(f(2.36068)=2.68737>f(3.81966)=0.03252\), keep \([2.36068,\ 6.18034]\); stage 3 \(f(3.81966)=0.03252<f(4.72136)=0.52036\), keep \([2.36068,\ 4.72136]\))
- How many evaluations does golden section need to reduce \([10,\,60]\) to \(0.5\)? (Answer: \((0.618)^{n-1}\le0.01\), \(n-1\ge9.57\), so \(n=11\))
- Verify algebraically that \(\tau^{2}=1-\tau\) for \(\tau=(\sqrt5-1)/2\), and deduce \(1/\tau=\tau+1\).
- Show that golden section needs at most one more evaluation than Fibonacci for any accuracy target, using \(F_n\approx\phi^{n}/\sqrt5\).
- A golden-section search returns the interval \([2.88854,\ 3.11146]\). What is the best point estimate, and what is the maximum possible error? (Answer: midpoint \(3.00000\); maximum error \(L/2=0.11146\) — though the actual error here is zero)
40.6 Summary¶
- The golden ratio \(\tau=\dfrac{\sqrt5-1}{2}=0.618034\) is forced by the requirement \(\boxed{\tau^{2}=1-\tau}\) — that one probe be reusable at every stage, for ever.
- Probes go at \(0.382L\) and \(0.618L\) from the left end. After the first stage each iteration costs one evaluation.
- \(\boxed{L_n=(0.618)^{\,n-1}L_0}\), so \(n\ge1+\dfrac{\ln(\epsilon/L_0)}{\ln 0.618}\).
- Golden section is the limiting case of Fibonacci as \(n\to\infty\): about \(17\,\%\) worse per interval, which is at most one extra evaluation regardless of the target.
- In exchange it needs no advance choice of \(n\), no Fibonacci table, and has no degenerate final step — so it is the practical default.
- Both are exponential (\(c^{n}\)) where exhaustive search is linear (\(1/n\)): \(18\) evaluations against \(4999\) in Problem 3.
- The midpoint of the final interval is usually far more accurate than the interval width guarantees, but only the width is a guarantee.
- Never search below the noise level of the function, and inside a multivariable algorithm do not over-solve the line search.
Next lesson: L41 — Interpolation and gradient-based one-dimensional methods: quadratic fitting, Newton–Raphson and the secant method.
Practise now: unit4-nlp-search-lab.html → Golden Section Trace: watch the interval shrink by
\(0.618\) each stage, with the inherited probe highlighted and the running comparison against Fibonacci.