Recipe

Run Fibonacci search on a bracket

Use when: you have a unimodal f, a valid bracket [a,b], and a FIXED number of iterations n decided in advance, rather than an open-ended tolerance

Goal: the narrowest possible bracket achievable in exactly n function evaluations — the best any comparison-only method can guarantee for that budget

Taught in Fibonacci search

1. 1

   Fix the iteration budget n, then generate F_0,F_1,\dots,F_{n+1} using F_0=F_1=1 and F_k=F_{k-1}+F_{k-2}. Build this once, before the first iteration.

   Example

   For n=4: F_0,\dots,F_5 = 1,1,2,3,5,8.

   Why: every iteration's ratio comes from this one fixed sequence, so it only needs to be generated a single time for the whole run.

2. 2

   At iteration k (starting from k=0, with n-k iterations remaining), compute \rho_k=F_{n-k-1}/F_{n-k+1}, then x_1=a+\rho_k(b-a) and x_2=b-\rho_k(b-a) — golden-section search's own formulas, with \rho_k in place of the fixed \rho.

   Example

   k=0, n=4: \rho_0=F_3/F_5=3/8=0.375. Bracket [0,5]: x_1=0+0.375(5)=1.875, x_2=5-0.375(5)=3.125.

   Why: the Fibonacci recurrence F_{n-k-1}+F_{n-k-2}=F_{n-k} plays the same algebraic role golden-section search's \rho^2=1-\rho identity played, guaranteeing the surviving point is already correctly placed for the next, smaller bracket.

3. 3

   Compute f(x_1) and f(x_2).

   Example

   f(1.875)=1.015625, f(3.125)=2.265625. Since f(x_1)<f(x_2), keep [0,3.125] and carry x=1.875 forward.

   • f(x_1)<f(x_2) — the minimum lies in [a,x_2]; discard [x_2,b]; keep x_1.
   • f(x_1)>f(x_2) — the minimum lies in [x_1,b]; discard [a,x_1]; keep x_2.
   • f(x_1)=f(x_2) — the minimum lies in [x_1,x_2]; discard both outer pieces.

   Why: the same unimodality argument every bracketing method here relies on — whichever side loses the comparison cannot contain the minimum.

4. 4

   Increase k by 1, recompute \rho_k for the new, smaller bracket, and check which of its two candidate interior points matches the point already carried over — only the other one needs a fresh evaluation. Repeat Steps 2-3 this way until k=n-1, then report the final bracket's midpoint as the estimated minimizer.

   Example

   Iteration k=1: \rho_1=F_2/F_4=2/5=0.4. New bracket [0,3.125], width 3.125: candidates are 0+0.4(3.125)=1.25 and 3.125-0.4(3.125)=1.875 — the second matches the carried point, so only x=1.25 needs evaluating: f(1.25)=1.5625. Comparing to the carried value f(1.875)=1.015625: the carried point wins, so keep [1.25,3.125].

   • k<n-1 — compute \rho_k fresh for the new bracket and continue with the next iteration.
   • k=n-1 (the final iteration) — nudge one interior point by a small \epsilon before comparing, since \rho_{n-1}=F_0/F_2=1/2 would otherwise place both candidate points at the exact same midpoint.

   Why: reusing the survivor is Fibonacci search's whole efficiency payoff, exactly as it was for golden-section search — and being honest about the degenerate final iteration keeps the recipe from silently comparing two identical points.