4.4.1 Optimality conditions in several variables

In this lesson

What it means to minimise a function of several variables, and why a maximum is the same problem
The first-order condition: at a minimum the gradient is $\mathbf{0}$
The second-order conditions: what the Hessian must be at a minimum, and what is enough
Local and global minima, and how to tell them apart
Quadratic functions $\frac{1}{2}\mathbf{x}^\top A\mathbf{x} - \mathbf{b}^\top\mathbf{x}$ , whose minimum solves $A\mathbf{x} = \mathbf{b}$
Least squares as a quadratic to minimise
Checking every step in Python

You need the gradient and the slope in a direction from lesson 4.2.1, and the Hessian and the second-derivative test from lessons 4.3.1 and 4.3.2. The quadratic functions use linear systems (lesson 3.3.1) and positive definite matrices (lesson 3.7.1). Lesson 2.4.1 did the same for one variable.

The problem

To minimise a function $f(\mathbf{x})$ of $n$ variables is to find a point $\mathbf{x}^*$ where $f$ is as small as possible. The point $\mathbf{x}^*$ is a minimiser and $f(\mathbf{x}^*)$ is the minimum value. As in lesson 2.4.1, an answer has two parts: where, in the units of $\mathbf{x}$ , and how much, in the units of $f$ .

The function being minimised is called the objective. Unconstrained means that $\mathbf{x}$ may be any point of $\mathbb{R}^n$ . Module 4.5 adds conditions, such as portfolio weights that must add up to 1.

A maximum needs no new theory. The highest point of $f$ is the lowest point of $-f$ , so this module speaks only of minima.

The first-order condition

Lesson 4.2.1 showed that the slope of $f$ in a unit direction $\mathbf{u}$ is $\nabla f \cdot \mathbf{u}$ , and that $f$ falls fastest against the gradient. So if $\nabla f(\mathbf{x}) \neq \mathbf{0}$ , a small step against the gradient lowers $f$ , and $\mathbf{x}$ is not a minimum.

Take $f(x, y) = x^2 + xy + y^2 - 3x$ , whose gradient is $\nabla f = (2x + y - 3,\ x + 2y)$ . At $(0, 1)$ , $f = 1$ and $\nabla f = (-2, 2)$ .

A step of size $t$ against the gradient goes to $(0, 1) - t(-2, 2)$ . The tangent-plane estimate of lesson 4.2.2 says $f$ falls by about $t\lVert\nabla f\rVert^2 = 8t$ .

step $t$	new point	$f$ there	estimate $1 - 8t$
0.1	$(0.2, 0.8)$	0.24	0.2
0.05	$(0.1, 0.9)$	0.61	0.6
0.01	$(0.02, 0.98)$	0.9204	0.92

Every step lowers $f$ , and the smaller the step, the closer the estimate.

Rule: First-order condition

\nabla f(\mathbf{x}^*) = \mathbf{0}

At a minimum of a differentiable function, every partial derivative is zero. A point where this holds is a critical point (lesson 4.3.2). The condition is needed but not enough: a maximum or a saddle passes it too.

The saddle $x^2 - y^2$ of lesson 4.1.1 has $\nabla f = (2x, -2y) = \mathbf{0}$ at the origin. Yet $f(0, 0.1) = -0.01$ is below $f(0, 0) = 0$ , so the origin is not a minimum.

For $f = x^2 + xy + y^2 - 3x$ , the condition is two linear equations, $2x + y = 3$ and $x + 2y = 0$ . That is a linear system (lesson 3.3.1), and its solution is $(2, -1)$ , with $f(2, -1) = -3$ . On a grid around it, every neighbour is higher:

	$y = -0.5$	$y = -1$	$y = -1.5$
$x = 1.5$	$-2.75$	$-2.75$	$-2.25$
$x = 2$	$-2.75$	$-3$	$-2.75$
$x = 2.5$	$-2.25$	$-2.75$	$-2.75$

A table only samples a few points. The next section gives a test that settles it.

\nabla f

