A New Quest: The Hunt for the Minimum

In our previous guides, we were detectives hunting for "zero"—the points where a function crosses the x-axis. But often in science and engineering, we face a different, equally important challenge: finding the function's minimum value. This is the core of optimizationIn math and computer science, optimization is the process of finding the best possible solution from all available options, like finding the lowest point in a valley or the highest point on a hill..

Imagine you are an engineer designing a bridge. You have a function that describes the total cost based on the thickness of a steel beam. Too thin, and you need many expensive supports. Too thick, and the beam itself is expensive. Somewhere in between is a "sweet spot" that minimizes the cost. Or perhaps you're a data scientist tuning an AI model, and you have a function that measures its error. Your goal is to find the model parameter that makes this error as small as possible. You are hunting for the minimum.

This masterclass explores one of the most elegant and efficient methods for this task: the Fibonacci Search Method. It's a clever bracketing technique that, like the Bisection Method, is guaranteed to work, but it uses a surprising tool from nature to close in on the minimum with remarkable speed.

The Key Assumption: Unimodality

The Fibonacci search method is powerful, but it relies on one crucial assumption: the function must be unimodal on our search interval. This is a fancy word for a very simple idea.

A unimodalFrom 'uni' (one) and 'modus' (mode). A unimodal function has only one peak (a maximum) or one valley (a minimum) within a given interval. It doesn't go up and down multiple times. function is one that, within our chosen interval $[a, b]$, has only one valley (a minimum). The function consistently decreases until it hits the minimum, and then consistently increases afterwards. It doesn't have multiple wiggles or hills. This property is vital because it allows us to discard parts of our search interval with confidence, knowing the minimum cannot possibly be in the section we're throwing away.

The Secret Weapon: Nature's Numbering System

What makes this method so special is its use of the famous Fibonacci sequence. You've surely seen it before: you start with 1 and 1, and each subsequent number is the sum of the two preceding ones.

This sequence appears everywhere in nature, from the petals on a flower to the branching of trees. In our case, it provides the mathematically optimal way to place test points within an interval to shrink it as efficiently as possible when we've decided in advance how many times we're willing to check the function.

The core idea is to use ratios of these numbers to place two interior test points, $x_1$ and $x_2$, within our interval $[a, b]$. By comparing the function values $f(x_1)$ and $f(x_2)$, we can eliminate a portion of the interval. The true genius lies in the fact that on the next step, one of our old test points is perfectly positioned to be reused as a new test point, meaning we only need to perform one new function evaluation per iteration. This makes the method incredibly efficient when function evaluations are computationally expensive.

The Fibonacci Search Algorithm in Action

Let's break down the process into clear, repeatable steps.

1. Step 1: Define the Problem. Choose your function $f(x)$, your initial interval of uncertainty $[a, b]$, and—crucially—the total number of function evaluations, $N$, you're willing to perform.
2. Step 2: Generate Fibonacci Numbers. You'll need the sequence up to $F_N$.
3. Step 3: Place Initial Test Points. For the first iteration ($k=1$), calculate two interior points, $x_1$ and $x_2$, using a ratio of Fibonacci numbers. The distance from each endpoint is determined by the ratio $F_{N-k-1}/F_{N-k+1}$ (initially $F_{N-2}/F_N$).
4. Step 4: Evaluate and Reduce. Compare the function values at the interior points.
   • If $f(x_1) < f(x_2)$, the minimum must be in the left sub-interval. Our new interval becomes $[a, x_2]$, and our old $x_1$ becomes the new $x_1$ for this smaller interval.
   • If $f(x_1) > f(x_2)$, the minimum must be in the right sub-interval. Our new interval becomes $[x_1, b]$, and our old $x_2$ becomes the new $x_2$.
5. Step 5: Repeat. Continue for $N-1$ iterations. Each time, you'll only need to calculate one new interior point because the other is magically reused from the previous step.

Convergence Analysis: Optimal and Efficient

Like the Bisection Method, Fibonacci search is a bracketing method and is therefore guaranteed to converge to the minimum. Its real advantage lies in its efficiency.

For a fixed number of function evaluations $N$, the Fibonacci search method is the optimal search strategy. This means it produces the smallest possible final interval of uncertainty compared to any other search method that uses the same number of evaluations. The length of the final interval after $N$ evaluations is precisely:

The reduction ratio at each step approaches $\frac{1}{\phi} \approx 0.618$, where $\phi$ is the Golden Ratio. This means we are eliminating about 38% of the interval at every step, which is significantly better than other simple search methods.

Solving Numerical Problems: A Step-by-Step Guide

Problem 1: Manual Fibonacci Search Iterations

Question: Perform the first three iterations of the Fibonacci search method to find the minimum of $f(x) = x^2 - 10x + 2$ on the interval $[0, 8]$, assuming a total of $N=6$ evaluations are allowed.

Test Your Intuition!