Lesson 39: The Fibonacci Search Method¶
39.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- State the Fibonacci sequence and its role in interval reduction.
- Derive the placement rule \(L_2^{*}=\dfrac{F_{n-2}}{F_n}L_0\) and the reduction \(L_n=\dfrac{L_0}{F_n}\).
- Execute the algorithm by hand, reusing one point at every stage.
- Handle the degenerate final step with an \(\varepsilon\)-perturbation.
- Explain in what sense Fibonacci search is optimal, and what it costs.
39.2 The Idea¶
Lesson 38 showed that reusing function values is what makes a line search efficient. Fibonacci search pushes that idea to its limit: at every stage after the first, exactly one of the two probe points is inherited from the previous stage, so each stage costs only one new evaluation.
The question it answers is sharp:
Given exactly \(n\) function evaluations, where should they be placed to guarantee the smallest possible final interval, whatever the function (assumed unimodal)?
Kiefer proved in 1953 that the answer involves the Fibonacci numbers, and that no method can do better. That optimality is what earns the method its place in the course, even though golden section (Lesson 40) is more convenient in practice.
The Fibonacci sequence¶
| \(n\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(F_n\) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 |
The ratio \(F_{n-1}/F_n\) tends to the golden ratio \(\dfrac{\sqrt5-1}{2}=0.618034\dots\), which is the bridge to Lesson 40.
39.3 The Algorithm¶
Inputs: interval \([a,b]\), unimodal \(f\), and the total number of evaluations \(n\) — chosen in advance (this is the method's one real drawback).
Step 1. With \(L_0=b-a\), place two points symmetrically: $\(x_1=a+\frac{F_{n-2}}{F_n}L_0,\qquad x_2=a+\frac{F_{n-1}}{F_n}L_0\)$ Note \(x_1\) is as far from \(a\) as \(x_2\) is from \(b\), because \(\dfrac{F_{n-2}}{F_n}+\dfrac{F_{n-1}}{F_n}=1\).
Step 2. Compare and eliminate (unimodality, Lesson 36): - If \(f(x_1)<f(x_2)\): the minimum lies in \([a,x_2]\). Discard \([x_2,b]\); \(x_1\) survives as the new right-hand probe. - If \(f(x_1)\ge f(x_2)\): the minimum lies in \([x_1,b]\). Discard \([a,x_1]\); \(x_2\) survives as the new left-hand probe.
Step 3. Place one new point symmetrically to the survivor in the reduced interval, using the next Fibonacci ratio down. Repeat.
The reduction achieved¶
At stage \(k\) the interval has length
because \(F_0=1\). The reduction is exponential in \(n\): since \(F_n\approx\phi^{n}/\sqrt5\) with \(\phi=1.618\), each extra evaluation shrinks the interval by a factor of about \(1.618\).
The degenerate final step¶
At the last stage the two probes coincide at the midpoint, because \(F_1/F_2=1/2\). No comparison is then possible. The standard remedy:
\(\varepsilon\)-perturbation. Take \(x_1=x_m\) and \(x_2=x_m+\varepsilon\) for a small \(\varepsilon>0\) and compare. This decides which half survives, at the cost of a final interval very slightly larger than \(L_0/F_n\).
How to choose n¶
Given a required accuracy \(\epsilon\), choose the smallest \(n\) with
39.4 Solved Problems¶
The running example is again \(f(x)=x^{2}+\dfrac{54}{x}\) on \([1,5]\), exact minimum \(x^{*}=3\), \(f=27\).
Problem 1 — A complete Fibonacci search¶
Minimise \(f\) on \([1,5]\) with \(n=6\) evaluations.
Solution. \(L_0=4\); \(F_6=13\), \(F_5=8\), \(F_4=5\), \(F_3=3\), \(F_2=2\), \(F_1=1\).
Stage 1.
\(f_1\ge f_2\Rightarrow\) discard \([1,\,2.53846]\). New interval \([2.53846,\ 5]\), \(L=2.46154\), and \(x_2=3.46154\) survives as the left probe.
Stage 2. New right probe \(=2.53846+\dfrac{F_4}{F_5}(2.46154)=2.53846+\dfrac{5}{8}(2.46154)=4.07692\).
\(f_1<f_2\Rightarrow\) discard \([4.07692,\,5]\). New interval \([2.53846,\ 4.07692]\), \(L=1.53846\).
Stage 3. New left probe \(=2.53846+\dfrac{F_2}{F_4}(1.53846)=2.53846+\dfrac{2}{5}(1.53846)=3.15385\).
\(f_1<f_2\Rightarrow\) discard \([3.46154,\ 4.07692]\). New interval \([2.53846,\ 3.46154]\), \(L=0.92308\).
Stage 4. New left probe \(=2.53846+\dfrac{F_1}{F_3}(0.92308)=2.53846+\dfrac{1}{3}(0.92308)=2.84615\).
\(f_1\ge f_2\Rightarrow\) discard \([2.53846,\ 2.84615]\). New interval \([2.84615,\ 3.46154]\), \(L=0.61538\).
Stage 5 — the degenerate step. Both probes now fall at \(3.15385\). Perturb:
The left value is smaller, so discard the right: final interval \([2.84615,\ 3.15485]\).
Check. \(L_0/F_6=4/13=0.30769\), and the \(\varepsilon=0.001\) perturbation accounts for the difference ✓. The true minimum \(x^{*}=3\) is comfortably inside.
Summary table.
| Stage | Interval | \(L\) | \(x_1\) | \(x_2\) | \(f_1\) | \(f_2\) | Discard |
|---|---|---|---|---|---|---|---|
| 1 | \([1.00000,\ 5.00000]\) | 4.00000 | 2.53846 | 3.46154 | 27.71652 | 27.58225 | left |
| 2 | \([2.53846,\ 5.00000]\) | 2.46154 | 3.46154 | 4.07692 | 27.58225 | 29.86657 | right |
| 3 | \([2.53846,\ 4.07692]\) | 1.53846 | 3.15385 | 3.46154 | 27.06870 | 27.58225 | right |
| 4 | \([2.53846,\ 3.46154]\) | 0.92308 | 2.84615 | 3.15385 | 27.07357 | 27.06870 | left |
| 5 | \([2.84615,\ 3.46154]\) | 0.61538 | 3.15385 | \(3.15385+\varepsilon\) | 27.06870 | 27.06958 | right |
| — | \([2.84615,\ 3.15485]\) | 0.30869 |
Interpretation. Read down the \(L\) column: \(4,\ 2.46,\ 1.54,\ 0.92,\ 0.62,\ 0.31\). Each is \(\dfrac{F_{n-k}}{F_n}L_0\) — the ratios \(\tfrac{13}{13},\tfrac{8}{13},\tfrac{5}{13},\tfrac{3}{13}, \tfrac{2}{13},\tfrac{1}{13}\) — and consecutive lengths are in the ratio \(\approx0.618\). Note in the \(x_1,x_2\) columns how each stage inherits one probe from the line above: only one new evaluation is ever made.
Problem 2 — Choosing n for a required accuracy¶
An engineer must locate a minimum on \([0,\,100]\) to within \(\pm0.5\) (an interval of \(1.0\)). How many evaluations are needed, and what if the interval were \([0,\,1000]\)?
Solution.
Case 1. Require \(\dfrac{100}{F_n}\le1\), i.e. \(F_n\ge100\). From the table, \(F_{10}=89<100\) and \(F_{11}=144\ge100\).
Case 2. Require \(F_n\ge1000\): \(F_{15}=987<1000\), \(F_{16}=1597\ge1000\).
Interpretation. A tenfold larger search region costs only five extra evaluations. Because \(F_n\sim\phi^{n}/\sqrt5\), the requirement is \(n\approx\log_\phi(L_0/\epsilon)\) — logarithmic in the size of the problem. Doubling the accuracy demand costs about \(1.44\) evaluations; a hundredfold larger interval costs about \(10\).
This is why elimination methods remain competitive: their cost grows with the logarithm of the required precision, not with the precision itself. Compare exhaustive search, which would need \(2(100)/1-1=199\) evaluations for Case 1 and \(1999\) for Case 2.
Problem 3 — A second worked example¶
Minimise \(f(x)=x^{2}-6x+9\) on \([0,10]\) with \(n=5\) evaluations.
Solution. \(L_0=10\); \(F_5=8\), \(F_4=5\), \(F_3=3\), \(F_2=2\), \(F_1=1\). (Exact minimum: \(f=(x-3)^2\), so \(x^{*}=3\).)
Stage 1. \(x_1=0+\dfrac{3}{8}(10)=3.75\), \(x_2=0+\dfrac{5}{8}(10)=6.25\).
\(f_1<f_2\Rightarrow\) discard \([6.25,10]\). New interval \([0,\ 6.25]\), \(L=6.25\); \(x_1=3.75\) survives as the right probe.
Stage 2. New left probe \(=0+\dfrac{2}{5}(6.25)=2.5\).
\(f_1<f_2\Rightarrow\) discard \([3.75,\ 6.25]\). New interval \([0,\ 3.75]\), \(L=3.75\).
Stage 3. New left probe \(=0+\dfrac{1}{3}(3.75)=1.25\).
\(f_1\ge f_2\Rightarrow\) discard \([0,\ 1.25]\). New interval \([1.25,\ 3.75]\), \(L=2.5\).
Stage 4 — degenerate. Both probes fall at \(2.5\); perturb to \(2.5\) and \(2.501\):
The right value is smaller, so discard the left: final interval \([2.5,\ 3.75]\).
Interpretation. The final interval contains \(x^{*}=3\), but is \(1.25\) wide — the method guarantees only \(L_0/F_n\), and with \(n=5\) that is all one can demand. Note the \(\varepsilon\)-test at stage 4 was genuinely informative: the two values differ by \(0.001\), and had \(\varepsilon\) been smaller than the noise in evaluating \(f\), the decision would have been a coin toss. Choose \(\varepsilon\) comfortably above the precision of your function evaluation, but far below the required accuracy.
Problem 4 — In what sense is Fibonacci search optimal?¶
State and justify the optimality property.
Solution.
Theorem (Kiefer, 1953). Among all sequential search methods that use exactly \(n\) function evaluations and are guaranteed to bracket the minimum of any unimodal function, Fibonacci search achieves the smallest possible final interval, namely \(L_0/F_n\). No method can do better.
Why the Fibonacci numbers appear. Work backwards. With \(1\) evaluation left the best achievable final interval, relative to the current one, is a factor of \(1\) (nothing can be resolved). With \(2\) evaluations the interval can be halved, so the achievable factor is \(\tfrac12\); with \(3\) evaluations, \(\tfrac13\); then \(\tfrac15\), \(\tfrac18\), \(\tfrac1{13}\) — the Fibonacci denominators.
The recursion arises because, at each stage, the surviving interval must be splittable so that the inherited point falls exactly where the next stage wants a probe. Writing \(L_k\) for the interval with \(k\) evaluations remaining, symmetry forces
which is precisely the Fibonacci recursion. The initial placement \(F_{n-2}/F_n\) is then the unique choice that makes every subsequent inheritance work out.
The price of optimality. \(n\) must be fixed before the search starts, because the first placement depends on \(F_{n-2}/F_n\). If after eight evaluations you decide you want more accuracy, you cannot simply continue — the ratios were computed for the old \(n\). Golden section (Lesson 40) gives up about one evaluation in exchange for removing exactly this restriction, which in practice is almost always the better trade.
Problem 5 — Fibonacci as a line search inside a bigger algorithm¶
In minimising \(f(x_1,x_2)=x_1^{2}+2x_2^{2}\) from \(\mathbf{x}_0=(4,2)\) along the steepest-descent direction, a line search must minimise \(\phi(\alpha)=f(\mathbf{x}_0-\alpha\nabla f)\). Set up the one-dimensional problem, bracket it and state what Fibonacci search would return.
Solution.
Step 1 — the direction.
Step 2 — the one-dimensional function.
Step 3 — bracket. \(\phi(0)=24\), \(\phi(0.25)=12-32+24=4\), \(\phi(0.5)=48-64+24=8\). Decrease then increase, so the minimum is bracketed by \([0,\ 0.5]\).
Step 4 — what Fibonacci search returns. The exact answer is
With \(n=8\) evaluations on \([0,0.5]\), Fibonacci guarantees a final interval of \(L_0/F_8=0.5/34=0.0147\), so \(\alpha\) would be located to about \(\pm0.007\) — ample, since the next outer iteration will recompute the direction anyway.
Interpretation — two lessons about line searches inside larger algorithms.
- The inner problem is always one-dimensional, however many variables the outer problem has. That is why Lessons 38–41 matter far beyond their apparent scope.
- Do not over-solve it. Spending \(20\) evaluations to pin \(\alpha\) to eight decimal places is wasted, because the direction \(\mathbf{d}_k\) will change at the next outer iteration. Practical codes use inexact line searches (Armijo/Wolfe conditions) that stop as soon as the step gives "sufficient decrease". Precision in the inner loop is only worth what the outer loop can use.
39.5 Practice Problems¶
- Minimise \(f(x)=x^{2}+2x\) on \([-3,\,5]\) with \(n=5\). (Answer: \(L_5=8/8=1\); the final interval contains the exact minimum \(x^{*}=-1\))
- How many evaluations are needed to reduce \([2,\,10]\) to \(0.1\)? (Answer: \(F_n\ge80\), so \(F_{10}=89\) gives \(n=10\))
- Show that \(\dfrac{F_{n-2}}{F_n}+\dfrac{F_{n-1}}{F_n}=1\), and explain why this makes the two probes symmetric about the centre of the interval.
- Compute \(L_k/L_{k-1}\) for \(k=1,\dots,6\) when \(n=10\), and comment on the trend. (Answer: \(55/89, 34/55, 21/34, 13/21, 8/13, 5/8 = 0.618, 0.618, 0.618, 0.619, 0.615, 0.625\) — converging on the golden ratio from below as \(k\) falls)
- Explain why \(n\) must be fixed in advance, and describe a situation in which that is a genuine obstacle.
39.6 Summary¶
- Fibonacci search places probes at \(\dfrac{F_{n-2}}{F_n}L_0\) and \(\dfrac{F_{n-1}}{F_n}L_0\) from the left end, then reuses one probe at every subsequent stage — one new evaluation per stage.
- \(L_k=\dfrac{F_{n-k}}{F_n}L_0\), so with \(n\) evaluations \(\boxed{L_n=\dfrac{L_0}{F_n}}\).
- The reduction is exponential: each extra evaluation shrinks the interval by a factor of \(\approx1.618\), so cost is logarithmic in the required precision.
- Choose \(n\) from \(F_n\ge L_0/\epsilon\).
- The final stage is degenerate (both probes at the midpoint) and needs an \(\varepsilon\)-perturbation. Choose \(\varepsilon\) above the noise floor of \(f\) but well below the target accuracy.
- Kiefer's theorem: Fibonacci search is optimal — no \(n\)-evaluation method guarantees a smaller final interval on every unimodal function. The recursion \(L_k=L_{k-1}+L_{k-2}\) is forced by the requirement that each inherited point land exactly where the next stage needs it.
- The price is that \(n\) must be fixed in advance. Golden section (Lesson 40) trades roughly one evaluation for the freedom to stop whenever you like.
- Inside a multivariable algorithm, do not over-solve the line search: the direction changes at the next outer iteration anyway.
Next lesson: L40 — Golden section search: near-optimal, and free of the fixed-\(n\) restriction.
Practise now: unit4-nlp-search-lab.html → Fibonacci Trace: set \(n\) and watch each stage,
with the inherited probe highlighted and the interval ratios displayed against \(F_{n-k}/F_n\).