import numpy as np def f(p): x, y = p return x**2 + x * y + y**2 - 3 * x def grad(p): x, y = p return np.array([2 * x + y - 3, x + 2 * y]) p = np.array([0.0, 1.0]) g = grad(p) print(f(p), g, g @ g) for t in [0.1, 0.05, 0.01]: print(t, np.round(p - t * g, 4), round(f(p - t * g), 6), round(f(p) - t * (g @ g), 6)) star = np.linalg.solve(np.array([[2.0, 1.0], [1.0, 2.0]]), np.array([3.0, 0.0])) print(star, f(star)) for dx in [-0.5, 0, 0.5]: print([round(float(f(star + np.array([dx, dy]))), 4) for dy in [0.5, 0, -0.5]]) print(np.linalg.eigvalsh(np.array([[2.0, 1.0], [1.0, 2.0]])))

⌘/Ctrl + Enter runs the cell

Second-order conditions

Lesson 4.3.2's test reads the Hessian $H$ , the matrix of second partial derivatives, at a critical point. Positive definite means a minimum, negative definite a maximum, indefinite a saddle, and semidefinite leaves it undecided. For minimising, the test splits into a condition that is needed and one that is enough.

Rule: Second-order conditions

\begin{gathered} \text{needed: } H(\mathbf{x}^*) \text{ positive semidefinite} \\[4pt] \text{enough: } \nabla f(\mathbf{x}^*) = \mathbf{0} \\ \text{and } H(\mathbf{x}^*) \text{ positive definite} \end{gathered}

At every local minimum the Hessian is positive semidefinite (lesson 3.7.1). A critical point with a positive definite Hessian is a strict local minimum: every nearby point is higher.

For $f = x^2 + xy + y^2 - 3x$ the Hessian is $H = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ at every point. Its eigenvalues are 1 and 3 (lesson 3.6.3), both positive, so $(2, -1)$ is a strict local minimum.

The "needed" condition rules points out. If $H$ has a negative eigenvalue, $f$ falls along that eigenvector, so the point is no minimum. At the saddle $x^2 - y^2$ , $H$ has eigenvalues 2 and $-2$ .

The gap between the two conditions is a semidefinite Hessian with a zero eigenvalue. Lesson 4.3.2 showed it with $x^4 + y^2$ and $x^3 + y^2$ : both have $\nabla f = \mathbf{0}$ and $H = \begin{pmatrix} 0 & 0 \\ 0 & 2 \end{pmatrix}$ at the origin, so both pass the needed condition. Only the first has a minimum there.

Local and global minima

A local minimum is lower than every point near it. The global minimum is the lowest value anywhere, as in lesson 2.4.1. Both conditions above are local: they look only near $\mathbf{x}^*$ .

Take $f(x, y) = x^4 - 3x^2 + x + y^2$ . Along $y = 0$ it is the quartic of lesson 2.4.3.

Its gradient is $(4x^3 - 6x + 1,\ 2y)$ , so a critical point needs $y = 0$ and $4x^3 - 6x + 1 = 0$ . Lesson 2.4.3 found the three roots.

The Hessian is $\begin{pmatrix} 12x^2 - 6 & 0 \\ 0 & 2 \end{pmatrix}$ , so the sign of $12x^2 - 6$ decides each point:

critical point	$f$	$12x^2 - 6$	Hessian	kind
$(-1.30084, 0)$	$-3.5139$	14.3062	positive definite	global minimum
$(0.169938, 0)$	0.0841	$-5.6535$	indefinite	saddle
$(1.130901, 0)$	$-1.0702$	9.3472	positive definite	local minimum only

Two valleys and a saddle between them. Both minima pass the second-order test; only the comparison of their values shows which is global. The dashed level curve through the saddle encloses one valley in each loop.

To find the global minimum, compare the critical points. On a closed interval lesson 2.4.1 also checked the ends.

In $\mathbb{R}^n$ there are no ends, but there is "far away": here $x^4$ and $y^2$ grow without limit in every direction, with $f(3, 0) = 57$ and $f(0, 3) = 9$ . So $f$ has a lowest point, and it is the lower minimum, $-3.5139$ at $(-1.30084, 0)$ .

Without that growth there may be no global minimum. Lesson 4.3.2's cubic $x^3 - 3x + y^2$ has a local minimum at $(1, 0)$ , where $f = -2$ , but $f(-10, 0) = -970$ : it falls without limit.

Rule: Local and global

\begin{gathered} f \text{ grows without limit far away:} \\ \text{the lowest critical point is global} \end{gathered}

If $f$ falls without limit in some direction, it has no global minimum. Lesson 4.5.3 adds convex functions, for which every local minimum is global.

The methods of lessons 4.4.2 and 4.4.3 walk downhill from a starting point and stop at a minimum near it. Which minimum depends on the start, so case study 4.4.5 tries several.

