Optimization · Module 4 of 10
Newton and Quasi-Newton Methods
Steepest descent uses only the slope. Newton's method adds the curvature, and it pays off dramatically: a quadratic is solved in a single step, and near any minimum the correct digits double each iteration.
Readiness check
This module uses curvature to step. Tick only what you can do closed-notes.
- Form the gradient and the Hessian of a function.
- Invert or solve with a 2 by 2 matrix.
- Recall Newton's method for a root of one equation.
- Recall what quadratic convergence means.
- Multiply a matrix by a vector.
The core idea
Newton's method models the function as a quadratic using the Hessian and jumps to that quadratic's minimum. For a true quadratic it lands exactly in one step; near any minimum it converges quadratically. Quasi-Newton methods get most of this without computing the Hessian.
Newton step: pk = −[∇2f]−1 ∇fexact in one step for a quadraticBFGS: build an approximate Hessian from gradientsSteepest descent follows the slope but ignores how the slope changes. Newton's method uses the Hessian to build a local quadratic model of f and steps straight to that model's minimum: the Newton direction is pk = −[∇2f(xk)]−1 ∇f(xk). If the function really is quadratic, the model is exact and one step reaches the minimum. For a general function the model is only local, but near a minimum Newton's method converges quadratically, doubling the correct digits each iteration, far faster than steepest descent's linear crawl. The cost is forming and solving with the Hessian at every step, which is expensive in many variables and can fail where the Hessian is not positive definite. Quasi-Newton methods, above all BFGS, avoid this by building an approximation to the Hessian (or its inverse) from successive gradients, gaining most of Newton's speed using only first derivatives. They are the default for smooth unconstrained problems.
The skills, taught in order
Five skills build the Newton step, its convergence, and the quasi-Newton alternative.
4.1 The Newton step
Newton's method solves ∇2f(xk) pk = −∇f(xk) for the step, then sets xk+1 = xk + pk. This is the exact minimiser of the local quadratic model built from the gradient and Hessian. In one variable it reduces to x − f′/f″.
4.2 One-step solution of a quadratic
If f is quadratic, its Hessian is constant and the quadratic model is exact, so a single Newton step reaches the minimum regardless of the starting point. This is the sharpest illustration of why curvature information is worth its cost.
4.3 Quadratic convergence
For a general smooth function with a positive definite Hessian at the minimum, Newton's method converges quadratically once close: the error roughly squares each step. A method that steepest descent needs dozens of iterations for, Newton finishes in a handful.
| Method | Uses | Convergence | Cost per step |
|---|---|---|---|
| Steepest descent | gradient | linear | cheap |
| Newton | gradient and Hessian | quadratic | form and solve Hessian |
| Quasi-Newton (BFGS) | gradient only | superlinear | cheap update |
Quasi-Newton methods sit between the two: near-Newton speed at near-gradient cost, which is why they dominate in practice.
4.4 Quasi-Newton and the BFGS update
Quasi-Newton methods never form the Hessian. Instead they build an approximation from the change in the gradient over each step, updating it by a formula such as BFGS so that it captures curvature. The result converges superlinearly using only first derivatives.
4.5 Safeguards and the trade-off
The raw Newton step is a descent direction only when the Hessian is positive definite; otherwise it may point uphill. Practical methods modify the Hessian or fall back to a line search or trust region. The choice among steepest descent, Newton, and quasi-Newton is a trade of cost against convergence speed.
Engineering connection: quasi-Newton solvers (BFGS and its limited-memory variant) are what commercial optimisers call when you minimise a simulation-based objective.
Worked example 1: Newton solves a quadratic in one step
Minimise f(x, y) = x2 + xy + y2 − 3x with one Newton step starting from (0, 0). Its Hessian is constant, [[2, 1], [1, 2]].
- ProblemTake one Newton step for the quadratic in Figure 1.
- Given / findf(x, y) = x2 + xy + y2 − 3x, start (0, 0), H = [[2, 1], [1, 2]]. Find the step and the new point.
- AssumptionsThe Hessian is positive definite (det 3 > 0), so the Newton step is a descent direction.
- ModelNewton step p = −H−1∇f; x1 = x0 + p.
- Equations∇f = (2x + y − 3, x + 2y)H−1 = (1/3)[[2, −1], [−1, 2]]
- Solve∇f(0, 0) = (−3, 0). p = −(1/3)[[2, −1], [−1, 2]](−3, 0) = −(1/3)(−6, 3) = (2, −1). New point (0, 0) + (2, −1) = (2, −1).
- CheckThe new point (2, −1) is exactly the minimum found in Module 2 by setting the gradient to zero, confirming that one Newton step solves a quadratic.
- ConclusionA single Newton step reaches the minimum, where steepest descent would take many. This one-step property is the whole reason to use curvature.
Worked example 2: Newton on a non-quadratic function
Minimise f(x) = x4 − 3x by Newton's method from x0 = 1. Since f is not quadratic, watch it converge over a few steps toward the true minimiser (0.75)1/3 = 0.90856.
- ProblemMinimise f(x) = x4 − 3x by Newton from x0 = 1, as in Figure 2.
- Given / findf′(x) = 4x3 − 3, f″(x) = 12x2, x0 = 1. Find x1, x2, x3.
- AssumptionsThe start is near the minimiser; f″ > 0 there, so Newton descends.
- Modelxk+1 = xk − f′(xk)/f″(xk).
- Equationsxk+1 = xk − (4xk3 − 3)/(12xk2)
- Solvex1 = 1 − (4 − 3)/12 = 0.91667. x2 = 0.90863. x3 = 0.90856, matching (0.75)1/3.
- CheckThe true minimiser solves 4x3 = 3, x = (0.75)1/3 = 0.90856, which x3 reaches; the error roughly squares each step, confirming quadratic convergence.
- ConclusionNewton does not one-step a non-quadratic, but its quadratic convergence still reaches high accuracy in three steps, from a rough start.
Misconceptions and diagnostics
| Mistake | Symptom | Diagnostic question | Correction |
|---|---|---|---|
| Newton always one-steps | Expecting exactness on any function | "Is the function quadratic?" | One step is exact only for a quadratic. |
| Ignoring Hessian definiteness | Step points uphill | "Is the Hessian positive definite?" | Modify the Hessian or safeguard the step. |
| Computing a full Hessian in high dimensions | Prohibitive cost | "Do I need the exact Hessian?" | Use a quasi-Newton approximation instead. |
| No line search on Newton | Overshoot far from the minimum | "Is the start close?" | Add a line search until near the minimum. |
Practice ladder
For f(x) = x2 − 4x, take one Newton step from x = 0.
Show answer
f′ = 2x − 4, f″ = 2. x1 = 0 − (−4)/2 = 2, the exact minimum (f is quadratic).
Why did that reach the minimum in one step?
Show answer
The function is quadratic, so its Hessian (here f″ = 2) is constant and the quadratic model is exact, giving a one-step solution.
For f(x) = x3 from x0 = 1, take one Newton step and comment.
Show answer
f′ = 3x2, f″ = 6x. x1 = 1 − 3/6 = 0.5. It approaches x = 0 but slowly, since the minimiser has f″ = 0 there (degenerate), so convergence is not quadratic.
Your simulation-based objective is costly to evaluate and its Hessian is unavailable. Argue for a quasi-Newton method and what it needs.
What good work looks like
Quasi-Newton (BFGS or limited-memory BFGS) gives near-Newton speed using only gradients, building the curvature from successive gradient changes, so it suits a costly objective where the Hessian cannot be formed.
Working with AI, and proving it yourself
Use AI as an examiner, not a solver
Portfolio task
Minimise a real objective by Newton's method, show the quadratic fall in error, and compare the iteration count to steepest descent on the same problem.
Retrieval and spaced review
Closed notes. Answer out loud, then reveal.
1. Write the Newton step.
p = −[∇2f]−1 ∇f, from ∇2f p = −∇f.
2. When is Newton exact in one step?
When the function is quadratic.
3. What is Newton's convergence rate near a minimum?
Quadratic: the error roughly squares each step.
4. What do quasi-Newton methods approximate?
The Hessian (or its inverse), built from successive gradients, as in BFGS.
5. When is the raw Newton step a descent direction?
When the Hessian is positive definite.
Textbook mapping
This module follows Nocedal and Wright, Numerical Optimization, 2nd edition. Use these references to read further.
| Topic in this module | Where to read more |
|---|---|
| The Newton step and convergence | Nocedal & Wright, Chapters 2 and 3 |
| Quasi-Newton and BFGS | Nocedal & Wright, Chapter 6 |
| Modified Newton and safeguards | Nocedal & Wright, Chapter 3 |
Chapter numbers refer to the 2nd edition. The Newton and quasi-Newton methods are standard, so any recent edition will align closely.