5.8 Constrained extrema and Lagrange multipliers

To extremise a field f on the set where g = c, look for points where the gradient of f is a multiple of the gradient of g, because there the level curve of f touches the constraint without crossing it. The multiplier is a number you solve for, and it equals the rate at which the best value changes when the constraint moves. The proof reduces to an ordinary extremum by solving the constraint with the implicit function theorem, and a bordered Hessian decides between maximum and minimum.

You have a field $f$ and you may not look at the whole plane or space: only at points that satisfy an equation, such as a circle, a plane, or a budget. Where is $f$ largest on that set, and where is it smallest? The rule from 5.2 ( $\nabla f = O$ at an interior extremum) cannot be the answer, because the constraint set has no interior points: stepping off it breaks the constraint. In JEE you solved such problems by substituting one equation into the other to leave one variable. That works when the constraint can be solved for a variable, and the implicit function theorem of 5.7 says it can be, locally, at a regular point, even when you cannot write the formula. Lagrange’s idea is to do the substitution without doing it: the condition for an extremum can be written in a form where the symmetry between the variables is kept, and where the extra unknown $\lambda$ that appears turns out to be a quantity with a meaning.

Before you start

5.6: critical points, the second-derivative test, and why an absolute extremum on a compact set exists. 5.7: regular points, and level sets as graphs. 5.3: the gradient is perpendicular to level sets.

Quick checkThe minimum of

f(x, y) = x^2 + y^2

on the line

x + y = 2

is at

(1, 1)

. Is

\nabla f(1, 1) = O

Quick checkAt a point of the circle

x^2 + y^2 = 1

, which vector is perpendicular to the circle?

Quick checkFor

g(x, y, z) = x^2 + y^2 + z^2

, which points of the level set

g = 0

are regular points?

The picture: when two curves touch

Slide the dot along the blue constraint. The orange curves are level curves of $f$ . As the dot slides, it crosses some level curves and so $f$ changes: the plot on the right goes up or down. At a few special positions the plot is flat, and on the left the two arrows point the same way (or exactly opposite ways). There the level curve of $f$ through the dot is tangent to the constraint: it touches it and turns back, and the constraint stays on one side of it. That is the maximum or minimum. Choose the second and third pictures to see a minimum and the eigenvalue structure; choose the last one to see where the method breaks.

The idea, in words

Apostol’s picture (9.14) of the nearest point to the origin: inflate a ball (a level set of $f(x) = \lVert x \rVert$ ) from radius $0$ until it first touches the constraint surface. At the first contact the ball and the surface are tangent. Two tangent surfaces have the same tangent plane, hence the same normal line, hence parallel gradients. The first contact is the minimum of $f$ on the surface, since any smaller ball has not reached it.

Why· The same fact without pictures

Take any curve $r(t)$ lying in the constraint set, through the candidate point $a$ at $t = 0$ . The function $t \mapsto f(r(t))$ has an extremum at $t = 0$ , so its derivative is $0$ there, and by the path theorem of 5.3 that derivative is $\nabla f(a)\cdot r'(0)$ . So $\nabla f(a)$ is perpendicular to every tangent vector $r'(0)$ of the constraint. But $\nabla g(a)$ is also perpendicular to all of them. In the plane or in space with one constraint, the vectors perpendicular to the tangent vectors form a single line, so $\nabla f(a)$ and $\nabla g(a)$ lie on one line: $\nabla f(a) = \lambda\nabla g(a)$ .

Where this came from· Lagrange and the statics of constrained bodies

Joseph-Louis Lagrange wanted one method for the statics and dynamics of bodies whose parts are tied together by constraints (a bead on a wire, a rigid rod, the links of a chain). In his Mécanique analytique (1788) he combined the principle of virtual velocities, due to Johann Bernoulli, with the multipliers that now carry his name; the rule had appeared in his earlier work on the calculus of variations, and the 1788 treatise is where he stated it in its modern form. The mechanical meaning survives: in mechanics the multipliers are the forces by which the constraints push on the system, and the theorem later in this chapter shows that in optimisation the multiplier is the derivative of the best value with respect to the constraint, the price of the constraint.

Definitions and the theorem

Definition T

Constrained extremum

Let $f: U \to \mathbb R$ and $g = (g_1, \dots, g_m): U \to \mathbb R^m$ be fields on an open set $U \subseteq \mathbb R^n$ with $m \lt n$ , and let $S = \{x \in U : g(x) = c\}$ (the constraint set, the common level set of the $g_i$ ). A point $a \in S$ is a local constrained maximum of $f$ if there is a ball $B(a, r)$ with $f(x) \le f(a)$ for every $x \in S \cap B(a, r)$ ; a local constrained minimum with $\ge$ . Together: constrained extrema. As in 5.6, absolute ones compare with all of $S$ . This is the 376 definition: ‘a local extremum at $P$ on $g = k$ ’.

In one lineA point $a$ with $g(a) = c$ such that $f(x) \le f(a)$ (a maximum) or $f(x) \ge f(a)$ (a minimum) for all nearby $x$ that also satisfy $g(x) = c$ .

Why it existsIt is the precise form of 'largest or smallest value of $f$ on the constraint', and it only compares $f(a)$ with values on the constraint set, never with values off it.

Definition T

Lagrange multiplier

When $\nabla f(a) = \lambda_1\nabla g_1(a) + \dots + \lambda_m\nabla g_m(a)$ , the numbers $\lambda_1, \dots, \lambda_m$ are the Lagrange multipliers of $f$ with respect to the constraints at $a$ . The sign convention varies ( $f - \lambda g$ here, $f + \lambda g$ in some books); the points found are the same and only the sign of $\lambda$ changes.

In one lineA number $\lambda_i$ in the equation $\nabla f(a) = \sum_i\lambda_i\nabla g_i(a)$ ; there is one multiplier for each constraint.

Why it existsIt is the coefficient that expresses the gradient of $f$ in terms of the constraint gradients; it turns a search over a curved set into algebraic equations and, by the theorem below, measures how much the best value would change if the constraint were loosened.

Definition T

Lagrangian

The Lagrangian is $L(x, \lambda) = f(x) - \sum_{i=1}^m\lambda_i\big(g_i(x) - c_i\big)$ . Its partial derivatives are $\dfrac{\partial L}{\partial x_k} = \dfrac{\partial f}{\partial x_k} - \sum_i\lambda_i\dfrac{\partial g_i}{\partial x_k}$ (the $k$ -th component of $\nabla f - \sum\lambda_i\nabla g_i$ ) and $\dfrac{\partial L}{\partial\lambda_i} = -(g_i - c_i)$ (the $i$ -th constraint). Setting all $n + m$ of them to $0$ is the system the method solves.

In one lineThe field $L(x, \lambda) = f(x) - \sum_i\lambda_i\big(g_i(x) - c_i\big)$ of $n + m$ variables, whose critical points are exactly the solutions of $\nabla f = \sum\lambda_i\nabla g_i$ together with the constraints.

Why it existsIt packages the $n + m$ equations of the method into one 'find the critical points' problem, so that the machinery of 5.6 can be reused.

Theorem T MATH 376 Worksheet 3 #5 (m = 1, n = 3) and Warm-up; Apostol 9.14; Rudin Thm 9.28

Lagrange multiplier theorem

Let $f, g_1, \dots, g_m$ be continuously differentiable on an open set $U \subseteq \mathbb R^n$ , $m \lt n$ , and $S = \{g = c\}$ . Suppose $f|_S$ has a local extremum at $a \in S$ and $a$ is a regular point of $g$ . Then there are unique $\lambda_1, \dots, \lambda_m \in \mathbb R$ with

\nabla f(a) = \lambda_1\nabla g_1(a) + \dots + \lambda_m\nabla g_m(a).

In one lineIf $f, g_1, \dots, g_m$ are $C^1$ , $f$ has a local constrained extremum at $a$ , and $a$ is a regular point of $g$ (the gradients $\nabla g_i(a)$ are linearly independent), then $\nabla f(a) = \sum\lambda_i\nabla g_i(a)$ for unique numbers $\lambda_i$ .

Why it is trueIt reduces a problem on a curved set to $n + m$ equations in $n + m$ unknowns, and it names the one hypothesis that cannot be skipped: the constraint gradients must be independent.

ProofWorksheet 3 #5 (in space), Rudin Thm 9.28 (general)

The idea: At a regular point the implicit function theorem lets us solve the constraint for m of the variables as functions of the other n minus m, so the constraint set is a graph and f restricted to it is an ordinary function of n minus m free variables with an interior extremum. Its gradient is zero. Writing that gradient with the chain rule, and defining lambda to match the m solved coordinates, gives the equation in the other coordinates automatically.

Write

x = (u, w)

with

u \in \mathbb R^{n-m}

w \in \mathbb R^m

, and

a = (a_u, a_w)

, such that the

m \times m

matrix

D_wg(a)

is invertible.

The

m \times n

Jacobian

Dg(a)

has rank

m

(regular point), so some

m

of its columns are independent (2.6). Renumber the variables so that these are the last

m

columns. Then

D_wg(a)

is invertible.

There is a

C^1

function

h

near

a_u

with

h(a_u) = a_w

and

g(u, h(u)) = c

, and near

a

the constraint set is the graph

\{(u, h(u))\}

Implicit function theorem (5.7) for

g(u, w) - c = O

Define

\varphi(u) = f\big(u, h(u)\big)

. It has an ordinary local extremum at

a_u

, an interior point of an open set of

\mathbb R^{n-m}

Every

u

near

a_u

gives the point

(u, h(u))

S

near

a

, and every point of

S

near

a

is of this form. So

\varphi

inherits the extremum of

f|_S

at the point

a_u

\nabla\varphi(a_u) = O

Partial derivatives vanish at an interior extremum (5.2).

\nabla_uf(a) + Dh(a_u)^{\mathsf T}\,\nabla_wf(a) = O

Chain rule (5.4):

u \mapsto (u, h(u))

has Jacobian

\begin{bmatrix}I\\ Dh\end{bmatrix}

, so the gradient of the composite is

