Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 68 ยท Derivatives

Unimodal and Bimodal Functions

Learn unimodal and bimodal functions, why one peak makes optimisation easy, and how ternary and golden-section search find a minimum without derivatives.

Imagine tuning the speed of a conveyor belt to minimise energy per item. Too slow wastes time, too fast wastes power, and somewhere between the two is the best setting. If the energy curve has a single valley, finding that setting is easy: you can home in on it with nothing but measurements. If the curve has two valleys, a search can quietly settle into the wrong one.

Whether a function has one turning point or several is the dividing line between easy and hard one-dimensional optimisation. This lesson names the two cases, unimodal and bimodal (more generally multimodal), and then teaches two derivative-free search methods that rely on unimodality: ternary search and golden-section search. It builds on Applications of Derivatives and complements the root-finding methods in Finding Roots and Interpolating Data.

What unimodal means

A function on an interval is unimodal if it has exactly one "mode", one place where its trend reverses. For a minimum search, that means:

There is a point x* such that f is strictly decreasing to the left of x* and strictly increasing to the right of it.

For a maximum, swap decreasing and increasing. Unimodal does not require differentiable or smooth: f(x) = |x| + 0.5x is unimodal even though it has a corner. It does not require convexity either. The key consequence is a simple fact about comparing two points. Pick x1 < x2 inside the interval:

  • If f(x1) < f(x2), the minimum cannot lie to the right of x2.
  • If f(x1) > f(x2), the minimum cannot lie to the left of x1.

Each comparison lets you throw away part of the interval without any derivative. That is the whole idea behind the search methods below.

A bimodal function has two local extrema of the same kind (two valleys or two peaks), and a multimodal one has more. The same word is used for probability densities with two humps, such as the distribution of readings from a sensor that sometimes sticks. In optimisation, the bad news is that comparing two points no longer tells you which side holds the global best: the better of two sampled values may sit in the smaller valley.

Python Counting the turning points of some functions

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.

Three of the five have a single direction change on [-3, 3] (the parabola, the Gaussian bump and the corner function), so each is unimodal there. The cubic x**3 - 3x rises, falls, then rises again, and sin(3x) oscillates six times. Note that "unimodal" always refers to an interval: x**3 - 3x is unimodal on [-0.5, 3], where it has just one turn, but not on [-3, 3]. You can find the turning points exactly by solving f'(x) = 0, as in the derivative-applications lesson, but that needs a derivative and often a root solver. The search methods avoid both.

Given a unimodal f on [a, b], split the interval into three equal parts using m1 = a + (b - a)/3 and m2 = b - (b - a)/3. Compare f(m1) and f(m2) (for a minimum): if f(m1) < f(m2), keep [a, m2]; otherwise keep [m1, b]. Each round multiplies the interval length by 2/3 at the cost of two new evaluations. Stop when the interval is shorter than your tolerance.

Ternary search wastes work: it discards both of its old evaluations each round. Golden-section search places the two interior points at the fractions 1 - r and r of the interval, where r = (sqrt(5) - 1)/2 = 0.618.... This special ratio satisfies r**2 = 1 - r, so after the interval shrinks, one of the old interior points lands exactly where a new interior point is needed. Only one new evaluation per round is required, and the interval shrinks by the factor 0.618 each time. This is the best you can do with sequential comparisons of this kind, and it is the one-dimensional engine inside many real optimisers.

Python Ternary versus 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.

Both methods locate the minimum near x = 1.0521, which you can confirm from f'(x) = 2(x - 1.3) + cos(x) = 0. Ternary search used 78 function evaluations, golden-section only 35, for the same 1e-6 tolerance. If each evaluation is an expensive experiment or simulation, that saving matters a great deal. The second part maximises x * exp(-x) by minimising its negative and finds the peak at x = 1 with value 1/e = 0.367879. One caution: search methods shrink the interval to about the square root of machine precision (around 1e-8 for double precision), because near a smooth minimum the function is nearly flat and two values differ below round-off. Do not ask for a tolerance much smaller than that.

When the function is bimodal

Run a unimodal search on a bimodal function and you still get an answer: a local minimum, with no warning that a better one exists. The method follows the comparisons, and the comparisons are only reliable within a region that has a single valley.

Python A bimodal function: where you search matters

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.

The function has two valleys at x = -1.165 (depth -2.1335) and x = 1.0642 (depth -1.0166) with a hill between them at x = 0.1008. On the whole interval the search happens to land in the deeper left valley, but that is luck; start with the interval [0, 2] and it reports the shallow right valley, with no sign of anything better. Three practical remedies:

  • Bracket first. Evaluate f on a coarse grid, find where the function dips, and run the search inside each bracket that holds a valley. Compare the results.
  • Use derivatives when you have them: all critical points are roots of f', and the second derivative classifies each as a valley or hill.
  • Restart a local method from many starting points (multi-start) and keep the best, which is the standard approach for harder, higher-dimensional problems such as those in Optimization in Several Variables.

Common slips

  • Applying ternary or golden-section search without checking unimodality on the chosen interval.
  • Plateaus: if f is constant over a flat stretch, comparisons of equal values can send the search the wrong way. Strict monotonicity on each side is part of the definition.
  • Noisy measurements. If f is measured with noise, two close points compare almost randomly; stop when the interval shrinks to the noise level.
  • Treating "bimodal" as a property of the whole function instead of the interval you search.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which description defines a function that is unimodal (for a minimum) on [a, b]?

    Unimodal means a single reversal of trend. It need not be smooth or convex.
  2. 2. In a minimum search on a unimodal f with x1 < x2, you find f(x1) < f(x2). What can you discard?

    Because f rises from the minimum onward, a lower value at x1 means the minimum cannot lie beyond x2.
  3. 3. Why is golden-section search cheaper than ternary search?

    The ratio 0.618 makes one interior point of the smaller interval coincide with an old interior point, so only one new evaluation is needed per round.
  4. 4. A golden-section search on a bimodal function returns x = 1.06. What can you conclude?

    Comparisons are only trustworthy within a single valley, so the result is a local minimum. Bracket the function on a grid or restart from several intervals.

Summary

  • A unimodal function has one trend reversal on the interval; a bimodal or multimodal function has several.
  • With a unimodal function, comparing f(x1) and f(x2) lets you discard part of the interval without derivatives.
  • Ternary search shrinks the interval by 2/3 for two evaluations; golden-section search shrinks it by 0.618 for one.
  • To maximise, minimise -f; do not demand a tolerance below about 1e-8.
  • On multimodal functions, a bracketing scan, derivative information or multi-start restarts are needed to find the global optimum.

Next: Linearization and Newton's Method.