The Quest for the Best: An Introduction to Optimization

In our previous guides, we were detectives hunting for "zero"—the points where a function crosses the x-axis. This is called root finding. But often in science, business, and engineering, we face a different, arguably more important challenge: finding the function's absolute best value. This could be a maximum (like maximizing profit) or a minimum (like minimizing cost or error). This entire field is known as optimization.

Imagine you are an engineer trying to find the angle for a robotic arm that uses the least amount of energy to complete a task. Or a data scientist finding the perfect parameter that minimizes a machine learning model's prediction error. In both cases, you are hunting for a minimum value.

This masterclass explores two legendary algorithmsAn algorithm is a set of step-by-step instructions for solving a problem or accomplishing a task. for one-dimensional, unconstrained optimization. They represent two fundamentally different philosophies for finding the bottom of a valley:

• Golden Section Search: A safe, reliable bracketingBracketing methods work by keeping the solution trapped within an ever-shrinking interval. They are slow but guaranteed to work. method that slowly but surely corners the minimum. It's the wise hiker who zig-zags down the valley, always keeping the lowest point in sight.
• Newton's Method: A blazing-fast open methodOpen methods use a single guess (or two) to project a new, better guess. They are extremely fast but can sometimes fail spectacularly if the initial guess is poor. that uses calculus to take daring leaps towards the minimum. It's the daredevil in a wingsuit, diving straight for the bottom.

Understanding both is key to becoming a master of numerical methods, as each has its own strengths, weaknesses, and ideal use cases.

Golden Section Search: Nature's Optimal Strategy

The Golden Section Search is the elegant and more flexible cousin of the Fibonacci Search. It's a bracketing method that is guaranteed to find the minimum of a function, provided that the function is unimodal.

A unimodalFrom 'uni' (one) and 'modus' (mode). A unimodal function has only one valley (a minimum) within a given interval. It consistently decreases, hits the minimum, and then consistently increases. function is one that, within our chosen interval $[a, b]$, has only one valley. This property is vital because it allows us to discard parts of our search interval with absolute confidence, knowing the minimum cannot possibly be in the section we're throwing away.

The Power of the Golden Ratio

What makes this method so special is its use of the famous Golden Ratio, $\phi$ (phi), which is approximately 1.618. This irrational number has fascinated mathematicians for centuries and appears unexpectedly in nature, art, and architecture.

In our case, it provides the mathematically optimal constant ratio to shrink our search interval at every step. Instead of pre-calculating a list of Fibonacci numbers, we simply place two interior test points, $x_1$ and $x_2$, using a fixed proportion related to the Golden Ratio. The key is that after we discard a section, one of our old test points magically becomes a new test point in the new, smaller interval, meaning we only need **one new function evaluation per iteration**. This makes the method incredibly efficient.

Newton's Method for Optimization: The Rocket-Powered Descent

If Golden Section Search is the reliable hiker, Newton's Method is the rocket-powered daredevil. It doesn't bother with bracketing; it uses the power of calculus to take huge, intelligent leaps directly toward the minimum.

A New Goal, A New Formula

We know from calculus that the minimum (or maximum) of a function occurs where its slope is zero. In other words, we are looking for the point $x$ where the first derivative is zero: $f'(x) = 0$.

This brilliantly transforms our optimization problem into a root-finding problem! We can now use the Newton's Method for root finding that we learned previously, but instead of applying it to our original function $f(x)$, we apply it to its derivative, $f'(x)$.

Recall the original Newton's formula for a function $g(x)$: $x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)}$. If we set our target function to be $g(x) = f'(x)$, then its derivative is $g'(x) = f''(x)$ (the second derivative). Substituting these in gives us the powerful Newton's Method formula for optimization:

The intuition is beautiful: the first derivative ($f'$) tells us the slope (are we going downhill?), and the second derivative ($f''$) tells us the curvatureCurvature measures how sharply a curve is bending. For optimization, the second derivative tells us if our valley is wide and flat or narrow and steep. (how steep is the valley?). By using both pieces of information, the algorithm creates a parabolic model of the valley at its current guess and then jumps directly to the bottom of that parabola.

Convergence and Catastrophic Failure

When Newton's method works, it exhibits blazing-fast quadratic convergence—the number of correct digits roughly doubles at every step. However, it's a high-risk, high-reward strategy. It can fail spectacularly if:

• The second derivative $f''(x)$ is zero (an inflection pointA point on a curve where the curvature changes sign (from concave up to concave down, or vice versa). At this point, the second derivative is zero.), causing division by zero.
• The initial guess is poor, causing the algorithm to diverge and shoot off to infinity.
• It accidentally converges to a maximum instead of a minimum if it starts in a region where the function is concave down.

Solving Numerical Problems: A Step-by-Step Guide

Problem 1: Manual Golden Section Search

Question: Perform the first two iterations of the Golden Section Search to find the minimum of $f(x) = x^2 - 4x + 5$ on the interval $[0, 5]$.

Problem 2: Manual Newton's Method for Optimization

Question: Perform the first two iterations of Newton's Method to find the minimum of $f(x) = e^x - 4x$ starting at $x_0 = 1$.

Test Your Intuition!