4x^3 - 6x + 1

import numpy as np def f(x, y): return x**4 - 3 * x**2 + x + y**2 roots = np.sort(np.roots([4, 0, -6, 1]).real) for r in roots: print(round(r, 6), round(f(r, 0), 4), round(12 * r**2 - 6, 4)) print(f(3, 0), f(0, 3)) def cubic(x, y): return x**3 - 3 * x + y**2 print(cubic(1, 0), cubic(-10, 0))

⌘/Ctrl + Enter runs the cell

Quadratic functions

The most important example is a quadratic function: a quadratic form (lesson 3.7.1) minus a linear part. For a symmetric $n \times n$ matrix $A$ and a vector $\mathbf{b}$ in $\mathbb{R}^n$ ,

f(\mathbf{x}) = \tfrac{1}{2}\,\mathbf{x}^\top A\,\mathbf{x} - \mathbf{b}^\top\mathbf{x}

Its gradient is $A\mathbf{x} - \mathbf{b}$ and its Hessian is $A$ at every point. For $n = 2$ , lesson 3.7.1 writes the form out as $\frac{1}{2}\mathbf{x}^\top A\mathbf{x} = \frac{1}{2}a_{11}x_1^2 + a_{12}x_1x_2 + \frac{1}{2}a_{22}x_2^2$ . Its partial derivative in $x_1$ is $a_{11}x_1 + a_{12}x_2$ , the first entry of $A\mathbf{x}$ .

The $\frac{1}{2}$ is there so that the gradient has no factor 2.

The example above is one. With $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ and $\mathbf{b} = (3, 0)$ , $\frac{1}{2}\mathbf{x}^\top A\mathbf{x} = x^2 + xy + y^2$ and $\mathbf{b}^\top\mathbf{x} = 3x$ .

So the first-order condition $\nabla f = \mathbf{0}$ reads $A\mathbf{x} = \mathbf{b}$ : the minimiser of a quadratic solves a linear system. For a quadratic, the second-order expansion of lesson 4.3.1 is exact, with nothing left over. At a solution of $A\mathbf{x}^* = \mathbf{b}$ its gradient term is zero:

Rule: Minimum of a quadratic

\begin{gathered} A\mathbf{x}^* = \mathbf{b} \\[4pt] f(\mathbf{x}^* + \mathbf{h}) = f(\mathbf{x}^*) + \tfrac{1}{2}\,\mathbf{h}^\top A\,\mathbf{h} \\[4pt] f(\mathbf{x}^*) = -\tfrac{1}{2}\,\mathbf{b}^\top\mathbf{x}^* \end{gathered}

If $A$ is positive definite, $\frac{1}{2}\mathbf{h}^\top A\mathbf{h} > 0$ for every step $\mathbf{h} \neq \mathbf{0}$ . So $\mathbf{x}^*$ is the unique global minimum, not just a local one.

For the example, $\mathbf{x}^* = (2, -1)$ and $-\frac{1}{2}\mathbf{b}^\top\mathbf{x}^* = -\frac{1}{2}(6) = -3$ , as found above. A step $\mathbf{h} = (0.5, 0.5)$ raises $f$ by $\frac{1}{2}\mathbf{h}^\top A\mathbf{h} = 0.75$ : $f(2.5, -0.5) = -2.25$ .

Along a unit eigenvector $\mathbf{q}$ of $A$ with eigenvalue $\lambda$ , a step of $t$ raises $f$ by $\frac{1}{2}\lambda t^2$ . Here one unit along $(1, 1)/\sqrt{2}$ adds 1.5, and along $(1, -1)/\sqrt{2}$ only 0.5. The bowl is steeper along one eigenvector than the other, which matters for lesson 4.4.2.

Three variables. Lesson 3.7.1's positive definite matrix

K = \begin{pmatrix} 4 & -1 & 0 \\ -1 & 3 & 2 \\ 0 & 2 & 5 \end{pmatrix}

with $\mathbf{b} = (3, 0, -3)$ gives $\mathbf{x}^* = (1, 1, -1)$ and a minimum value of $-3$ . Its eigenvalues are 1.4711, 4.1674 and 6.3615.

When A is not positive definite

$A\mathbf{x} = \mathbf{b}$ can still have a solution, but it is not a minimum.