\nabla_uf + Dh^{\mathsf T}\nabla_wf

, with everything evaluated at

a

Dh(a_u) = -D_wg(a)^{-1}D_ug(a)

Differentiate the identity

g(u, h(u)) = c

(chain rule):

D_ug + D_wg\,Dh = 0

, and solve with the invertible

D_wg

Put

\lambda = \big(D_wg(a)^{\mathsf T}\big)^{-1}\nabla_wf(a) \in \mathbb R^m

Define

\lambda

so that the last

m

components of the claimed equation hold:

\nabla_wf = (D_wg)^{\mathsf T}\lambda = \sum_i\lambda_i\nabla_wg_i

. This is possible because

(D_wg)^{\mathsf T}

is invertible.This is the 'where does the idea come from' step. We have

m

numbers to choose and

m

equations to satisfy, and the matrix is invertible exactly because the point is regular.

\nabla_uf(a) = D_ug(a)^{\mathsf T}\lambda = \sum_i\lambda_i\nabla_ug_i(a)

Substitute

Dh = -D_wg^{-1}D_ug

into the equation of the fifth step; transposing gives

Dh^{\mathsf T} = -D_ug^{\mathsf T}\big(D_wg^{\mathsf T}\big)^{-1}

. Then

\nabla_uf = -Dh^{\mathsf T}\nabla_wf = D_ug^{\mathsf T}\big(D_wg^{\mathsf T}\big)^{-1}\nabla_wf = D_ug^{\mathsf T}\lambda

\nabla f(a) = \sum_i\lambda_i\nabla g_i(a)

, with unique

\lambda_i

\blacksquare

The

u

-components and the

w

-components together make the whole vector. Uniqueness: if two lists of multipliers worked, their difference would be a linear relation among the independent gradients

\nabla g_i(a)

, so it is zero.

Proof workshopRebuild the proof of the Lagrange multiplier theoremRudin Thm 9.28; MATH 376 Worksheet 3 #5

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Quick checkIn the proof, why does the extremum of

f|_S

a

become an ordinary extremum of

\varphi

with

\nabla\varphi = O

