Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 38 · Getting Started

Local and Global Minima

Understand local and global minima, saddle points and why non-convex functions trap algorithms. Run code that finds different valleys from different starts.

When an algorithm walks downhill, where does it stop? At the bottom of a valley, but not always the deepest one. This lesson separates two ideas that beginners often mix up: a local minimum and a global minimum. The gap between them explains why general optimization is hard and why convex optimization is such a gift.

Definitions

Let f be an objective and X the feasible set.

  • x* is a global minimum if f(x*) ≤ f(x) for every feasible x.
  • x* is a local minimum if f(x*) ≤ f(x) for every feasible x in some small neighborhood around x* (say, within distance r > 0).

Every global minimum is local, but a local minimum can be worse than the global one. Picture a mountain range with many valleys: standing at the bottom of one valley, you cannot see whether another valley is deeper.

A related trap is the saddle point. There the slope is zero, but the point is a minimum in some directions and a maximum in others, like the middle of a horse saddle. The function f(x, y) = x² - y² has its flat spot at (0, 0): moving along x goes up, moving along y goes down.

A function with several valleys

Take f(x) = x⁴ - 3x² + x. It has two valleys of different depth. Let us find where each starting point ends up with a simple downhill walk (gradient descent, which you will study properly in a later chapter). The derivative is f'(x) = 4x³ - 6x + 1.

Python Different starts, different valleys

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.

You should see two different end points. The one on the left has the lower function value: that is the global minimum. The one on the right is only a local minimum, yet the algorithm is perfectly happy to stop there because the slope is zero.

Plotting the trap

Python The two valleys

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 plot shows a deeper valley on the left and a shallower one on the right, separated by a small hill. No downhill algorithm that starts on the right side can climb the hill to reach the better valley.

Why convexity changes everything

A function is convex if the line segment between any two points on its graph never dips below the graph. You will define this carefully in the convex sets lesson and the lessons after it. The consequence is dramatic:

For a convex function on a convex feasible set, every local minimum is a global minimum.

A convex bowl, like f(x) = x², has exactly one valley. Starting anywhere and walking downhill brings you to the global answer. That is why researchers try so hard to express problems in convex form.

Python A convex bowl has no false valleys

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.

Every start reaches -1.5, the unique minimum (the derivative 2x + 3 is zero there).

Practical advice for non-convex problems

When a problem is not convex you often cannot prove you found the global minimum. Common coping strategies:

  • Multiple starts. Run the algorithm from many random points and keep the best result.
  • Smoothing or relaxation. Replace the hard problem with a nearby convex one and use its answer as a start.
  • Accept "good enough". In deep learning, loss surfaces are non-convex, yet local minima found by gradient methods work well in practice.

Zero gradient is only a necessary clue. A point with zero gradient can be a minimum, a maximum or a saddle. You need more information (second derivatives or convexity) to decide.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A point that is lower than all its neighbors but not lower than every point is a

    Local minima only need to beat nearby points; the global minimum beats all feasible points.
  2. 2. For f(x, y) = x² - y², the point (0, 0) is

    The gradient (2x, -2y) vanishes at the origin, but f increases along x and decreases along y.
  3. 3. Which statement is true for convex functions on convex sets?

    Convexity rules out false valleys, which is the key reason convex problems are easy.
  4. 4. A common strategy for non-convex problems is to

    Multiple starts give several chances to land in a deep valley.

Summary

  • A global minimum beats every feasible point; a local minimum beats only nearby points.
  • Saddle points have zero slope but are neither minima nor maxima.
  • Downhill algorithms can get stuck in local minima of non-convex functions.
  • For convex problems, every local minimum is global.

Next: Gradients and Hessians