$A$	$A\mathbf{x} = \mathbf{b}$	the quadratic
positive definite	one solution	one global minimum
indefinite	a solution	a saddle: no minimum
semidefinite, singular	none, or a whole line	no minimum, or a line of minima

Indefinite. $N = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$ , with eigenvalues $-1$ and 3, and $\mathbf{b} = (3, 3)$ give the solution $(1, 1)$ , where $f = -3$ . Along $(1, -1)$ , $f(1 + t, 1 - t) = -3 - t^2$ , which is $-4$ , $-7$ and $-103$ at $t = 1$ , 2 and 10.

Semidefinite. $J = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ is singular, so solve stops with an error. With $\mathbf{b} = (1, 1)$ , $f = \frac{1}{2}(x + y)^2 - (x + y)$ is smallest, $-0.5$ , on the whole line $x + y = 1$ . With $\mathbf{b} = (1, -1)$ , $f(t, -t) = -2t$ falls without limit.

\frac{1}{2}\mathbf{x}^\top A\mathbf{x} - \mathbf{b}^\top\mathbf{x}

import numpy as np def quad(A, b, x): return 0.5 * x @ A @ x - b @ x A = np.array([[2.0, 1.0], [1.0, 2.0]]) b = np.array([3.0, 0.0]) p = np.array([0.3, 0.7]) print(round(quad(A, b, p), 6), round(p[0]**2 + p[0] * p[1] + p[1]**2 - 3 * p[0], 6)) star = np.linalg.solve(A, b) h = np.array([0.5, 0.5]) print(star, quad(A, b, star), -0.5 * b @ star, round(quad(A, b, star + h) - quad(A, b, star), 6), 0.5 * h @ A @ h) K = np.array([[4.0, -1.0, 0.0], [-1.0, 3.0, 2.0], [0.0, 2.0, 5.0]]) bK = np.array([3.0, 0.0, -3.0]) print(np.linalg.solve(K, bK), np.round(np.linalg.eigvalsh(K), 4), quad(K, bK, np.linalg.solve(K, bK))) N = np.array([[1.0, 2.0], [2.0, 1.0]]) bN = np.array([3.0, 3.0]) sN = np.linalg.solve(N, bN) print(np.linalg.eigvalsh(N), sN, [float(quad(N, bN, sN + t * np.array([1, -1]))) for t in [1, 2, 10]]) J = np.array([[1.0, 1.0], [1.0, 1.0]]) try: np.linalg.solve(J, np.array([1.0, 1.0])) except np.linalg.LinAlgError as err: print("LinAlgError:", err) print([float(quad(J, np.array([1.0, 1.0]), np.array(p))) for p in [(1, 0), (0, 1), (3, -2)]]) print([float(quad(J, np.array([1.0, -1.0]), np.array([t, -t]))) for t in [1, 5, 10]])

⌘/Ctrl + Enter runs the cell

Least squares is a quadratic

Lesson 3.5.3 chose $\hat{\mathbf{x}}$ to make $\lVert M\mathbf{x} - \mathbf{y} \rVert^2$ as small as possible, for a matrix $M$ and data $\mathbf{y}$ . Multiplied out, this is

\begin{gathered} F(\mathbf{x}) = \mathbf{x}^\top M^\top M\,\mathbf{x} - 2(M^\top\mathbf{y})^\top\mathbf{x} + \mathbf{y}^\top\mathbf{y} \end{gathered}

That is a quadratic function with $A = 2M^\top M$ and $\mathbf{b} = 2M^\top\mathbf{y}$ , plus a constant. So $\nabla F = 2M^\top(M\mathbf{x} - \mathbf{y})$ , and $\nabla F = \mathbf{0}$ is $M^\top M\,\mathbf{x} = M^\top\mathbf{y}$ : the normal equations of lesson 3.5.3.

The Hessian $2M^\top M$ is always positive semidefinite, and positive definite when the columns of $M$ are independent (lesson 3.7.1). Then the normal equations give the global minimum.

For lesson 3.5.3's five points, the line $y = 1 + 1.2x$ leaves a sum of squares of 0.8, and the gradient there is $(0, 0)$ . The line $y = 1 + x$ leaves 2, with gradient $(-4, -12)$ : both entries negative, so raising the intercept or the slope lowers $F$ . The Hessian has eigenvalues 2.9844 and 67.0156.

When a model is not linear in its unknowns, $\nabla F = \mathbf{0}$ is no longer a linear system. Lessons 4.4.2 and 4.4.3 find such minima by walking downhill, and case study 4.4.5 fits a yield curve that way. Module 5.9 maximises a likelihood with the same conditions.