Why· The picture behind the proof, in space (the version from Worksheet 3 #5)

In $\mathbb R^3$ with one constraint $g = c$ and $\nabla g(P) \ne O$ , say $g_z(P) \ne 0$ . Near $P$ the level set is a graph $z = h(x, y)$ , parametrised by $r(u, v) = (u, v, h(u, v))$ , and the two tangent vectors $r_u$ , $r_v$ span the tangent plane (5.7). Differentiating $g(r) = c$ shows $\nabla g\cdot r_u = \nabla g\cdot r_v = 0$ ; differentiating $f(r)$ , which has a critical point, shows $\nabla f\cdot r_u = \nabla f\cdot r_v = 0$ . The vectors perpendicular to a plane in space form one line, so $\nabla f$ is a multiple of $\nabla g$ (here $\nabla g \ne O$ ). In the visualiser above, this is the red arrow lining up with the purple one.

Watch out· Two hypotheses the theorem needs, and one thing it does not say

(1) The point must be regular: $\nabla g(a) \ne O$ for one constraint, independent gradients for several. If it is not, the theorem says nothing, and the point must be examined separately (the cusp $y^2 = x^3$ in the examples). (2) $f, g$ must be $C^1$ . (3) The theorem is a necessary condition: it produces candidates. It does not say that an extremum exists, nor which candidate is the maximum. You need an existence argument (a continuous function on a compact set has a largest and a smallest value, 4.3 and 5.6) or a growth argument.

The recipe

A preview· The method, as used in MATH 376 (WS3 solution key)

Write the constraint as $g = c$ . List the points of the constraint where $\nabla g = O$ (or where the gradients of several constraints are dependent). They are candidates of their own.
Solve $\nabla f = \sum\lambda_i\nabla g_i$ together with $g = c$ : $n + m$ equations for $n$ coordinates and $m$ multipliers. The usual trick is to solve each coordinate in terms of $\lambda$ , substitute in the constraint, and find $\lambda$ ; or to divide one component equation by another (after checking the divisor is not $0$ ).
List all candidate points.
Evaluate $f$ at each candidate. Decide the maximum and the minimum by an existence argument (compact set, or $f \to \infty$ along every unbounded direction) or by geometry. If asked for a distance, use the squared distance (same minimiser, no square root).

Examples from the course

Worked example MATH 376 Worksheet 1 #5

Find the largest and smallest values of

f(x, y) = xy

on the circle

x^2 + y^2 = 1

Solution.

Set up. $g = x^2 + y^2$ , constraint $g = 1$ . $\nabla g = (2x, 2y)$ is zero only at the origin, which is not on the circle. Step 1 of the recipe: there are no singular candidates.
Write the equations. $\nabla f = (y, x) = \lambda(2x, 2y)$ , so $y = 2\lambda x$ and $x = 2\lambda y$ . Components of $\nabla f = \lambda\nabla g$ .
Eliminate $\lambda$ . Substitute $x = 2\lambda y$ into $y = 2\lambda x$ : $y = 4\lambda^2y$ . If $y = 0$ then $x = 0$ , not on the circle. So $y \ne 0$ and $4\lambda^2 = 1$ , $\lambda = \pm\frac12$ . Dividing by $y$ is allowed once we have checked $y = 0$ separately; this is the step where solutions are lost if you divide too early.
Find the points. $\lambda = \frac12$ gives $y = x$ and $2x^2 = 1$ : $\pm\big(\frac{\sqrt2}2, \frac{\sqrt2}2\big)$ , $f = \frac12$ . $\lambda = -\frac12$ gives $y = -x$ : $\pm\big(\frac{\sqrt2}2, -\frac{\sqrt2}2\big)$ , $f = -\frac12$ . Put each $\lambda$ in $y = 2\lambda x$ and then in the circle.
Decide. The circle is closed and bounded and $xy$ is continuous, so a largest and a smallest value exist (5.6, 4.3), and they are among the four candidates. Existence from compactness; the theorem only gives candidates.

Answer. Maximum $\frac12$ at the two points where $x, y$ have the same sign; minimum $-\frac12$ where they have opposite signs. (Check by substitution: $x = \cos t$ , $y = \sin t$ gives $xy = \frac12\sin2t$ .)

Your answerWhat is the largest value of

xy

on the circle

x^2 + y^2 = 1

Worked example MATH 376 Worksheet 3 #4

Find the point of the plane

x + 2y + z = 10

closest to

(1, 2, 0)

and the distance.

Solution.

Squared distance. Minimise $f = (x - 1)^2 + (y - 2)^2 + z^2$ subject to $g = x + 2y + z = 10$ . The squared distance has the same minimiser and no square root.
Singular points. $\nabla g = (1, 2, 1) \ne O$ everywhere. The theorem applies at every point.
Equations. $2(x - 1) = \lambda$ , $2(y - 2) = 2\lambda$ , $2z = \lambda$ , so $x = \frac\lambda2 + 1$ , $y = \lambda + 2$ , $z = \frac\lambda2$ . Solve each coordinate in terms of $\lambda$ .
Constraint. $\big(\frac\lambda2 + 1\big) + 2(\lambda + 2) + \frac\lambda2 = 3\lambda + 5 = 10$ , so $\lambda = \frac53$ . Substitute into the plane.
Point and distance. $(x, y, z) = \big(\frac{11}6, \frac{11}3, \frac56\big)$ and $f = \big(\frac56\big)^2 + \big(\frac53\big)^2 + \big(\frac56\big)^2 = \frac{150}{36}$ , so the distance is $\frac{5}{\sqrt6}$ . The offsets from $(1, 2, 0)$ are $\frac56, \frac53, \frac56$ .
Why a minimum exists. The plane is unbounded, but $f \to \infty$ far away, so $f$ has a smallest value; it must be at a candidate, and there is only one. Existence by growth.

Answer. $\big(\frac{11}6, \frac{11}3, \frac56\big)$ , distance $\frac5{\sqrt6} \approx 2.041$ . It agrees with the formula $\frac{\lvert1 + 4 + 0 - 10\rvert}{\sqrt{1 + 4 + 1}}$ . The offset from $(1, 2, 0)$ to the closest point is $\frac56(1, 2, 1)$ , parallel to the normal $\nabla g = (1, 2, 1)$ , as the picture says.

Your answerWhat is the shortest distance from

(1, 2, 0)

to the plane

x + 2y + z = 10

? (Give a decimal.)

Worked example MATH 376 Worksheet 1 #6

Find the extreme values of

f = x^2 + y^2 + z^2

on the line where the planes

x + y + z = 1

and

x - y + 2z = 2

meet.

Solution.

Check independence. $\nabla g_1 = (1, 1, 1)$ and $\nabla g_2 = (1, -1, 2)$ are not multiples of each other, at every point. Every point is regular; the two-constraint theorem applies.
Equations. $\nabla f = (2x, 2y, 2z) = \lambda_1(1, 1, 1) + \lambda_2(1, -1, 2)$ , so $x = \frac{\lambda_1 + \lambda_2}2$ , $y = \frac{\lambda_1 - \lambda_2}2$ , $z = \frac{\lambda_1 + 2\lambda_2}2$ . Solve each coordinate. (The Worksheet writes $L = f + \lambda(g_1 - 1) + \mu(g_2 - 2)$ , so its multipliers are the negatives of these; the points are the same.)
Constraints. $x + y + z = \frac{3\lambda_1 + 2\lambda_2}2 = 1$ and $x - y + 2z = \frac{2\lambda_1 + 6\lambda_2}2 = \lambda_1 + 3\lambda_2 = 2$ . So $3\lambda_1 + 2\lambda_2 = 2$ and $\lambda_1 + 3\lambda_2 = 2$ . Two linear equations in the two multipliers.
Solve. $\lambda_1 = \frac27$ , $\lambda_2 = \frac47$ . Then $(x, y, z) = \big(\frac37, -\frac17, \frac57\big)$ and $f = \frac{9 + 1 + 25}{49} = \frac57$ . Substitute.
Decide. The feasible set is a line and $f \to \infty$ along it, so the single candidate is the minimum and there is no maximum. Growth argument.

Answer. Minimum $\frac57$ at $\big(\frac37, -\frac17, \frac57\big)$ ; no maximum. The sympy lab below reports the multipliers $\frac27, \frac47$ for this same problem.

Worked example MATH 376 Worksheet 3 #2

Minimise

50x + 100y

subject to

100\sqrt{xy} = 1000

, with

x, y \gt 0

Solution.

Clean the constraint. $\sqrt{xy} = 10$ means $g = xy = 100$ for $x, y \gt 0$ . Same set, no square root.
Singular points. $\nabla g = (y, x) \ne O$ for $x, y \gt 0$ . No extra candidates.
Equations. $50 = \lambda y$ and $100 = \lambda x$ . Dividing the second by the first, $2 = x/y$ , so $x = 2y$ . $\lambda \ne 0$ (else $50 = 0$ ) and $y \gt 0$ , so the division is legal.
Constraint. $2y^2 = 100$ , $y = 5\sqrt2$ , $x = 10\sqrt2$ . Substitute $x = 2y$ into $xy = 100$ .
Cost and existence. The cost is $50\cdot10\sqrt2 + 100\cdot5\sqrt2 = 1000\sqrt2 \approx 1414$ . On the curve $y = 100/x$ the cost $50x + 10000/x \to \infty$ as $x \to 0^+$ and as $x \to \infty$ , so a minimum exists and it is the only candidate. Existence by growth.

Answer. $x = 10\sqrt2 \approx 14.14$ , $y = 5\sqrt2 \approx 7.07$ , minimum cost $1000\sqrt2 \approx 1414$ . The input with the lower price (here $x$ , at $50$ against $100$ ) is bought in the larger amount, $x/y = \frac{\text{price of }y}{\text{price of }x} = 2$ , which is what the equal exponents in $\sqrt{xy}$ give.

Worked example MATH 376 Worksheet 3 #3

Minimise

f = x

on the curve

y^2 = x^3

. Why does the Lagrange recipe fail?

Solution.

Write the constraint. $g = y^2 - x^3 = 0$ with $\nabla g = (-3x^2, 2y)$ . Step 1 of the recipe.
Singular points. $\nabla g = O$ only at $(0, 0)$ , which is on the curve. That point is a separate candidate, not covered by the theorem.
Try Lagrange. $\nabla f = (1, 0) = \lambda(-3x^2, 2y)$ : the first component needs $1 = -3\lambda x^2$ , so $x \ne 0$ ; the second needs $\lambda y = 0$ , so $y = 0$ (since $\lambda \ne 0$ ). But $y = 0$ and $y^2 = x^3$ force $x = 0$ . Contradiction. The system has no solutions at all.
The true minimum. On the curve $x^3 = y^2 \ge 0$ , so $x \ge 0$ , and $x = 0$ is attained at the origin. Direct inspection.

Answer. The minimum is $0$ at $(0, 0)$ , the single singular point, where no multiplier exists. This is why step 1 of the recipe (find the points with $\nabla g = O$ ) cannot be skipped. In the visualiser, choose the last picture and slide to $0$ .

Quick checkYou solve

\nabla f = \lambda\nabla g

with

g = c

and find exactly one solution. What else must you do before calling it the minimum?

Worked example MATH 376 Homework 1 #1

Find the shortest distance from

(1, 2, 3)

to the northern hemisphere

\{x^2 + y^2 + z^2 = 1,\ z \ge 0\}

Solution.

Use the whole sphere. Minimise $f = (x - 1)^2 + (y - 2)^2 + (z - 3)^2$ on $g = x^2 + y^2 + z^2 = 1$ . $\nabla g = 2(x, y, z) \ne O$ on the sphere. The constraint is smooth on the full sphere; the boundary $z = 0$ of the hemisphere would add a second kind of candidate, to be checked at the end.
Equations. $2(x - 1) = 2\lambda x$ , and similarly for $y, z$ , so $(1 - \lambda)x = 1$ , $(1 - \lambda)y = 2$ , $(1 - \lambda)z = 3$ . Move $\lambda x$ to the left and divide by $2$ .
Find $\lambda$ . Square and add: $(1 - \lambda)^2(x^2 + y^2 + z^2) = 1 + 4 + 9 = 14$ , and on the sphere the bracket is $1$ , so $1 - \lambda = \pm\sqrt{14}$ . Use the constraint.
The points. $(x, y, z) = \pm\dfrac{(1, 2, 3)}{\sqrt{14}}$ . Divide each equation by $1 - \lambda$ .
Choose. The plus sign has $z \gt 0$ , so $q = \frac{(1, 2, 3)}{\sqrt{14}}$ is in the hemisphere. The distance to $q$ is $\big(1 - \frac1{\sqrt{14}}\big)\sqrt{14} = \sqrt{14} - 1$ , and to $-q$ it is $\sqrt{14} + 1$ . $(1, 2, 3) - q$ is a multiple of $(1, 2, 3)$ .
The boundary. The closest point of the whole sphere already lies in the hemisphere, so the boundary circle $z = 0$ is not a competitor. A minimum over a larger set that lies in the smaller set is also the minimum over the smaller set.

Answer. $\sqrt{14} - 1 \approx 2.742$ , at $\frac{(1, 2, 3)}{\sqrt{14}}$ . (For a point $v$ outside the unit ball the closest point of the sphere is $v/\lVert v\rVert$ and the distance is $\lVert v\rVert - 1$ .)

Worked example new (the style of MATH 375 Lecture 24: interior critical points, then check the boundary)

Find the largest and smallest values of

f(x, y) = x^2 + 2y^2 - x

on the closed unit disc

x^2 + y^2 \le 1

Solution.

Interior. $\nabla f = (2x - 1,\ 4y) = O$ at $\big(\frac12, 0\big)$ , an interior point, with $f = \frac14 - \frac12 = -\frac14$ . The zero-gradient rule applies in the interior (5.6).
Boundary by a multiplier. On $x^2 + y^2 = 1$ : $2x - 1 = 2\lambda x$ and $4y = 2\lambda y$ . The second gives $y = 0$ or $\lambda = 2$ . If $y = 0$ , then $x = \pm1$ : $f(1, 0) = 0$ , $f(-1, 0) = 2$ . If $\lambda = 2$ , then $2x - 1 = 4x$ , $x = -\frac12$ , $y = \pm\frac{\sqrt3}2$ , and $f = \frac14 + \frac32 + \frac12 = \frac94$ . Case split on the factor $y$ rather than dividing by it.
Boundary by substitution. With $x = \cos t$ , $y = \sin t$ : $f = \cos^2t + 2\sin^2t - \cos t = 2 - \cos^2t - \cos t$ . As a function of $c = \cos t \in [-1, 1]$ this is $2 - c^2 - c$ , with derivative $-2c - 1 = 0$ at $c = -\frac12$ , value $\frac94$ , and endpoint values $0$ ( $c = 1$ ) and $2$ ( $c = -1$ ). The two methods give the same candidates and values.
Compare. Candidates: $-\frac14$ (interior), $0$ , $2$ , $\frac94$ (boundary). The disc is compact, so the largest and smallest values exist (5.6). Absolute extrema on a compact set: compare interior critical points with boundary candidates.

Answer. Maximum $\frac94$ at $\big(-\frac12, \pm\frac{\sqrt3}2\big)$ ; minimum $-\frac14$ at the interior point $\big(\frac12, 0\big)$ . Note that the minimum on the boundary alone is $0$ : the true minimum is not on the boundary.

Your answerWhat is the largest value of

x^2 + 2y^2 - x

on the closed unit disc?

Worked example Apostol 9.15 #2

Find the greatest and least distances from the origin to the curve

5x^2 + 6xy + 5y^2 = 8

Solution.

Set up. Minimise and maximise $f = x^2 + y^2$ (the squared distance) on $g = 5x^2 + 6xy + 5y^2 = 8$ . $\nabla g = (10x + 6y,\ 6x + 10y)$ is zero only at the origin, which is not on the curve. No singular candidates.
Equations. $\nabla f = (2x, 2y) = \lambda\nabla g$ , that is $\begin{bmatrix}5 & 3\\ 3 & 5\end{bmatrix}\begin{bmatrix}x\\ y\end{bmatrix} = \dfrac1\lambda\begin{bmatrix}x\\ y\end{bmatrix}$ . Here $\nabla g = 2A\begin{bmatrix}x\\ y\end{bmatrix}$ , so $\nabla f = \lambda\nabla g$ reads $2\begin{bmatrix}x\\ y\end{bmatrix} = 2\lambda A\begin{bmatrix}x\\ y\end{bmatrix}$ . We have $\lambda \ne 0$ , else $x = y = 0$ , which is off the curve. Dividing by $2\lambda$ says $(x, y)$ is an eigenvector of $A = \begin{bmatrix}5 & 3\\ 3 & 5\end{bmatrix}$ with eigenvalue $\frac1\lambda$ .
Eigenvalues. $A$ has eigenvalues $8$ (eigenvector $(1, 1)$ ) and $2$ (eigenvector $(1, -1)$ ). Trace $10$ , determinant $16$ : $\mu^2 - 10\mu + 16 = 0$ .
Points. Along $(1, 1)$ : $(x, y) = s(1, 1)$ and $g = 16s^2 = 8$ , so $s^2 = \frac12$ , $f = 2s^2 = 1$ . Along $(1, -1)$ : $g = 4s^2 = 8$ , $s^2 = 2$ , $f = 2s^2 = 4$ . Substitute in the constraint, then compute $f = x^2 + y^2$ .
Decide. The curve is closed and bounded, so both extremes are attained; they are the two values found.

Answer. Nearest distance $1$ , at $\pm\big(\frac{\sqrt2}2, \frac{\sqrt2}2\big)$ ; farthest distance $2$ , at $\pm(\sqrt2, -\sqrt2)$ . The multiplier turned the problem into an eigenvalue problem: for a quadratic constraint $x^{\mathsf T}Ax = 8$ the squared distance is $8/\mu$ where $\mu$ runs over the eigenvalues, and the principal axes of 3.2 are the ends of the ellipse’s axes. (Third picture of the visualiser.)

Your answerWhat is the greatest distance from the origin to the curve

5x^2 + 6xy + 5y^2 = 8

Worked example Apostol 9.15 #7

Find the shortest distance from

(1, 0)

to the parabola

y^2 = 4x

Solution.

Set up. Minimise $f = (x - 1)^2 + y^2$ on $g = y^2 - 4x = 0$ . $\nabla g = (-4,\ 2y)$ is never $O$ . No singular points.
Equations. $2(x - 1) = -4\lambda$ and $2y = 2\lambda y$ . Components of $\nabla f = \lambda\nabla g$ .
Split on the second. $y(1 - \lambda) = 0$ . If $y = 0$ , then $x = 0$ (from $y^2 = 4x$ ), the point $(0, 0)$ . If $\lambda = 1$ , then $2(x - 1) = -4$ gives $x = -1$ , and $y^2 = -4$ : impossible. Never divide by $y$ without treating $y = 0$ separately.
Conclude. The only candidate is $(0, 0)$ , at distance $1$ . A minimum exists since $f \to \infty$ far along the curve. One candidate plus an existence argument.

Answer. $1$ , at the vertex $(0, 0)$ . Check by substitution: on the parabola $f = (x - 1)^2 + 4x = (x + 1)^2$ for $x \ge 0$ , smallest at $x = 0$ .

Which candidate is which? The second-order test

The theorem produces candidates. For a maximum or minimum we used geometry or existence so far. When that is not available, there is a second-order test, which is the Hessian test of 5.6 restricted to the tangent space of the constraint.

Definition B

Bordered Hessian

Let $f, g_1, \dots, g_m$ be $C^2$ , $a$ a regular point with multipliers $\lambda_i$ . The Hessian of the Lagrangian in the $x$ variables is $H = D^2f(a) - \sum_{i}\lambda_iD^2g_i(a)$ , a symmetric $n \times n$ matrix (5.5). The bordered Hessian is $B = \begin{bmatrix}0 & Dg(a)\\ Dg(a)^{\mathsf T} & H\end{bmatrix}$ , with the $m \times n$ block $Dg(a)$ above and its transpose beside $H$ . The tangent space is $T = \ker Dg(a)$ (5.7).

In one lineThe $(n + m) \times (n + m)$ symmetric matrix $B = \begin{bmatrix}0 & Dg(a)\\ Dg(a)^{\mathsf T} & H\end{bmatrix}$ , where $H = D^2f(a) - \sum\lambda_iD^2g_i(a)$ is the Hessian in $x$ of the Lagrangian.

Why it existsIt puts the constraint gradients around the Hessian like a border, so that a single determinant (for two variables) or a few minors decide between maximum and minimum on the tangent space.

Theorem B Rudin-style via 5.4 and 5.6; Apostol 9.14 (remark); Spivak ch. 5

Second-order test for constrained extrema

Let $f, g_i$ be $C^2$ near a regular point $a$ of $g$ with $g(a) = c$ , $\nabla f(a) = \sum\lambda_i\nabla g_i(a)$ , $H = D^2f(a) - \sum\lambda_iD^2g_i(a)$ and $T = \ker Dg(a)$ .

(i) If $v^{\mathsf T}Hv \gt 0$ for every $v \in T\setminus\{O\}$ , then $a$ is a strict local constrained minimum of $f$ . If $v^{\mathsf T}Hv \lt 0$ for every such $v$ , a strict local constrained maximum.

(ii) If $a$ is a local constrained minimum, then $v^{\mathsf T}Hv \ge 0$ for all $v \in T$ ; for a local constrained maximum, $v^{\mathsf T}Hv \le 0$ .

In one lineAt a regular point with multipliers $\lambda_i$ : if $v^{\mathsf T}Hv \gt 0$ for all nonzero $v$ in the tangent space then $a$ is a strict local constrained minimum; if $\lt 0$ , a strict local maximum; a local minimum forces $v^{\mathsf T}Hv \ge 0$ on the tangent space.

Why it is trueIt is the second-derivative test with the constraint accounted for: only the directions along the constraint matter, and the curvature of the constraint itself enters through the term $-\sum\lambda_iD^2g_i$ in $H$ .

ProofSpivak ch. 5; this version uses 5.4 and 5.6

The idea: Parametrise the constraint by the free variables, as in the proof of the multiplier theorem. On the constraint, f equals the Lagrangian, and the Lagrangian has zero gradient at a, so the second derivative of the restricted function is the Hessian of the Lagrangian pulled back to the tangent space. Then apply the ordinary second-derivative test of 5.6 to the restricted function.

Solve the constraint near

a

w = h(u)

with

h

of class

C^2

, and let

X(u) = (u, h(u))

As in the multiplier theorem. Since

f, g

are

C^2

h

C^2

Dh = -D_wg^{-1}D_ug

is built from

C^1

functions.

Define

\varphi(u) = f(X(u)) = L(X(u), \lambda)

with

L(x, \lambda) = f(x) - \sum\lambda_i(g_i(x) - c_i)

and

\lambda

the fixed multipliers.

For

x

on the constraint,

g(x) = c

, so the terms

\lambda_i(g_i - c_i)

vanish:

L(x, \lambda) = f(x)

there.

a_u

D^2\varphi(a_u) = Z^{\mathsf T}HZ

Second derivatives of a composite (5.4):

D^2\varphi = Z^{\mathsf T}\,(D^2L)\,Z + \sum_k\dfrac{\partial L}{\partial x_k}\,D^2X_k

, where

Z = DX(a_u) = \begin{bmatrix}I\\ Dh\end{bmatrix}

. The sum has the factors

\frac{\partial L}{\partial x_k}(a) = 0

, because

\nabla_xL(a) = \nabla f(a) - \sum\lambda_i\nabla g_i(a) = O

v^{\mathsf T}Hv \gt 0

T\setminus\{O\}

says exactly that

D^2\varphi(a_u)

is positive definite.

5.7: the columns of

Z

are the tangent vectors

(e_j, Dh\,e_j)

, a basis of

T = \ker Dg(a)

. So

v \in T

means

v = Zs

for a unique

s \in \mathbb R^{n-m}

, and

v^{\mathsf T}Hv = s^{\mathsf T}Z^{\mathsf T}HZs

Positive definite:

\varphi

has a strict local minimum at

a_u

, hence

f

has a strict local constrained minimum at

a

. The statements for maxima and (ii) are the same with signs changed or with ‘semidefinite’.

\blacksquare

\nabla\varphi(a_u) = O

(proof of the multiplier theorem) and the second-derivative test of 5.6, together with its converse for a minimum (a minimum needs a positive semidefinite Hessian).

Corollary B standard; Apostol 9.14 remark

Bordered determinant test in two variables

Let $n = 2$ , $m = 1$ , $a$ a regular point, $g_x = g_x(a)$ , $g_y = g_y(a)$ and $L_{xx}, L_{xy}, L_{yy}$ the entries of $H$ . Then

\det B = \det\begin{bmatrix}0 & g_x & g_y\\ g_x & L_{xx} & L_{xy}\\ g_y & L_{xy} & L_{yy}\end{bmatrix} = -\big(g_x^2L_{yy} - 2g_xg_yL_{xy} + g_y^2L_{xx}\big).

If $\det B \gt 0$ , $a$ is a strict local constrained maximum; if $\det B \lt 0$ , a strict local constrained minimum.

In one lineFor $f(x, y)$ with one constraint $g$ at a regular point: $\det B \gt 0$ means a strict local constrained maximum, $\det B \lt 0$ a strict local constrained minimum, where $B$ is the $3 \times 3$ bordered Hessian.

Why it is trueIt gives a one-line test for the most common case, and shows how the bordering encodes the restriction to the tangent line.

Proofstandard

The idea: The tangent space is the line spanned by (minus g_y, g_x). Compute v-transpose H v for that vector and compare it with the determinant.

\det B = -g_x^2L_{yy} + 2g_xg_yL_{xy} - g_y^2L_{xx}

Expand along the first row:

0 - g_x\big(g_xL_{yy} - L_{xy}g_y\big) + g_y\big(g_xL_{xy} - L_{xx}g_y\big)

The tangent line is spanned by

v = (-g_y, g_x)

T = \ker Dg = \{v : g_xv_1 + g_yv_2 = 0\}

is the line through

v = (-g_y, g_x)

(nonzero since the point is regular).

v^{\mathsf T}Hv = g_y^2L_{xx} - 2g_xg_yL_{xy} + g_x^2L_{yy} = -\det B

Multiply out

v^{\mathsf T}Hv = L_{xx}v_1^2 + 2L_{xy}v_1v_2 + L_{yy}v_2^2

with

v_1 = -g_y

v_2 = g_x

\det B \lt 0

gives

v^{\mathsf T}Hv \gt 0

: a strict local minimum;

\det B \gt 0

gives a strict local maximum.

Every nonzero tangent vector is a nonzero multiple of

v

, so

w^{\mathsf T}Hw

has the same sign as

v^{\mathsf T}Hv

. Then the second-order test:

-\det B \gt 0

means minimum,

\lt 0

means maximum.

\blacksquare

For more variables the same idea is a test on the leading principal minors of $B$ (the determinants of its top-left $k \times k$ blocks). With $n$ variables and $m$ constraints, look at the $n - m$ minors of orders $2m + 1, \dots, m + n$ . If all have the sign of $(-1)^m$ the point is a strict local minimum. If they alternate in sign, starting with the sign of $(-1)^{m + 1}$ at order $2m + 1$ , it is a strict local maximum. For $n = 2$ , $m = 1$ there is the single minor $\det B$ of order $3$ , and the rule is the one proved above. We state the general rule without proof; its source is the same reduction to the tangent space. Check on $x^2 + y^2 + z^2$ with the constraint $x + y + z = 1$ ( $n = 3$ , $m = 1$ ): the minors of orders $3$ and $4$ are $-4$ and $-12$ , both with the sign of $(-1)^1$ , so the point is a minimum.

Worked example MATH 376 Worksheet 1 #5, second-order check (new)

Classify the four candidates of

xy

x^2 + y^2 = 1

with the bordered Hessian.

Solution.

Hessian of the Lagrangian. With $L = xy - \lambda(x^2 + y^2 - 1)$ : $L_{xx} = L_{yy} = -2\lambda$ , $L_{xy} = 1$ . $D^2f = \begin{bmatrix}0 & 1\\ 1 & 0\end{bmatrix}$ and $D^2g = 2I$ .
At $\big(\frac{\sqrt2}2, \frac{\sqrt2}2\big)$ , $\lambda = \frac12$ . $L_{xx} = L_{yy} = -1$ , $g_x = g_y = \sqrt2$ . $g_x^2L_{yy} - 2g_xg_yL_{xy} + g_y^2L_{xx} = -2 - 4 - 2 = -8$ , so $\det B = +8 \gt 0$ . Positive: maximum.
At $\big(\frac{\sqrt2}2, -\frac{\sqrt2}2\big)$ , $\lambda = -\frac12$ . $L_{xx} = L_{yy} = 1$ , $g_x = \sqrt2$ , $g_y = -\sqrt2$ . The bracket is $2 + 4 + 2 = 8$ , so $\det B = -8 \lt 0$ . Negative: minimum.
The other two are the negatives of these points; the same values hold by symmetry.

Answer. Maxima (value $\frac12$ ) where $x, y$ have the same sign, minima (value $-\frac12$ ) where they differ, in agreement with the compactness argument. A second example: minimising $x + y$ on $xy = 1$ , $x \gt 0$ : at $(1, 1)$ , $\lambda = 1$ , $L_{xx} = L_{yy} = 0$ , $L_{xy} = -1$ , $g_x = g_y = 1$ , bracket $= 0 + 2 + 0 = 2$ , $\det B = -2 \lt 0$ : a minimum, value $2$ (the inequality $x + \frac1x \ge 2$ ).

Quick checkAt a candidate for the problem 'maximise

f

g = c

' the bordered determinant is

\det B = -6

(two variables, one constraint). What is the candidate?

What the multiplier means

Theorem B standard (the shadow price of economics); Lagrange's mechanical interpretation

The multiplier is the price of the constraint

Let $f, g$ be $C^1$ with $m = 1$ , and suppose for $c$ in an interval there is a $C^1$ curve $c \mapsto x^*(c)$ of regular constrained extrema with $g(x^*(c)) = c$ and $\nabla f(x^*(c)) = \lambda(c)\nabla g(x^*(c))$ . Then $V(c) = f(x^*(c))$ has $V'(c) = \lambda(c)$ .

In one lineIf the constrained optimum $x^*(c)$ depends differentiably on $c$ and $V(c) = f(x^*(c))$ , then $V'(c) = \lambda(c)$ : the multiplier is the rate at which the best value changes when the constraint $g = c$ is moved.

Why it is trueIt explains why the multiplier is worth computing: it tells you how much a unit of loosening the constraint is worth (a price), and its size tells you how binding the constraint is.

Proofstandard

The idea: Differentiate V with the chain rule, replace the gradient of f by lambda times the gradient of g, and differentiate the constraint to see that the remaining dot product equals 1.

V'(c) = \nabla f(x^*(c))\cdot x^{*\prime}(c)

Chain rule along the curve

x^*(c)

(5.3).

= \lambda(c)\,\nabla g(x^*(c))\cdot x^{*\prime}(c)

The multiplier equation at

x^*(c)

\nabla g(x^*(c))\cdot x^{*\prime}(c) = 1

, so

V'(c) = \lambda(c)

\blacksquare

Differentiate the identity

g(x^*(c)) = c

with the chain rule: the right side has derivative

1

.This is the whole content: moving the constraint by

dc

moves the point by

dx

with

\nabla g\cdot dx = dc

, and the first-order change of

f

\lambda\,dc

Worked example

Check the price theorem on: minimise

x^2 + y^2

subject to

x + y = c

Solution.

Solve. $\nabla f = (2x, 2y) = \lambda(1, 1)$ , so $x = y = \frac\lambda2$ , and the constraint gives $\lambda = c$ , $x = y = \frac c2$ . Lagrange.
The best value. $V(c) = \frac{c^2}4 + \frac{c^2}4 = \frac{c^2}2$ . Substitute.
Compare. $V'(c) = c = \lambda(c)$ . The theorem holds: loosening $x + y = c$ by one unit raises the minimum squared distance at rate $c$ .

Answer. $V'(c) = \lambda = c$ . For several constraints, $\partial V/\partial c_i = \lambda_i$ .

Convexity: when a candidate is automatically the best

Definition B

Convex function

A set $C \subseteq \mathbb R^n$ is convex if it contains the segment between any two of its points (a ball, a plane, all of $\mathbb R^n$ ). A function $f: C \to \mathbb R$ is a convex function if $f\big(tx + (1 - t)y\big) \le tf(x) + (1 - t)f(y)$ for all $x, y \in C$ and $t \in [0, 1]$ , that is, the graph lies below every chord. It is concave if $-f$ is convex. Examples: $\lVert x\rVert^2$ , $e^x$ , $x^{\mathsf T}Ax$ with $A$ positive semidefinite; $\ln x$ is concave.

In one lineA function $f$ on a convex set with $f\big(tx + (1 - t)y\big) \le tf(x) + (1 - t)f(y)$ for all $x, y$ and $t \in [0, 1]$ : the graph lies below every chord.

Why it existsIt is the property that makes every critical point a global minimum, which is why convex problems are the ones that optimisation solves reliably (5.10).

Theorem B standard (Boyd and Vandenberghe, Convex Optimization, 3.1.3)

Gradient inequality for convex functions

If $f$ is convex and differentiable on an open convex set $C$ , then for all $x, y \in C$ : $f(y) \ge f(x) + \nabla f(x)\cdot(y - x)$ .

In one lineA differentiable convex function lies above each of its tangent planes: $f(y) \ge f(x) + \nabla f(x)\cdot(y - x)$ .

Why it is trueIt says the linearization is a lower bound, so a zero gradient forces the global minimum; it also drives the convergence proofs of gradient descent.

Proofstandard

The idea: Compare the chord with the tangent: the difference quotient of f in the direction y minus x increases with the step, so it is at most its value at the full step, and its limit at step 0 is the directional derivative.

f(x + t(y - x)) \le (1 - t)f(x) + tf(y)

Convexity with the point

x + t(y - x) = (1 - t)x + ty

0 \lt t \le 1

\dfrac{f(x + t(y - x)) - f(x)}{t} \le f(y) - f(x)

Subtract

f(x)

and divide by

t \gt 0

\nabla f(x)\cdot(y - x) \le f(y) - f(x)

Let

t \to 0^+

: the left side tends to

f'(x; y - x) = \nabla f(x)\cdot(y - x)

by 5.3.

\blacksquare

Theorem B standard

Positive semidefinite Hessian implies convex

Let $f$ be $C^2$ on an open convex set $C$ with $v^{\mathsf T}H_f(x)v \ge 0$ for all $x \in C$ , $v \in \mathbb R^n$ . Then $f$ is convex on $C$ .

In one lineIf $f$ is $C^2$ on an open convex set and its Hessian is positive semidefinite everywhere, then $f$ is convex; in particular $\tfrac12x^{\mathsf T}Ax - b^{\mathsf T}x$ is convex when $A$ is symmetric positive semidefinite.

Why it is trueIt turns convexity into the eigenvalue test of 3.2, so you can check it for any smooth function.

Proofstandard

The idea: Show the tangent-plane inequality on each segment with the one-variable mean value theorem, then average the two tangent-plane inequalities at the point on the chord.

\psi'

is non-decreasing on

[0, 1]

(its derivative is

\ge 0

, mean value theorem of 1.4).

Fix

x, y

and put

\psi(t) = f(x + t(y - x))

. Then

\psi'(t) = \nabla f(\cdot)\cdot(y - x)

and

\psi''(t) = (y - x)^{\mathsf T}H_f(\cdot)(y - x) \ge 0

(chain rule twice, 5.4).

f(y) - f(x) \ge \psi'(0) = \nabla f(x)\cdot(y - x)

Mean value theorem:

\psi(1) - \psi(0) = \psi'(\xi)

for some

\xi \in (0, 1)

, and

\psi'(\xi) \ge \psi'(0)

tf(x) + (1 - t)f(y) \ge f(z) = f(tx + (1 - t)y)

\blacksquare

Apply this at

z = tx + (1 - t)y

twice:

f(x) \ge f(z) + \nabla f(z)\cdot(x - z)

and

f(y) \ge f(z) + \nabla f(z)\cdot(y - z)

. Multiply by

t

and

1 - t

and add: the gradient terms cancel because

t(x - z) + (1 - t)(y - z) = O

Corollary B standard

A convex Lagrangian gives a global minimum

Suppose $\nabla_xL(a, \lambda) = O$ , $g(a) = c$ and $L(\cdot, \lambda)$ is convex and differentiable. Then $f(x) \ge f(a)$ for every $x$ with $g(x) = c$ . In particular this holds whenever $f$ is convex and the constraints are linear, $Mx = c$ .

In one lineIf $x \mapsto L(x, \lambda) = f(x) - \sum\lambda_i(g_i(x) - c_i)$ is convex and $a$ satisfies $\nabla f(a) = \sum\lambda_i\nabla g_i(a)$ and $g(a) = c$ , then $a$ is an absolute minimum of $f$ on $\{g = c\}$ .

Why it is trueThis is the case where the recipe needs no existence argument and no second-order test: for convex $f$ with linear constraints (least squares, quadratic programs, maximum entropy) every Lagrange point is the global optimum.

Proofstandard

The idea: On the constraint set f equals the Lagrangian; a convex function with zero gradient at a is minimal at a.

For feasible

x

f(x) = L(x, \lambda)

and

f(a) = L(a, \lambda)

For

g(x) = c

the terms

\lambda_i(g_i - c_i)

vanish.

L(x, \lambda) \ge L(a, \lambda) + \nabla_xL(a, \lambda)\cdot(x - a) = L(a, \lambda)

Gradient inequality for the convex function

L(\cdot, \lambda)

, with

\nabla_xL(a, \lambda) = O

f(x) \ge f(a)

for all feasible

x

Combine. If

f

is convex and

g_i

linear, then

L

is convex (sum of a convex and a linear function).

\blacksquare

Quick checkMinimise

\lVert x\rVert^2

on the set

Mx = c

(an affine subspace). You solve

2x = M^{\mathsf T}\lambda

Mx = c

and find one solution. What does the corollary say?

Where it is used

Used inside maths· Inside maths: eigenvalues, inequalities and minimum-norm solutions

Eigenvalues are Lagrange multipliers. The maximum of $x^{\mathsf T}Ax$ on $\lVert x\rVert = 1$ , for $A$ symmetric, is found by $\nabla(x^{\mathsf T}Ax) = 2Ax = \lambda\cdot2x$ , so every candidate is an eigenvector and the value there is $x^{\mathsf T}Ax = \lambda$ . The sphere is compact, so the maximum is attained: it is the largest eigenvalue. This is the Rayleigh bound used in 5.6, and it proves the spectral theorem’s first step (3.1). The same argument with $A^{\mathsf T}A$ shows $\sigma_1 = \max_{\lVert x\rVert = 1}\lVert Ax\rVert$ (3.4). Inequalities. The maximum of $a\cdot x$ on $\lVert x\rVert = 1$ is $\lVert a\rVert$ (the Cauchy–Schwarz inequality, problem below). To maximise $xyz$ on $x + y + z = s$ with $x, y, z \ge 0$ : the maximum exists on the compact triangle and is not on the boundary (where $xyz = 0$ ); $\nabla = (yz, xz, xy) = \lambda(1, 1, 1)$ forces $x = y = z = \frac s3$ ; so $xyz \le \big(\frac s3\big)^3$ , the AM–GM inequality for three numbers. Minimum-norm solutions. Among all solutions of an underdetermined system $Mx = c$ the shortest is $x = M^{\mathsf T}(MM^{\mathsf T})^{-1}c$ (the corollary above): for the two planes of Worksheet 1 #6 this is the point $\big(\frac37, -\frac17, \frac57\big)$ , whose norm squared is $\frac57$ .

Used in the real world· Entropy, portfolios, margins and budgets: four real Lagrange problems

Maximum entropy (physics and machine learning). Among all probability distributions $p = (p_1, \dots, p_n)$ the entropy $H(p) = -\sum p_i\ln p_i$ measures how spread out $p$ is. E. T. Jaynes (1957) proposed this as a rule of inference: among all distributions that fit what you know, pick the one with the largest entropy, because it assumes nothing more. Maximise it subject to $\sum p_i = 1$ : $-\ln p_i - 1 = \lambda$ for every $i$ , so all $p_i$ are equal, $p_i = \frac1n$ , $H = \ln n$ (for $n = 8$ : $\ln8 = 2.079$ nats, which is $3$ bits). Add a constraint on the average of a quantity $E_i$ (energy): $\sum p_iE_i = e$ . The equation becomes $-\ln p_i - 1 = \lambda_0 + \beta E_i$ , so $p_i = e^{-\beta E_i}/Z$ with $Z = \sum e^{-\beta E_i}$ , the Boltzmann distribution, and the multiplier $\beta$ is the inverse temperature. The Hessian of $H$ is $-\operatorname{diag}(1/p_i)$ , negative definite, so $H$ is concave, and the corollary applied to $-H$ (convex) says this is the global maximum. Numbers: three levels with $E = (0, 1, 2)$ and mean energy $\frac12$ : with $x = e^{-\beta}$ the mean is $\frac{x + 2x^2}{1 + x + x^2} = \frac12$ , that is $3x^2 + x - 1 = 0$ , $x = \frac{-1 + \sqrt{13}}6 = 0.4343$ , $p = (0.616, 0.268, 0.116)$ , $H = 0.901$ nats against $\ln3 = 1.099$ for the uniform distribution (which has mean $1$ ). For a six-sided die forced to average $4.5$ , the maximum-entropy distribution has $\beta = -0.371$ and $p = (0.054, 0.079, 0.114, 0.165, 0.240, 0.347)$ , $H = 1.614$ nats against $\ln6 = 1.792$ . And the softmax of a neural network is the same: maximising $\sum p_iz_i + H(p)$ over distributions gives $p_i = e^{z_i}/\sum_je^{z_j}$ with the maximum value $\ln\sum_je^{z_j}$ , so the output layer of a classifier (3.8, 5.10) returns the maximum-entropy distribution compatible with its scores $z_i$ .

Portfolio optimisation (finance). Harry Markowitz (1952) proposed choosing portfolio weights $w$ to minimise the variance $w^{\mathsf T}\Sigma w$ for a target expected return: constraints $\mathbf 1^{\mathsf T}w = 1$ and $\mu^{\mathsf T}w = r$ . Lagrange gives $2\Sigma w = \lambda_1\mathbf 1 + \lambda_2\mu$ , and together with the two constraints this is one linear system (its matrix is the bordered matrix $\begin{bmatrix}2\Sigma & \mathbf 1 & \mu\\ \mathbf 1^{\mathsf T} & 0 & 0\\ \mu^{\mathsf T} & 0 & 0\end{bmatrix}$ ). Take three assets with expected returns $\mu = (6\%, 10\%, 14\%)$ , standard deviations $20\%, 30\%, 40\%$ and covariances $\Sigma_{12} = 0.006$ , $\Sigma_{23} = 0.012$ , $\Sigma_{13} = 0$ (so $\Sigma = \begin{bmatrix}0.04 & 0.006 & 0\\ 0.006 & 0.09 & 0.012\\ 0 & 0.012 & 0.16\end{bmatrix}$ ). The target $r = 9\%$ gives $w = (0.485, 0.281, 0.235)$ with standard deviation $16.9\%$ . Dropping the return constraint (only $\mathbf 1^{\mathsf T}w = 1$ ) gives the minimum-variance portfolio $w = \dfrac{\Sigma^{-1}\mathbf 1}{\mathbf 1^{\mathsf T}\Sigma^{-1}\mathbf 1} = (0.622, 0.231, 0.147)$ with standard deviation $16.2\%$ and return $8.1\%$ . The quadratic objective is convex, so these Lagrange points are global minima (corollary). (Weights here happen to be positive; a ban on short selling adds inequality constraints.)

Support vector machines (a light look). To separate points with labels $y_i = \pm1$ by a plane $w\cdot x + b = 0$ with the widest empty margin, minimise $\frac12\lVert w\rVert^2$ subject to $y_i(w\cdot x_i + b) \ge 1$ . These are inequality constraints; the Lagrangian $\frac12\lVert w\rVert^2 - \sum\alpha_i\big(y_i(w\cdot x_i + b) - 1\big)$ now needs multipliers $\alpha_i \ge 0$ (the Karush–Kuhn–Tucker conditions, B). Setting the derivatives in $w$ and $b$ to zero gives $w = \sum\alpha_iy_ix_i$ and $\sum\alpha_iy_i = 0$ , and substituting back leaves the dual problem: maximise $\sum\alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,x_i\cdot x_j$ . It involves the data only through dot products $x_i\cdot x_j$ , which is why one can replace them by kernels. Tiny example: $x_1 = (2, 0)$ with $y_1 = +1$ and $x_2 = (0, 0)$ with $y_2 = -1$ . The constraint $\sum\alpha_iy_i = 0$ forces $\alpha_1 = \alpha_2 = \alpha$ , the dual is $2\alpha - \frac12\alpha^2\lVert x_1 - x_2\rVert^2 = 2\alpha - 2\alpha^2$ , maximal at $\alpha = \frac12$ , and $w = \alpha(x_1 - x_2) = (1, 0)$ . From $y_1(w\cdot x_1 + b) = 1$ : $2 + b = 1$ , $b = -1$ . The plane is $x = 1$ , halfway between the points, and the margin from each point is $1/\lVert w\rVert = 1$ .

Economics: budgets and shadow prices. A consumer with income $m$ buys $x$ and $y$ at prices $p_x, p_y$ to maximise $U = x^{0.4}y^{0.6}$ subject to $p_xx + p_yy = m$ . Lagrange gives $U_x = \lambda p_x$ and $U_y = \lambda p_y$ , so the marginal rate of substitution $U_x/U_y$ equals the price ratio $p_x/p_y$ , and $x = \frac{0.4m}{p_x}$ , $y = \frac{0.6m}{p_y}$ . With $m = 100$ , $p_x = 2$ , $p_y = 5$ : $x = 20$ , $y = 12$ , $U = 20^{0.4}12^{0.6} = 14.72$ , and $\lambda = U_x/p_x = 0.1472 = U/m$ . By the price theorem, $\lambda$ is the utility gained per extra unit of money: raising $m$ from $100$ to $101$ raises the best utility by $0.147$ (here $U$ is homogeneous of degree $1$ , so the best utility is exactly $0.1472\,m$ ).

Your answerIn the maximum-entropy example with energies

0, 1, 2

and mean energy

\frac12

, what is

x = e^{-\beta}

? (Give a decimal.)

Your answerA consumer maximises

U = x^{0.4}y^{0.6}

with budget

100

and prices

p_x = 2

p_y = 5

. What is the best amount of

x

Python labSolve the Lagrange system with sympy and check against brute force

import numpy as np
import sympy as sp

x, y, z = sp.symbols('x y z', real=True)

def lagrange(f, gs, vs):
    """Solve grad f = sum(l_i grad g_i) with g_i = 0. Returns (point, multipliers, f value) triples."""
    ls = sp.symbols('l1:%d' % (len(gs) + 1), real=True)
    L = f - sum(l * g for l, g in zip(ls, gs))
    eqs = [sp.diff(L, v) for v in vs] + list(gs)
    out = []
    for s in sp.solve(eqs, list(vs) + list(ls), dict=True):
        out.append(([s[v] for v in vs], [s[l] for l in ls], sp.simplify(f.subs(s))))
    return out

print("A. xyz on the unit sphere")
for p, l, val in lagrange(x*y*z, [x**2 + y**2 + z**2 - 1], [x, y, z]):
    print("  ", [sp.nsimplify(c) for c in p], " lambda =", l[0], " f =", val, "~", round(float(val), 5))

print("B. x^2+y^2+z^2 on x+y+z=1 and x-y+2z=2")
for p, l, val in lagrange(x**2 + y**2 + z**2, [x + y + z - 1, x - y + 2*z - 2], [x, y, z]):
    print("  ", p, " multipliers =", l, " f =", val)

print("C. minimise x on y^2 = x^3: the recipe finds")
print("  ", lagrange(x, [y**2 - x**3], [x, y]), " (no candidates, yet the minimum 0 is at the origin)")

rng = np.random.default_rng(0)
v = rng.normal(size=(400000, 3)); v /= np.linalg.norm(v, axis=1)[:, None]
vals = v[:, 0] * v[:, 1] * v[:, 2]
print("sampled max, min of xyz on the sphere:", vals.max().round(4), vals.min().round(4), "  1/(3*sqrt(3)) =", round(1/(3*3**0.5), 4))

Try this. Run it. Problem A (xyz on the sphere) has fourteen solutions: six on the axes, where xyz = 0 and the point is a saddle of f on the sphere, and eight at the corners of a cube, where xyz is plus or minus 0.19245. The brute-force sampling agrees that these are the largest and smallest values. Problem B reports the multipliers 2/7 and 4/7. Problem C returns the empty list: the recipe finds nothing, yet the minimum 0 exists at the origin, the point where the gradient of the constraint vanishes. Change f in A to x + y + z or x**2 + 2*y**2 + 3*z**2 and see how the candidates change. Add the constraint z - x - y for a second constraint on A and read off the two multipliers.

Traps

Watch out· Skipping the singular points

Points where $\nabla g = O$ (or the constraint gradients are dependent) are candidates of their own and the equation $\nabla f = \lambda\nabla g$ cannot find them. The cusp $y^2 = x^3$ (Worksheet 3 #3) is built to catch this: Lagrange returns no solution, and the minimum is at the singular point. Apostol’s example of a plane meeting a cylinder along a line (stretch problem below) is the same trap with two constraints.

Watch out· Dividing by something that can be zero

From $y = 4\lambda^2y$ you may not cancel $y$ without first treating $y = 0$ (Worksheet 1 #5: $y = 0$ forces $x = 0$ , off the circle). In the disc example the equation $4y = 2\lambda y$ splits into $y = 0$ or $\lambda = 2$ . Lost cases are lost extrema.

Watch out· Candidates are not answers

One solution does not mean it is the minimum. Say why an extremum exists (the constraint set is compact, or $f \to \infty$ along every unbounded direction) or classify with the bordered Hessian or convexity. Worksheet 1 #6 has a minimum and no maximum, because the constraint is a line.

Watch out· The Lagrangian's critical point is a saddle, not a minimum

For $xy$ on the circle, at the maximum $\big(\frac{\sqrt2}2, \frac{\sqrt2}2\big)$ with $\lambda = \frac12$ , the Hessian of $L(x, y, \lambda)$ in all three variables is $\begin{bmatrix}-1 & 1 & -\sqrt2\\ 1 & -1 & -\sqrt2\\ -\sqrt2 & -\sqrt2 & 0\end{bmatrix}$ , with eigenvalues $-2, -2, 2$ : indefinite. The 5.6 test applied to $L$ in all variables is meaningless; the right matrix is the Hessian in $x$ restricted to the tangent space (the bordered Hessian).

Watch out· Inequality constraints and the boundary of a region

For a region such as a disc, find the interior critical points with $\nabla f = O$ (5.6) and then treat the boundary with a multiplier; compare all values. Two constraints need independent gradients. For true inequality constraints the multipliers have a sign (KKT), which the equality case does not.

Watch out· Sign and size of lambda

The sign of $\lambda$ depends on writing $f - \lambda g$ or $f + \lambda g$ . Do not read meaning from it before fixing the convention. With $L = f - \lambda(g - c)$ the price theorem says $V'(c) = +\lambda$ .

Problems

check

Write and solve the Lagrange equations for the maximum of $x + 2y$ on $x^2 + y^2 = 5$ .

Solution

$\nabla f = (1, 2) = \lambda(2x, 2y)$ gives $x = \frac1{2\lambda}$ , $y = \frac1\lambda = 2x$ . Then $5x^2 = 5$ , $x = \pm1$ . The points are $(1, 2)$ with $f = 5$ and $(-1, -2)$ with $f = -5$ . The circle is compact, so the maximum is $5$ at $(1, 2)$ (and the minimum is $-5$ ). Check: $x + 2y = (1, 2)\cdot(x, y) \le \sqrt5\cdot\sqrt5 = 5$ by Cauchy–Schwarz.

check

How many unknowns and how many equations are there when you maximise $f(x_1, x_2, x_3, x_4)$ on two constraints $g_1 = c_1$ , $g_2 = c_2$ ?

Solution

Unknowns: four coordinates and two multipliers, six. Equations: four from $\nabla f = \lambda_1\nabla g_1 + \lambda_2\nabla g_2$ and two constraints, six. In general $n + m$ equations in $n + m$ unknowns.

checkApostol 9.15 #1

Find the extreme values of $z = xy$ subject to $x + y = 1$ .

Solution

$\nabla(xy) = (y, x) = \lambda(1, 1)$ gives $x = y$ , and $x + y = 1$ gives $x = y = \frac12$ , $z = \frac14$ . The constraint is a line (not compact): by substitution $z = x(1 - x) = \frac14 - \big(x - \frac12\big)^2$ , a downward parabola. So $\frac14$ is the maximum and there is no minimum ( $z \to -\infty$ ).

check

Show that replacing $L = f - \lambda g$ by $L' = f + \lambda g$ changes the multiplier’s sign but not the candidate points.

Solution

$\nabla L' = O$ means $\nabla f = -\lambda\nabla g$ and $g = c$ . So $(x, \lambda)$ solves the system for $L'$ exactly when $(x, -\lambda)$ solves it for $L$ . The points $x$ are the same; only $\lambda$ changes sign.

useApostol 9.15 #5

Find the extreme values of $f(x, y, z) = x - 2y + 2z$ on the sphere $x^2 + y^2 + z^2 = 1$ .

Solution

$\nabla f = (1, -2, 2) = \lambda(2x, 2y, 2z)$ , so $(x, y, z) = \frac{(1, -2, 2)}{2\lambda}$ . On the sphere, $\frac{1 + 4 + 4}{4\lambda^2} = 1$ , so $\lambda = \pm\frac32$ and $(x, y, z) = \pm\frac{(1, -2, 2)}3$ . Values: $f = \pm\frac{1 + 4 + 4}{3} = \pm3$ . The sphere is compact: maximum $3$ , minimum $-3$ (this is $\lVert(1, -2, 2)\rVert = 3$ , Cauchy–Schwarz).

useApostol 9.15 #13

Find the greatest and least distances from the ellipse $x^2 + 4y^2 = 4$ to the line $x + y = 4$ .

Solution

The distance from $(x, y)$ to the line is $\frac{\lvert x + y - 4\rvert}{\sqrt2}$ . On the ellipse $x + y$ has extremes found by $(1, 1) = \lambda(2x, 8y)$ : $x = \frac1{2\lambda}$ , $y = \frac1{8\lambda}$ , so $x = 4y$ ; then $16y^2 + 4y^2 = 4$ , $y = \pm\frac1{\sqrt5}$ , $x = \pm\frac4{\sqrt5}$ , and $x + y = \pm\sqrt5$ . Since $\lvert x + y\rvert \le \sqrt5 \lt 4$ , the distance is $\frac{4 - (x + y)}{\sqrt2}$ : greatest $\frac{4 + \sqrt5}{\sqrt2} \approx 4.410$ , least $\frac{4 - \sqrt5}{\sqrt2} \approx 1.247$ .

useApostol 9.15 #6

Find the points of the surface $z^2 - xy = 1$ nearest to the origin.

Solution

Minimise $f = x^2 + y^2 + z^2$ on $g = z^2 - xy = 1$ . $\nabla g = (-y, -x, 2z)$ is zero only at the origin, which is not on the surface. Equations: $2x = -\lambda y$ , $2y = -\lambda x$ , $2z = 2\lambda z$ . If $z \ne 0$ : $\lambda = 1$ , then $2x = -y$ and $2y = -x$ give $x = y = 0$ , $z = \pm1$ , $f = 1$ . If $z = 0$ : $-xy = 1$ and $4xy = \lambda^2xy$ so $\lambda = \pm2$ ; $\lambda = 2$ gives $y = -x$ , $x^2 = 1$ , points $\pm(1, -1, 0)$ with $f = 2$ ; $\lambda = -2$ gives $y = x$ and $-x^2 = 1$ , impossible. A minimum exists since $f \to \infty$ on the closed surface. The nearest points are $(0, 0, \pm1)$ , distance $1$ .

usenew (economics, with the price theorem)

Maximise $U = \sqrt{xy}$ subject to $4x + y = 40$ . Find the best bundle and $\lambda$ , and check $\lambda = dV/dm$ for $m = 40$ .

Solution

$\nabla U = \Big(\frac{y}{2\sqrt{xy}},\ \frac{x}{2\sqrt{xy}}\Big) = \lambda(4, 1)$ , so $\frac yx = 4$ (ratio of the two equations: $\frac{y}{x} = \frac41$ ), $y = 4x$ . Budget: $4x + 4x = 40$ , $x = 5$ , $y = 20$ , $U = \sqrt{100} = 10$ . Then $\lambda = \frac{U_y}{p_y} = \frac{x}{2\sqrt{xy}} = \frac5{20} = \frac14$ . For general income $m$ : $x = \frac m8$ , $y = \frac m2$ , $V(m) = \sqrt{\frac{m^2}{16}} = \frac m4$ , so $V'(m) = \frac14 = \lambda$ . ✓.

provenew (Cauchy–Schwarz)

Use Lagrange multipliers to show that $\max\{a\cdot x : \lVert x\rVert = 1\} = \lVert a\rVert$ for $a \ne O$ , and deduce $\lvert a\cdot x\rvert \le \lVert a\rVert\lVert x\rVert$ .

Solution

Plan. Find the candidates, use compactness for existence, then scale.

$\nabla(a\cdot x) = a = \lambda\nabla(\lVert x\rVert^2) = 2\lambda x$ , so $x = \frac{a}{2\lambda}$ and $\lVert x\rVert = 1$ gives $2\lvert\lambda\rvert = \lVert a\rVert$ : the candidates are $x = \pm\frac{a}{\lVert a\rVert}$ , with values $\pm\lVert a\rVert$ . The unit sphere is compact, so the maximum exists; it is $\lVert a\rVert$ . For a general nonzero $x$ apply this to $x/\lVert x\rVert$ : $a\cdot\frac x{\lVert x\rVert} \le \lVert a\rVert$ , and replacing $x$ by $-x$ gives the absolute value. $\blacksquare$

provenew (Rayleigh quotient)

Let $A$ be a real symmetric matrix. Prove that $\max\{x^{\mathsf T}Ax : \lVert x\rVert = 1\}$ equals the largest eigenvalue of $A$ .

Solution

Plan. Lagrange turns the maximisation into an eigenvalue equation.

The sphere is compact and $x^{\mathsf T}Ax$ is continuous, so the maximum is attained at some $x_0$ . Every point of the sphere is regular for $g = \lVert x\rVert^2$ ( $\nabla g = 2x \ne O$ ). By the theorem, $\nabla(x^{\mathsf T}Ax) = 2Ax_0 = \lambda\cdot2x_0$ (using $\nabla(x^{\mathsf T}Ax) = 2Ax$ , 3.8, for symmetric $A$ ), so $Ax_0 = \lambda x_0$ : $x_0$ is an eigenvector. Then $x_0^{\mathsf T}Ax_0 = \lambda\lVert x_0\rVert^2 = \lambda$ , so the maximum value is an eigenvalue. Conversely for any eigenvalue $\mu$ with unit eigenvector $u$ , $u^{\mathsf T}Au = \mu$ is attained on the sphere, so the maximum is at least every eigenvalue. Hence the maximum is the largest eigenvalue. $\blacksquare$

provenew (AM–GM)

Prove that $(abc)^{1/3} \le \frac{a + b + c}3$ for $a, b, c \ge 0$ by maximising $xyz$ on $x + y + z = s$ , $x, y, z \ge 0$ .

Solution

Plan. Existence by compactness, boundary excluded because the product vanishes there, interior by Lagrange.

Fix $s \gt 0$ . The triangle $T = \{x + y + z = s,\ x, y, z \ge 0\}$ is closed and bounded, so $xyz$ attains a maximum on $T$ . On the boundary of $T$ some coordinate is $0$ and $xyz = 0$ , while the interior has $xyz \gt 0$ , so the maximum is at an interior point. There $\nabla(xyz) = (yz, xz, xy) = \lambda(1, 1, 1)$ . Multiplying the first equation by $x$ and the second by $y$ gives $xyz = \lambda x = \lambda y$ , and $\lambda = xyz/x \ne 0$ , so $x = y$ ; likewise $y = z$ . So $x = y = z = \frac s3$ and the maximum is $\big(\frac s3\big)^3$ . Taking $s = a + b + c$ (the case $s = 0$ is trivial), $abc \le \big(\frac{a + b + c}{3}\big)^3$ . $\blacksquare$

provenew (n = 2, m = 1, directly)

Prove the multiplier theorem for $f, g$ of two variables, $\nabla g(a) \ne O$ , without using the general implicit function proof: use a curve in the level set.

Solution

Plan. A regular level curve has a tangent vector; $f$ along it is stationary; the perpendicular line in the plane is one-dimensional.

By the corollary of 5.7, near $a$ the level curve $g = c$ is the image of a $C^1$ curve $r(t)$ with $r(0) = a$ and $r'(0) \ne O$ spanning $\ker Dg(a)$ , so $r'(0) \perp \nabla g(a)$ . The function $t \mapsto f(r(t))$ has a local extremum at the interior point $t = 0$ , so its derivative is $0$ : by the path theorem (5.3) $\nabla f(a)\cdot r'(0) = 0$ . In the plane the vectors perpendicular to the nonzero vector $r'(0)$ form a line, and it contains both $\nabla f(a)$ and $\nabla g(a) \ne O$ . So $\nabla f(a) = \lambda\nabla g(a)$ . $\blacksquare$

stretchApostol 9.14 (the example where the method fails)

Minimise $f(x, y, z) = x^2 + y^2$ on the set $z = 0$ , $z^2 = (y - 1)^3$ . Show that the method of Lagrange multipliers applied to $g_1 = z$ , $g_2 = z^2 - (y - 1)^3$ finds no candidate, and explain.

Solution

The constraint set: $z = 0$ forces $(y - 1)^3 = 0$ , so $y = 1$ : it is the line $\{(x, 1, 0)\}$ . On it $f = x^2 + 1$ , minimal at $(0, 1, 0)$ with value $1$ . There $\nabla g_1 = (0, 0, 1)$ and $\nabla g_2 = (0, -3(y - 1)^2, 2z) = O$ : the gradients are linearly dependent, so $(0, 1, 0)$ is not a regular point. And $\nabla f = (0, 2, 0)$ is not in the span of $\nabla g_1, \nabla g_2$ , which is the $z$ -axis direction. So no multipliers exist. The theorem requires independent gradients; here the two surfaces (a plane and a cylinder) are tangent along the line, which is why the dependence appears.

stretchnew (finance; links 2.10 and 5.8)

Derive the minimum-variance portfolio $w = \dfrac{\Sigma^{-1}\mathbf 1}{\mathbf 1^{\mathsf T}\Sigma^{-1}\mathbf 1}$ for a positive definite covariance matrix $\Sigma$ , and compute it for two uncorrelated assets with variances $0.04$ and $0.09$ .

Solution

Minimise $w^{\mathsf T}\Sigma w$ subject to $\mathbf 1^{\mathsf T}w = 1$ . $\nabla = 2\Sigma w = \lambda\mathbf 1$ , so $w = \frac\lambda2\Sigma^{-1}\mathbf 1$ ( $\Sigma$ is invertible, being positive definite). The constraint gives $\frac\lambda2\mathbf 1^{\mathsf T}\Sigma^{-1}\mathbf 1 = 1$ , hence the formula. The objective is convex ( $\Sigma$ positive definite, hence the convexity theorem above) and the constraint linear, so by the corollary this is the global minimum. For $\Sigma = \operatorname{diag}(0.04, 0.09)$ , $\Sigma^{-1}\mathbf 1 = (25, 11.11)$ and $\mathbf 1^{\mathsf T}\Sigma^{-1}\mathbf 1 = 36.11$ , so $w = (0.6923, 0.3077) = \big(\frac9{13}, \frac4{13}\big)$ , with variance $\frac{0.04\cdot0.09}{0.13} = 0.02769$ (standard deviation $16.6\%$ , less than the $20\%$ of the safer asset alone: diversification).

Summary

A constrained extremum of $f$ on $\{g = c\}$ is not a point with $\nabla f = O$ . The Lagrange multiplier theorem: if $a$ is a regular point of the constraint (the gradients $\nabla g_i(a)$ are independent) and $f|_S$ has a local extremum at $a$ , then $\nabla f(a) = \sum\lambda_i\nabla g_i(a)$ . Picture: the level curve of $f$ touches the constraint, so their normals are parallel.
Proof: by the implicit function theorem the constraint is a graph over $n - m$ free variables, $f$ restricted to it has an interior extremum, so its gradient is zero, and defining $\lambda$ from the solved coordinates makes the equation hold in the free coordinates too.
Recipe: (1) find the singular points of the constraint; (2) solve $\nabla f = \sum\lambda_i\nabla g_i$ and $g = c$ ( $n + m$ equations); (3) list candidates; (4) compare values and justify existence (compactness, growth) or classify. Use squared distances, and never divide by a quantity that may be $0$ .
The theorem gives candidates only. Classification: compact feasible set, growth, convexity (a convex Lagrangian makes any Lagrange point a global minimum), or the second-order test: $v^{\mathsf T}Hv$ on the tangent space with $H = D^2f - \sum\lambda_iD^2g_i$ ; for two variables and one constraint $\det B \gt 0$ means a maximum and $\det B \lt 0$ a minimum.
The multiplier is the price of the constraint: $V'(c) = \lambda$ , where $V(c)$ is the best value.
Eigenvalues are Lagrange multipliers: the extremes of $x^{\mathsf T}Ax$ on the unit sphere are the extreme eigenvalues; $\sigma_1$ is $\max\lVert Ax\rVert$ .
Real problems: maximum entropy gives the Boltzmann distribution and the softmax; the Markowitz portfolio solves a linear (bordered) system; SVM margins come from a dual problem; utility maximisation gives the budget tangency and shadow prices.
Failure modes: singular points (the cusp $y^2 = x^3$ ), dependent gradients (plane and cylinder), lost cases from dividing by a variable, and treating the Lagrangian’s critical point as if it were a minimum of $L$ .

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

5.8 Constrained extrema and Lagrange multipliers

The picture: when two curves touch

The idea, in words

Definitions and the theorem

Constrained extremum

Lagrange multiplier

Lagrangian

Lagrange multiplier theorem

The recipe

Examples from the course

Which candidate is which? The second-order test

Bordered Hessian

Second-order test for constrained extrema

Bordered determinant test in two variables

What the multiplier means

The multiplier is the price of the constraint

Convexity: when a candidate is automatically the best

Convex function

Gradient inequality for convex functions

Positive semidefinite Hessian implies convex

A convex Lagrangian gives a global minimum

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere