Skip to content

Lesson 42: Unconstrained Multivariable Optimisation

42.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. State the general descent framework \(\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{d}_k\).
  2. Execute steepest descent with an exact line search and explain its zig-zag.
  3. Relate the convergence rate to the condition number of the Hessian.
  4. Apply Newton's method in several variables and state its cost.
  5. 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:

\[\boxed{\ \alpha_k=\frac{\mathbf{g}_k^{T}\mathbf{g}_k}{\mathbf{g}_k^{T}Q\,\mathbf{g}_k}\ }, \qquad \mathbf{g}_k=\nabla f(\mathbf{x}_k). \tag{2.1}\]

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:

\[f(\mathbf{x})\approx f_k+\mathbf{g}_k^{T}(\mathbf{x}-\mathbf{x}_k) +\tfrac12(\mathbf{x}-\mathbf{x}_k)^{T}H_k(\mathbf{x}-\mathbf{x}_k)\]

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

\[f(x_1,x_2)=x_1^{2}+2x_2^{2}-2x_1x_2-2x_2\]

from \(\mathbf{x}_0=(0,0)\).

The exact answer.

\[\nabla f=\begin{pmatrix}2x_1-2x_2\\ 4x_2-2x_1-2\end{pmatrix}=\mathbf{0} \Rightarrow x_1=x_2\ \text{and}\ 2x_2=2\Rightarrow \mathbf{x}^{*}=(1,1)\]
\[H=Q=\begin{pmatrix}2&-2\\-2&4\end{pmatrix},\quad D_1=2>0,\ \det=4>0\ \text{(positive definite)}, \quad f^{*}=1+2-2-2=-1\]

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)\).

\[Q\mathbf{d}_0=\begin{pmatrix}2&-2\\-2&4\end{pmatrix}\begin{pmatrix}0\\2\end{pmatrix} =\begin{pmatrix}-4\\8\end{pmatrix},\qquad \alpha_0=\frac{4}{(0)(-4)+(2)(8)}=\frac{4}{16}=0.25\]
\[\mathbf{x}_1=(0,0)+0.25(0,2)=(0,\ 0.5),\qquad f=-0.5\]
\(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.

  1. 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.
  2. 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.
  3. 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

\[H^{-1}=\frac{1}{4}\begin{pmatrix}4&2\\2&2\end{pmatrix}=\begin{pmatrix}1&0.5\\0.5&0.5\end{pmatrix}\]

Iteration 0. \(\mathbf{g}_0=(0,-2)\):

\[\mathbf{x}_1=(0,0)-\begin{pmatrix}1&0.5\\0.5&0.5\end{pmatrix}\begin{pmatrix}0\\-2\end{pmatrix} =(0,0)-(-1,-1)=(1,\ 1)\]
\[\boxed{\text{Converged exactly in ONE iteration},\quad f=-1}\]

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)\).

\[\beta_1=\frac{\mathbf{g}_1^{T}\mathbf{g}_1}{\mathbf{g}_0^{T}\mathbf{g}_0}=\frac{1}{4}=0.25\]
\[\mathbf{d}_1=-\mathbf{g}_1+\beta_1\mathbf{d}_0=(1,0)+0.25(0,2)=(1,\ 0.5)\]

Conjugacy check.

\[\mathbf{d}_0^{T}Q\mathbf{d}_1=(0,2)\begin{pmatrix}2&-2\\-2&4\end{pmatrix}\begin{pmatrix}1\\0.5\end{pmatrix} =(0,2)\cdot(1,\ 0)=0\ \checkmark\]

Iteration 1.

\[Q\mathbf{d}_1=\begin{pmatrix}2&-2\\-2&4\end{pmatrix}\begin{pmatrix}1\\0.5\end{pmatrix} =\begin{pmatrix}1\\0\end{pmatrix},\qquad \alpha_1=\frac{-\mathbf{g}_1^{T}\mathbf{d}_1}{\mathbf{d}_1^{T}Q\mathbf{d}_1} =\frac{1}{(1)(1)+(0.5)(0)}=1\]
\[\mathbf{x}_2=(0,0.5)+1(1,\ 0.5)=(1,\ 1)\]
\[\boxed{\text{Converged exactly in }n=2\text{ iterations},\quad f=-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

  1. 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\))
  2. 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)
  3. 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\))
  4. 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)
  5. 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.