Skip to content
Tutorials Center
My learning

Topics

Lesson 38 of 39 · Projects and Practice

Project: Gradient Descent on a Landscape

Build gradient descent from scratch, run it on a four-minimum landscape, draw the paths on a contour map and see how start point and step size matter.

In this project you will build a small optimizer, run it on a landscape with several valleys and explore how the result depends on where you start. It combines gradients, critical points and the Hessian test from this track.

The landscape

Himmelblau's function is a classic test problem:

Text
f(x, y) = (x² + y - 11)² + (x + y² - 7)²

It has four local minima (all with value 0), one local maximum and four saddle points. The minima are at (approximately) (3, 2), (-2.805, 3.131), (-3.779, -3.283) and (3.584, -1.848). The point (3, 2) is exact, since 9 + 2 - 11 = 0 and 3 + 4 - 7 = 0.

Step 1: the gradient

Differentiate with the chain rule. Let A = x² + y - 11 and B = x + y² - 7. Then f = A² + B² and

Text
∂f/∂x = 2A · 2x + 2B · 1 = 4xA + 2B
∂f/∂y = 2A · 1 + 2B · 2y = 2A + 4yB
Python Gradient check: formula against finite differences

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 last point is a minimum, so its gradient should be near zero.

Step 2: gradient descent

The update rule is p ← p - η ∇f(p). We add a safeguard: stop when the gradient is tiny, or after a maximum number of steps.

Python Descent paths from different starting points

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.

Each start slides into whichever valley is "downhill" from it. The boundaries between these basins of attraction run along the ridges and saddle points.

Step 3: which minimum do we reach?

You can map the basins by running descent from a grid of starting points and recording which of the four minima each run reaches. The result is a coloring of the plane.

Python Basins of attraction

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.

If a few cells stay uncolored, they have not converged in 2000 steps (near saddle points the gradient is small and progress is slow).

Step 4: step size and the Hessian

For a quadratic bowl, descent converges only when η < 2/λ_max, where λ_max is the largest eigenvalue of the Hessian. Himmelblau's function is not quadratic, but near a minimum it is almost so. Let us compute the Hessian eigenvalues at (3, 2) and use them to predict a safe step size.

The second derivatives, from the formulas above, are

Text
fxx = 4A + 8x² + 2        fyy = 4B + 8y² + 2        fxy = 4x + 4y

At (3, 2), A = B = 0, so fxx = 74, fyy = 34 and fxy = 20.

Python Hessian at the minimum and a safe step size

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 small steps settle on (3, 2) and a step beyond the limit fail to settle there.

Extensions to try

  1. Add momentum: keep a velocity v ← 0.9 v - η ∇f and update p ← p + v. Does it cross shallow ridges faster?
  2. Find the saddle points by solving ∇f = 0 with SymPy, then classify them with the Hessian test.
  3. Replace f by a function of your own, for example sin(x) cos(y) + 0.1(x² + y²), and map its basins.
  4. Make a random restart search: run descent from 50 random points and report the lowest value found.

Gradient descent only finds a local minimum. On landscapes with many valleys, the answer depends on the starting point, which is why practical optimizers use restarts, momentum or randomness.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Himmelblau's function has how many local minima?

    It has four local minima, all with value 0, together with one local maximum and four saddles.
  2. 2. Which minimum gradient descent reaches depends mainly on:

    Each minimum has a basin of attraction, and the start decides which basin the point falls into.
  3. 3. For a quadratic bowl, descent converges only when η is smaller than:

    Steps beyond 2/λ_max overshoot more than they correct in the steepest direction, so the error grows.
  4. 4. A point where the gradient is zero and the Hessian has eigenvalues of both signs is:

    Mixed-sign eigenvalues mean the surface curves up in one direction and down in another.

Summary

  • You built a gradient, checked it against finite differences and ran descent from several starts.
  • The starting point decides which valley you end in; basins of attraction map this.
  • The Hessian at a minimum gives a stability limit for the step size.
  • Real optimizers add momentum, restarts and adaptive steps to cope with such landscapes.

Next: Project: Verifying the Big Theorems Numerically