Lesson 42: Unconstrained Multivariable Optimisation¶
42.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- State the general descent framework \(\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{d}_k\).
- Execute steepest descent with an exact line search and explain its zig-zag.
- Relate the convergence rate to the condition number of the Hessian.
- Apply Newton's method in several variables and state its cost.
- Apply the Fletcher–Reeves conjugate gradient method and state its finite-termination property.
42.2 The Descent Framework¶
Every method in this lesson has the same shape:
Repeat: choose a direction \(\mathbf{d}_k\), choose a step length \(\alpha_k\) by a line search (Lessons 38–41), and set \(\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{d}_k\). Stop when \(\lVert\nabla f\rVert<\epsilon\).
\(\mathbf{d}_k\) is a descent direction if \(\nabla f(\mathbf{x}_k)^{T}\mathbf{d}_k<0\), i.e. \(f\) initially decreases along it. The methods differ only in how \(\mathbf{d}_k\) is chosen.
| Method | Direction \(\mathbf{d}_k\) | Cost per iteration | Iterations |
|---|---|---|---|
| Steepest descent | \(-\nabla f\) | cheap (gradient) | many |
| Newton | \(-H^{-1}\nabla f\) | expensive (\(n^2\) second derivatives, \(n^3\) solve) | very few |
| Conjugate gradient | \(-\nabla f+\beta_k\mathbf{d}_{k-1}\) | cheap (gradient) | few |
| Quasi-Newton (BFGS) | \(-B_k\nabla f\), \(B_k\) built from gradients | cheap–moderate | few |
42.3 Steepest Descent (Cauchy, 1847)¶
Direction: \(\mathbf{d}_k=-\nabla f(\mathbf{x}_k)\) — the direction of most rapid local decrease.
With an exact line search on a quadratic \(f=\tfrac12\mathbf{x}^{T}Q\mathbf{x}-\mathbf{b}^{T}\mathbf{x}\) the optimal step has a closed form:
The zig-zag¶
Orthogonality property. With an exact line search, \(\nabla f(\mathbf{x}_{k+1})^{T}\mathbf{d}_k=0\): consecutive steepest-descent directions are perpendicular.
Why. The line search minimises \(\phi(\alpha)=f(\mathbf{x}_k+\alpha\mathbf{d}_k)\), so \(\phi'(\alpha_k)=\nabla f(\mathbf{x}_{k+1})^{T}\mathbf{d}_k=0\). ∎
The consequence is the method's defining weakness. On elongated elliptical contours, right-angled turns produce a zig-zag across the narrow valley instead of progress along it:
contours (elongated ellipses) steepest descent
___________________ start
/ \ \
| .-----------. | \/\
| / * \ | \/\ <- zig-zag,
| \ / | \/\ tiny progress
\___\___________/___/ * along the valley
The convergence rate¶
Theorem. For a quadratic with Hessian \(Q\) of condition number \(\kappa=\lambda_{\max}/\lambda_{\min}\), steepest descent with exact line search satisfies $\(f(\mathbf{x}_{k+1})-f^{*}\ \le\ \left(\frac{\kappa-1}{\kappa+1}\right)^{2}\big(f(\mathbf{x}_k)-f^{*}\big).\)$
| \(\kappa\) | contours | rate \(\left(\frac{\kappa-1}{\kappa+1}\right)^2\) | behaviour |
|---|---|---|---|
| 1 | circles | 0 | one step |
| 5 | mild ellipse | 0.444 | fast |
| 25 | elongated | 0.852 | slow |
| 100 | very elongated | 0.960 | crawling |
| 1000 | needle | 0.996 | useless |
Steepest descent is only as good as the conditioning of the problem. Ill-conditioned problems — which is most real ones — defeat it entirely. Everything else in this lesson is a response to that fact.
42.4 Newton's Method in n Variables¶
Expand \(f\) to second order about \(\mathbf{x}_k\) and minimise the quadratic model exactly:
Result. \(\qquad\boxed{\ \mathbf{x}_{k+1}=\mathbf{x}_k-H_k^{-1}\mathbf{g}_k\ }\tag{3.1}\)
Properties.
- Quadratic convergence near the solution, and it converges in exactly one step on a quadratic function — because then the model is exact.
- It is affine invariant: rescaling the variables does not change the iterates, so the condition number of \(Q\) is irrelevant. This is precisely the cure for §2's weakness.
- Cost: \(n(n+1)/2\) second derivatives and an \(O(n^{3})\) linear solve per iteration. At \(n=1000\) that is half a million second derivatives — usually prohibitive.
- Danger: if \(H_k\) is not positive definite, \(-H_k^{-1}\mathbf{g}_k\) need not be a descent direction, and the method can move towards a saddle. Practical codes modify \(H_k\) (add \(\mu I\)) or use a trust region.
Quasi-Newton methods (BFGS, DFP) build an approximation to \(H^{-1}\) from successive gradients — the multivariable secant idea of Lesson 41. They keep most of Newton's speed at a fraction of its cost, and are the default in nearly all modern software.
42.5 Conjugate Gradient (Fletcher–Reeves)¶
The insight: steepest descent zig-zags because it forgets. Each new direction undoes part of the progress made by the last. Conjugate directions fix this.
Definition. Directions \(\mathbf{d}_i,\mathbf{d}_j\) are \(Q\)-conjugate if \(\mathbf{d}_i^{T}Q\mathbf{d}_j=0\) for \(i\ne j\).
Minimising along \(Q\)-conjugate directions in turn never spoils the minimisation already achieved along the earlier ones.
Theorem (finite termination). For a quadratic in \(n\) variables, exact minimisation along \(n\) mutually \(Q\)-conjugate directions reaches the exact minimum in at most \(n\) steps.
The algorithm¶
Fletcher–Reeves. $\(\mathbf{d}_0=-\mathbf{g}_0;\qquad \mathbf{d}_{k}=-\mathbf{g}_{k}+\beta_{k}\mathbf{d}_{k-1},\qquad \boxed{\ \beta_k=\frac{\mathbf{g}_k^{T}\mathbf{g}_k}{\mathbf{g}_{k-1}^{T}\mathbf{g}_{k-1}}\ }\tag{4.1}\)$ with \(\alpha_k\) from an exact line search — for a quadratic, (2.1) with \(\mathbf{d}_k\) in place of \(\mathbf{g}_k\).
Remarkably, \(\beta_k\) requires no knowledge of \(Q\) — only the ratio of successive gradient norms. So conjugate gradient costs the same per iteration as steepest descent but inherits Newton-like finite termination. On non-quadratic functions it is restarted (\(\beta_k=0\)) every \(n\) iterations, because the conjugacy relations decay.
42.6 Solved Problems¶
Running example throughout: minimise
from \(\mathbf{x}_0=(0,0)\).
The exact answer.
Eigenvalues: \(\lambda=3\pm\sqrt5=5.236,\ 0.764\), so \(\kappa=6.854\).
Problem 1 — Steepest descent¶
Perform six iterations from \(\mathbf{x}_0=(0,0)\) with exact line searches.
Solution. \(\alpha_k=\dfrac{\mathbf{g}^{T}\mathbf{g}}{\mathbf{g}^{T}Q\mathbf{g}}\) with \(\mathbf{d}=-\mathbf{g}\).
Iteration 0. \(\mathbf{g}_0=(0,-2)\), so \(\mathbf{d}_0=(0,2)\).
| \(k\) | \(\mathbf{x}_k\) | \(f(\mathbf{x}_k)\) | \(\nabla f\) | \(\lVert\nabla f\rVert\) | \(\alpha_k\) |
|---|---|---|---|---|---|
| 0 | \((0.000,\ 0.000)\) | \(0.00000\) | \((0.00,\ -2.00)\) | 2.000 | 0.250 |
| 1 | \((0.000,\ 0.500)\) | \(-0.50000\) | \((-1.00,\ 0.00)\) | 1.000 | 0.500 |
| 2 | \((0.500,\ 0.500)\) | \(-0.75000\) | \((0.00,\ -1.00)\) | 1.000 | 0.250 |
| 3 | \((0.500,\ 0.750)\) | \(-0.87500\) | \((-0.50,\ 0.00)\) | 0.500 | 0.500 |
| 4 | \((0.750,\ 0.750)\) | \(-0.93750\) | \((0.00,\ -0.50)\) | 0.500 | 0.250 |
| 5 | \((0.750,\ 0.875)\) | \(-0.96875\) | \((-0.25,\ 0.00)\) | 0.250 | 0.500 |
| 6 | \((0.875,\ 0.875)\) | \(-0.98438\) | \((0.00,\ -0.25)\) | 0.250 | 0.250 |
Interpretation — three things visible in the table.
- The zig-zag is explicit. Every gradient is either purely horizontal or purely vertical, and consecutive ones are perpendicular — exactly the orthogonality property of §2.1. The iterates creep along the line \(x_1=x_2\) in alternating axis-aligned moves.
- The convergence is linear. \(\lVert\nabla f\rVert\) goes \(2,1,1,0.5,0.5,0.25,0.25\) — halving every two iterations. The error \(f_k-f^{*}\) goes \(1,\ 0.5,\ 0.25,\ 0.125,\dots\), a constant factor of \(\tfrac12\) per step.
- It never arrives. After six iterations \(\mathbf{x}_6=(0.875,0.875)\) is still \(12.5\,\%\) away in each coordinate. Steepest descent converges to the answer but never reaches it, and here \(\kappa\) is only \(6.85\) — a well-conditioned problem by real standards.
Problem 2 — Newton's method on the same function¶
Solution. \(H=Q\) is constant, with
Iteration 0. \(\mathbf{g}_0=(0,-2)\):
Iteration 1. \(\nabla f(1,1)=(0,0)\), step \(=\mathbf{0}\): confirmed optimal.
Interpretation. Newton solves a quadratic in one step by construction — its model is the function. Contrast the six steepest-descent iterations that got only to \((0.875,0.875)\). But count the cost: Newton needed the \(2\times2\) Hessian and its inverse. In \(n=1000\) variables that is \(500{,}500\) second derivatives and a \(10^{9}\)-operation solve, per iteration. Newton's speed is real but its cost is often unaffordable, which is exactly the gap conjugate gradient and quasi-Newton methods fill.
Problem 3 — Conjugate gradient (Fletcher–Reeves)¶
Solution.
Iteration 0. \(\mathbf{g}_0=(0,-2)\), \(\mathbf{d}_0=-\mathbf{g}_0=(0,2)\). As in Problem 1, \(\alpha_0=0.25\) and \(\mathbf{x}_1=(0,\ 0.5)\).
New gradient \(\mathbf{g}_1=(-1,\ 0)\).
Conjugacy check.
Iteration 1.
Summary.
| Method | Iterations to the exact optimum | Second derivatives used |
|---|---|---|
| Steepest descent | \(\infty\) (still \(0.125\) away after 6) | 0 |
| Conjugate gradient | 2 | 0 |
| Newton | 1 | 3 (the Hessian) |
Interpretation. Conjugate gradient achieves finite termination using only gradients. The whole trick is \(\beta_1=0.25\): the second direction \((1,0.5)\) is not the steepest-descent direction \((1,0)\) but is tilted to preserve the progress already made along \(\mathbf{d}_0\). That one number is the difference between six ineffective iterations and two exact ones.
For large problems this is decisive: CG stores a handful of vectors and never forms a matrix, so it scales to millions of variables — which is why it remains the standard method for large sparse systems, both in optimisation and in solving linear equations.
Problem 4 — Ill-conditioning in action¶
Minimise \(f(x_1,x_2)=x_1^{2}+25x_2^{2}\) from \((5,1)\) by steepest descent. Here \(Q=\mathrm{diag}(2,50)\), so \(\kappa=25\).
Solution.
| \(k\) | \(\mathbf{x}_k\) | \(f(\mathbf{x}_k)\) | \(\alpha_k\) | \(f_k/f_{k-1}\) |
|---|---|---|---|---|
| 0 | \((5.00000,\ 1.00000)\) | 50.00000 | 0.020767 | — |
| 1 | \((4.79233,\ -0.03834)\) | 23.00320 | 0.260000 | 0.4601 |
| 2 | \((2.30032,\ 0.46006)\) | 10.58294 | 0.020767 | 0.4601 |
| 3 | \((2.20478,\ -0.01764)\) | 4.86883 | 0.260000 | 0.4601 |
| 4 | \((1.05829,\ 0.21166)\) | 2.23997 | 0.020767 | 0.4601 |
| 5 | \((1.01434,\ -0.00812)\) | 1.03053 | 0.260000 | 0.4601 |
| 6 | \((0.48688,\ 0.09738)\) | 0.47411 | 0.020767 | 0.4601 |
| 7 | \((0.46666,\ -0.00373)\) | 0.21812 | 0.260000 | 0.4601 |
Solution \((0,0)\) with \(f^{*}=0\).
Interpretation.
- The step lengths alternate between \(0.0208\) and \(0.2600\) — a factor of \(12.5\) — because the gradient alternates between pointing mostly along the steep \(x_2\) axis and mostly along the shallow \(x_1\) axis. This alternation is the zig-zag, in numbers.
- The reduction factor is a constant \(0.4601\) per iteration, well inside the worst-case bound \(\left(\frac{24}{26}\right)^{2}=0.8521\); the bound is attained only from the least favourable start.
- Even at \(0.4601\) per step, reaching \(f<10^{-6}\) takes about \(22\) iterations. At \(\kappa=100\) the worst-case factor is \(0.96\) and the same target takes over \(400\).
- Newton would solve this in one step, because it rescales the variables implicitly. So would conjugate gradient in two (\(n=2\)).
The lesson for practice: before blaming an algorithm, check the conditioning. Simply rescaling \(x_2\to5x_2\) here makes the contours circular (\(\kappa=1\)) and steepest descent converges in one step. Good scaling of the variables is often worth more than a better algorithm.
Problem 5 — Choosing a method¶
Recommend a method for each situation.
| Situation | Recommendation | Reason |
|---|---|---|
| \(n=2\), cheap analytic derivatives, quadratic \(f\) | Newton | One step; the Hessian is trivial |
| \(n=50\), smooth, second derivatives available but costly | Quasi-Newton (BFGS) | Near-Newton speed, gradients only |
| \(n=10^{6}\), sparse quadratic (e.g. a discretised PDE) | Conjugate gradient | Stores only vectors; never forms \(H\) |
| Gradients unavailable, \(f\) from a black-box simulation | Nelder–Mead or pattern search | Derivative-free; all methods here need \(\nabla f\) |
| Non-convex, several local minima | Multi-start with any local method | No local method can escape a basin |
| \(f\) noisy (Monte-Carlo output) | Stochastic methods (SPSA, or heavy smoothing) | Finite-difference gradients are meaningless in noise |
| Very ill-conditioned but small | Newton, or rescale first | \(\kappa\) is irrelevant to Newton; rescaling fixes it for everyone else |
The two decisions that matter. (1) How expensive is a derivative? — this chooses the family. (2) How well-conditioned is the problem? — this decides whether first-order methods are viable at all. Everything else is detail.
42.7 Practice Problems¶
- One steepest-descent step on \(f=x_1^{2}+x_2^{2}\) from \((3,4)\) with exact line search. (Answer: \(\mathbf{g}=(6,8)\), \(\alpha=0.5\), \(\mathbf{x}_1=(0,0)\) — exact in one step, since \(\kappa=1\))
- Verify that \(\mathbf{d}_0=(0,2)\) and \(\mathbf{d}_1=(1,0.5)\) are \(Q\)-conjugate for \(Q=\begin{pmatrix}2&-2\\-2&4\end{pmatrix}\), and find a third direction conjugate to both. (Answer: the check is in Problem 3; in \(\mathbb{R}^{2}\) no third non-zero direction can be conjugate to two independent ones)
- For \(f=4x_1^{2}+x_2^{2}\), find \(\kappa\) and the steepest-descent convergence factor. (Answer: \(Q=\mathrm{diag}(8,2)\), \(\kappa=4\), factor \((3/5)^2=0.36\))
- Show that with an exact line search, \(\nabla f(\mathbf{x}_{k+1})^{T}\mathbf{d}_k=0\), and explain what it means geometrically. (Answer: the new gradient is tangent to the contour through \(\mathbf{x}_{k+1}\) in the direction just searched — the line touches the contour there)
- Why is Fletcher–Reeves restarted every \(n\) iterations on a non-quadratic function? (Answer: conjugacy is defined relative to a fixed \(Q\); when the Hessian changes from point to point the accumulated directions lose conjugacy and \(\mathbf{d}_k\) can stop being a descent direction)
42.8 Summary¶
- All methods share \(\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{d}_k\) and differ only in \(\mathbf{d}_k\); the step \(\alpha_k\) comes from a line search (Lessons 38–41).
- Steepest descent (\(\mathbf{d}=-\nabla f\)) is cheap but zig-zags, because exact line searches make consecutive directions perpendicular. Its rate is \(\left(\dfrac{\kappa-1}{\kappa+1}\right)^{2}\) — useless on ill-conditioned problems.
- Newton (\(\mathbf{d}=-H^{-1}\nabla f\)) converges quadratically, solves any quadratic in one step, and is immune to conditioning — but costs \(O(n^{2})\) second derivatives and an \(O(n^{3})\) solve, and can be attracted to saddles if \(H\) is not positive definite.
- Conjugate gradient achieves finite termination in \(n\) steps on a quadratic using gradients only, via \(\beta_k=\dfrac{\mathbf{g}_k^{T}\mathbf{g}_k}{\mathbf{g}_{k-1}^{T}\mathbf{g}_{k-1}}\). Restart every \(n\) iterations on non-quadratics.
- Quasi-Newton (BFGS) builds \(H^{-1}\) from successive gradients — the multivariable secant idea — and is the practical default.
- On the running example: steepest descent had not arrived after 6 iterations; CG took 2; Newton took 1.
- Rescaling the variables is often worth more than changing the algorithm. Check the condition number before blaming the method.
Next lesson: L43 — Constrained optimisation: graphical solution and Lagrange multipliers.
Practise now: unit4-nlp-search-lab.html → Descent Lab: draw contours, pick a start point and
watch steepest descent zig-zag while conjugate gradient and Newton cut straight to the optimum.