Bracketing

Chapter 1: Unimodality

A function is unimodal on an interval [a, b] if there is a unique minimizer x* in [a, b] such that f is strictly decreasing on [a, x*] and strictly increasing on [x*, b].

Given a unimodal function and a bracket [a, b], evaluate at two interior points x₁ < x₂:

• If f(x₁) < f(x₂): the minimum is in [a, x₂] — discard [x₂, b]
• If f(x₁) > f(x₂): the minimum is in [x₁, b] — discard [a, x₁]

The key question is: where should you place x₁ and x₂ to shrink the interval as fast as possible?

Chapter 2: Finding an Initial Bracket

Before we can shrink a bracket, we need to find one. The textbook presents an expanding search: start with a point and a step size, then keep expanding in the downhill direction until you overshoot the minimum.

pseudocode
function bracket_minimum(f, x; s=1e-2, k=2.0)
  a, ya = x, f(x)
  b, yb = a + s, f(a + s)
  if yb > ya
    a, b = b, a       # swap: go the other direction
    s = -s
  end
  while true
    c, yc = b + s, f(b + s)
    if yc > yb
      return (a, c)    # bracket found: ya > yb and yc > yb
    end
    a, ya, b, yb = b, yb, c, yc
    s *= k             # expand step size
  end

The expansion factor k = 2 doubles the step at each iteration. This ensures the bracket is found in O(log(distance to minimum)) steps, but the resulting bracket may be much wider than necessary — hence the need for shrinking algorithms.

Chapter 3: Fibonacci Search

If you know in advance exactly how many function evaluations you can afford (say n), Fibonacci search is provably optimal — it shrinks the interval as much as possible for n evaluations.

The placement of evaluation points is determined by Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21, .... After n evaluations, the interval shrinks by a factor of 1/F_n.

The catch: you must decide n in advance. If you don't know your budget ahead of time, the golden section search (next chapter) is more practical.

Chapter 4: Golden Section Search

The golden section search is the limit of Fibonacci search as n → ∞. It places evaluation points at the golden ratio φ = (1 + √5) / 2 ≈ 1.618.

At each step, the interval shrinks by a factor of 1/φ ≈ 0.618. The magic property: the remaining point from the previous iteration is already in the right position for the next iteration, so you only need one new function evaluation per step.

pseudocode
function golden_section_search(f, a, b; n)
  ρ = (√5 - 1) / 2
  d = ρ * (b - a)
  x1, x2 = a + d, b - d      # symmetric placement
  y1, y2 = f(x1), f(x2)
  for i = 1 to n - 2
    if y1 < y2
      a, x2, y2 = x2, x1, y1
      d *= ρ
      x1 = a + d
      y1 = f(x1)
    else
      b, x1, y1 = x1, x2, y2
      d *= ρ
      x2 = b - d
      y2 = f(x2)
  return y1 < y2 ? x1 : x2

Chapter 5: Quadratic Fit Search

Golden section search ignores the function values — it only uses comparisons. Quadratic fit search does better by fitting a parabola through three points and jumping to its minimum.

Given three bracket points (a, f(a)), (b, f(b)), (c, f(c)), fit a quadratic q(x) = αx² + βx + γ and compute its minimizer x* = −β/(2α).

The danger: if the function is not well-approximated by a quadratic (e.g., near a kink or in a flat region), the quadratic fit can give a terrible prediction. Robust implementations combine quadratic fit with golden section as a fallback.

Chapter 6: Shubert-Piyavskii Method

What if you want to find the global minimum, not just a local one? The Shubert-Piyavskii method can do this — but it requires the function to be Lipschitz continuous with a known constant L:

The Lipschitz constant L bounds how fast the function can change. Given L and a set of evaluated points, we can construct a sawtooth lower bound: from each evaluated point, draw lines of slope ±L. The function must lie above this sawtooth.

The catch: you need to know L. Overestimating L makes the search conservative (slow). Underestimating L means you might miss the global minimum. In practice, L is often unknown.

Chapter 7: Bisection Method

If you have access to the derivative f'(x), you can use the bisection method. The idea: at the midpoint m of [a, b], evaluate f'(m):

• If f'(m) > 0: the function is increasing at m, so the minimum is to the left → set b = m
• If f'(m) < 0: the function is decreasing at m, so the minimum is to the right → set a = m
• If f'(m) = 0: found the minimum!

Each step halves the interval, giving a shrinkage factor of 0.5 per evaluation (better than golden section's 0.618). The tradeoff: you need the derivative, which is an extra cost.

Chapter 8: Golden Section Simulator

Watch golden section search in action. The canvas below shows a unimodal function with the current bracket [a, b] and the two evaluation points. Click "Step" to advance the algorithm.

Chapter 9: Summary