Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 37 ยท Optimization and Eigenvalues

One-Dimensional Optimization: Golden Section and Brent

Find the minimum of a function of one variable without derivatives. Bracket, golden-section search, successive parabolic interpolation and Brent's method.

Optimization means finding the input that makes a function as small (or as large) as possible: the cheapest design, the best-fit parameter, the lowest energy. We begin with the simplest case, one variable, because the ideas carry over to many dimensions and because line searches inside bigger algorithms are exactly this problem.

Maximizing f is the same as minimizing -f, so we speak only of minimizing. At a smooth interior minimum f'(x) = 0, so you can reuse root finding on the derivative, but only if you can compute f'. The methods here need only function values.

Unimodal functions and bracketing

A function is unimodal on [a, b] if it decreases to a single minimum and then increases. For such a function, comparing values at two interior points c < d tells you which end to discard:

  • if f(c) < f(d) the minimum lies in [a, d];
  • otherwise it lies in [c, b].

Most methods first bracket the minimum: find three points a < m < b with f(m) < f(a) and f(m) < f(b). Then a minimum is guaranteed inside. Without a bracket you can only find local minima, and you may find none (a monotonic function).

Bisection for roots halves the interval each step. For minimizing, two new evaluations would be needed per step unless you are clever. Choose the interior points at fractions of the interval that reuse one old point after shrinking. The ratio that makes this work is the golden ratio phi = (1 + sqrt(5)) / 2:

c = b - (b - a) / phi, d = a + (b - a) / phi.

After discarding one end, one of the old interior points is exactly at a golden-section position of the new interval, so each iteration costs one new function evaluation and shrinks the interval by 1/phi ~ 0.618. The convergence is linear (each step multiplies the error by 0.618).

Python Golden-section search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Use it on a function you can plot first, to be sure it is unimodal on the interval.

The precision limit

Near a minimum f(x) ~ f(x*) + f''(x*)(x - x*)^2 / 2, so function values change like the square of the distance. Once |x - x*| is about sqrt(eps) (around 1e-8), changes in f fall below the rounding error and the comparisons become noise. A minimizer can therefore locate x* only to about the square root of machine precision, in contrast with root finding where full precision is possible. Setting tol smaller than about 1e-8 buys nothing.

Python Why x* is limited to ~1e-8

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Below about 1e-8 the computed difference is exactly zero: the function value cannot tell those points apart.

Parabolic interpolation

Smooth functions look like parabolas near a minimum. Given three points, fit a parabola and jump to its vertex:

x_new = b - ((b - a)^2 (f(b) - f(c)) - (b - c)^2 (f(b) - f(a))) / (2 ((b - a)(f(b) - f(c)) - (b - c)(f(b) - f(a))))

This is superlinear (order about 1.32) and usually far faster than golden section, but it can step outside the bracket or stall, like secant for roots.

Brent's method

Brent's method combines the two: parabolic steps when they behave, golden-section steps as a safe fallback, and bookkeeping that guarantees progress. It is the default for scalar minimization and what scipy.optimize.minimize_scalar uses.

Python minimize_scalar methods compared

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three find the same minimum; brent needs fewer evaluations than golden.

Local versus global minima

The methods find a minimum in the bracket, not necessarily the lowest. A function such as sin(3x) + (x - 2)^2 has several valleys. Strategies: plot the function; scan a grid for the best starting bracket; run from several starting points and compare; use global methods (differential_evolution, shgo) for rugged problems.

Python Scan, then refine

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For problems with more than one variable, see gradient descent and Newton's method.

Common mistakes

  • Starting without a bracket and calling the result "the minimum".
  • Asking for tol below sqrt(eps).
  • Assuming a local minimum is global.
  • Forgetting that minimize_scalar(method="bounded") ignores points outside bounds, even if the true minimum lies there.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. By what factor does golden-section search shrink the interval each iteration?

    Each step multiplies the interval length by 1/phi, about 0.618, with one new evaluation.
  2. 2. Why can a minimizer find x* only to about 1e-8 in double precision?

    Differences in f of size eps*|f| correspond to |x - x*| of about sqrt(eps).
  3. 3. Which method is the default scalar minimizer, combining parabolic and golden-section steps?

    Brent's method uses fast parabolic steps with golden-section safeguards.
  4. 4. What is a bracket for a minimum?

    That configuration guarantees a minimum lies inside for a continuous function.

Summary

  • Unimodality and bracketing guarantee a minimum in an interval.
  • Golden-section search is derivative-free, linear (0.618 per step) and robust; parabolic interpolation is faster; Brent combines them.
  • Locating x* is limited to about sqrt(eps) precision.
  • Plot and scan for global structure before polishing a local minimum.

Next: Gradient descent and Newton's method for optimization