x

import numpy as np x = np.array([0.0, 1.0, 2.0, 3.0, 4.0]) y = np.array([1.0, 2.0, 4.0, 4.0, 6.0]) M = np.column_stack([np.ones(5), x]) def F(c): return np.sum((M @ c - y) ** 2) def grad(c): return 2 * M.T @ (M @ c - y) best = np.linalg.solve(M.T @ M, M.T @ y) print(best, round(F(best), 6), np.round(grad(best), 10) + 0.0) print(F(np.array([1.0, 1.0])), grad(np.array([1.0, 1.0]))) print(2 * M.T @ M, np.round(np.linalg.eigvalsh(2 * M.T @ M), 4))

⌘/Ctrl + Enter runs the cell

Common mistakes

$\nabla f = \mathbf{0}$ is not enough. Maxima and saddles pass it too; check the Hessian.
A semidefinite Hessian proves nothing. $x^4 + y^2$ and $x^3 + y^2$ have the same Hessian at the origin; only the first has a minimum there (lesson 4.3.2).
Both conditions are local. The minimum at $(1.130901, 0)$ passes the test but lies above the one at $(-1.30084, 0)$ .
A local minimum may have no global one below it. $x^3 - 3x + y^2$ falls without limit as $x$ goes to $-\infty$ .
Mind the $\frac{1}{2}$ . The gradient of $\frac{1}{2}\mathbf{x}^\top A\mathbf{x}$ is $A\mathbf{x}$ ; the gradient of $\mathbf{x}^\top A\mathbf{x}$ is $2A\mathbf{x}$ .
Check $A$ before you solve. An indefinite $A$ still gives a solution of $A\mathbf{x} = \mathbf{b}$ , and it is a saddle.
For a maximum, minimise $-f$ . At a maximum the Hessian of $f$ is negative definite.

Optimality conditions

0 of 12 correct

1.
At what $x$ is $f(x, y) = x^2 + 4y^2 - 2x + 8y$ smallest? Give the $x$ -coordinate
2.
For the same $f$ , give the $y$ -coordinate of the minimiser
3.
What is the minimum value of $x^2 + 4y^2 - 2x + 8y$ ?
4.
At $(0, 1)$ , $f = 1$ and $\nabla f = (-2, 2)$ . Estimate $f$ after a step $t = 0.05$ against the gradient, using $f - t\lVert\nabla f\rVert^2$
5.
At a critical point the Hessian has eigenvalues 4 and 0.5. Is the point a strict local minimum? Type 1 for yes, 0 for no
6.
At a critical point the Hessian has eigenvalues 3 and $-0.5$ . Can the point be a local minimum? Type 1 for yes, 0 for no
7.
At a critical point $H = \begin{pmatrix} 2 & 0 \\ 0 & 0 \end{pmatrix}$ . Can the second-order conditions decide whether it is a minimum? Type 1 for yes, 0 for no
8.
$x^3 - 3x + y^2$ has a local minimum at $(1, 0)$ with value $-2$ . Find $f(-4, 0)$
9.
Minimise $\frac{1}{2}\mathbf{x}^\top A\mathbf{x} - \mathbf{b}^\top\mathbf{x}$ with $A = \begin{pmatrix} 4 & 1 \\ 1 & 3 \end{pmatrix}$ and $\mathbf{b} = (5, 4)$ . What is $x_1$ at the minimiser?
10.
For the same quadratic, the minimiser is $(1, 1)$ . What is the minimum value $-\frac{1}{2}\mathbf{b}^\top\mathbf{x}^*$ ?
11.
For $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ , how much does $f$ rise from its minimum after the step $\mathbf{h} = (1, 1)$ ?
12.
The Hessian of $\lVert M\mathbf{x} - \mathbf{y} \rVert^2$ is $2M^\top M$ . For $M$ with columns $(1, 1, 1)$ and $(0, 1, 2)$ , find its entry in row 2, column 2

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

f(\mathbf{x})

Optimality conditions in several variables

The problem

The first-order condition

Rule: First-order condition

Second-order conditions

Rule: Second-order conditions

Local and global minima

Rule: Local and global

Quadratic functions

Rule: Minimum of a quadratic

When A is not positive definite

Least squares is a quadratic

Common mistakes

Optimality conditions

Summary card

Free further reading