Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 37 ยท Optimization and Eigenvalues

Gradient Descent and Newton's Method for Optimization

Minimize functions of many variables with gradient descent, line search, momentum and Newton's method. Compare convergence on the Rosenbrock function with SciPy.

Most useful optimization problems have many variables: the weights of a model, the coordinates of a structure, the parameters of a fit. We want the point x in R^n that minimizes f(x). At a smooth minimum the gradient (the vector of partial derivatives) is zero and the Hessian (the matrix of second derivatives) is positive definite.

Two families of methods dominate. Gradient descent uses only first derivatives and is cheap per step but can be slow. Newton's method also uses the Hessian, converges in very few steps near the solution, and costs much more per step. Quasi-Newton methods (BFGS) sit in between and are the practical default.

Gradient descent

The gradient points uphill, so walk the other way:

x(k+1) = x(k) - alpha * grad f(x(k))

The step length alpha (learning rate) matters. Too small: slow. Too large: oscillation or divergence. For a quadratic f(x) = 0.5 x^T A x - b^T x, convergence requires alpha < 2 / lambda_max(A), and the speed is governed by the condition number kappa = lambda_max / lambda_min: the error shrinks per step by about (kappa - 1) / (kappa + 1). Long, narrow valleys (large kappa) are the enemy.

Python Gradient descent on an ill-conditioned quadratic

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 best rate arrives near alpha = 0.039; 0.05 crosses the stability limit and diverges (the printed distance explodes), while 0.01 is stable but slow in the flat direction.

Line search and backtracking

Rather than fixing alpha, choose it every step. Backtracking starts with a large alpha and shrinks it (multiply by 0.5) until the Armijo condition holds: f(x - alpha g) <= f(x) - c * alpha * |g|^2, with c around 1e-4. This guarantees a decrease at every step without tuning.

Momentum

Plain gradient descent zigzags across a narrow valley. Momentum keeps a velocity that averages past gradients, smoothing the zigzag and speeding up along the valley floor:

v = beta * v - alpha * grad f(x), x = x + v with beta about 0.9.

Python Plain versus momentum on the Rosenbrock valley

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 head to the minimum at (1, 1) along a curved valley; momentum gets much closer in the same number of steps. (Plain descent is still creeping along the flat valley floor.)

Newton's method in many dimensions

Approximate f by its second-order Taylor model and jump to that model's minimum. The step p solves the linear system

H(x) p = -grad f(x), then x(k+1) = x(k) + p.

Near a minimum with positive definite H the convergence is quadratic (digits double per step). Drawbacks: computing and factorizing the Hessian costs O(n^3); far from a minimum H may be indefinite and the step may go uphill; Newton needs safeguards (line search, trust region, or adding a multiple of the identity to H).

Python Newton's method on Rosenbrock

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.

About twenty damped Newton steps (the early ones are short because of the backtracking) solve a problem that costs plain gradient descent tens of thousands.

Quasi-Newton: BFGS, and SciPy

BFGS builds an approximation of the inverse Hessian from successive gradient differences. It needs only gradients, costs O(n^2) per step, and converges superlinearly. L-BFGS keeps just a few recent vectors, so it scales to millions of variables. In SciPy, minimize selects a method; supplying the gradient (jac=) saves evaluations.

Python scipy.optimize.minimize methods

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.

Nelder-Mead needs no derivatives at all, which is handy for noisy or non-smooth functions, but it is slow for more than a handful of variables.

Rule of thumb: derivatives available and a moderate number of variables, use BFGS. Very many variables, L-BFGS. No derivatives, a few variables, Nelder-Mead. Simple bounds, L-BFGS-B. Constraints, SLSQP or trust-constr. For fitting model parameters, see least squares, where Gauss-Newton exploits the problem structure.

Common mistakes

  • Using a fixed learning rate without checking stability.
  • Starting Newton far from the solution without a line search.
  • Not scaling variables of very different magnitudes (badly scaled problems have huge condition numbers).
  • Stopping on |x(k+1) - x(k)| alone; check the gradient norm too.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What condition does the gradient satisfy at a smooth interior minimum?

    Stationary points have grad f = 0; positive definite Hessian makes it a minimum.
  2. 2. What mainly slows gradient descent on a long narrow valley?

    The convergence factor (kappa - 1)/(kappa + 1) approaches 1 when kappa is large.
  3. 3. What does Newton's method solve at each step?

    The step p solves the linear system formed by the Hessian and the negative gradient.
  4. 4. Which method scales to millions of variables using only gradients?

    L-BFGS stores only a few recent vectors instead of a full Hessian approximation.

Summary

  • Optimum: zero gradient and positive definite Hessian.
  • Gradient descent is simple but limited by step size and conditioning; momentum and line search help.
  • Newton's method converges quadratically near the solution but needs the Hessian and safeguards.
  • BFGS and L-BFGS are the practical compromise; Nelder-Mead needs no derivatives.

Next: Power iteration and eigenvalues