Skip to main content

MATH 345: Linear Algebra and Optimization

Sebastien Roch with Jacob Denson and Kaitlyn Phillipson

Section 6.2 Lagrange multipliers

Recall from Definition 3.6.12 that an optimization problem has an objective function and a feasible region. A constrained optimization problem restricts the feasible region. We begin with one equality constraint.
🔗

Definition 6.2.1. Constrained optimization with one equality constraint.

Let \(f:\R^n\to\R\) be an objective function, let \(g:\R^n\to\R\text{,}\) and let \(k\in\R\text{.}\) To maximize or minimize \(f(\mathbf{x})\) subject to
\begin{equation*} g(\mathbf{x})=k \end{equation*}
means to optimize \(f\) on the feasible region
\begin{equation*} S=\{\mathbf{x}\in\R^n:g(\mathbf{x})=k\}. \end{equation*}
The equation \(g(\mathbf{x})=k\) is the constraint. A point of \(S\) is feasible.
🔗
🔗
Suppose \(\mathbf{a}\in S\) is a local extremum of \(f\) on \(S\text{.}\) At \(\mathbf{a}\text{,}\) allowed motion follows tangent directions to \(S\text{.}\) The first-order change of \(f\) must vanish along those directions, so \(\nabla f(\mathbf{a})\) is normal to \(S\text{.}\) The vector \(\nabla g(\mathbf{a})\) is also normal to the level set \(g(\mathbf{x})=k\text{.}\) If
\begin{equation*} \nabla g(\mathbf{a})\neq\mathbf{0}, \end{equation*}
this suggests that the two gradients are parallel.
🔗

Definition 6.2.2. Constrained critical point.

Let \(f,g:\R^n\to\R\) be differentiable, and let
\begin{equation*} S=\{\mathbf{x}\in\R^n:g(\mathbf{x})=k\}. \end{equation*}
Assume
\begin{equation*} \nabla g(\mathbf{x})\neq\mathbf{0} \end{equation*}
for every \(\mathbf{x}\in S\text{.}\) A point \(\mathbf{a}\in S\) in the interior of the domain of \(f\) is a constrained critical point of \(f\) on \(S\) if there exists \(\lambda\in\R\) such that
\begin{equation*} \nabla f(\mathbf{a})=\lambda\nabla g(\mathbf{a}). \end{equation*}
The scalar \(\lambda\) is a Lagrange multiplier.
🔗
🔗

Lagrangian formulation.

The same equations can be packaged in one function. Define the Lagrangian
\begin{equation*} L(\mathbf{x},\lambda) = f(\mathbf{x})-\lambda\bigl(g(\mathbf{x})-k\bigr). \end{equation*}
Then
\begin{equation*} \nabla_{\mathbf{x}}L(\mathbf{x},\lambda) = \nabla f(\mathbf{x})-\lambda\nabla g(\mathbf{x}), \end{equation*}
and
\begin{equation*} \frac{\partial L}{\partial\lambda}(\mathbf{x},\lambda) = -\bigl(g(\mathbf{x})-k\bigr). \end{equation*}
Therefore the equations
\begin{equation*} \nabla_{\mathbf{x}}L(\mathbf{x},\lambda)=\mathbf{0}, \qquad \frac{\partial L}{\partial\lambda}(\mathbf{x},\lambda)=0 \end{equation*}
are exactly the equations
\begin{equation*} \nabla f(\mathbf{x})=\lambda\nabla g(\mathbf{x}), \qquad g(\mathbf{x})=k. \end{equation*}
The Lagrangian does not replace the constraint. It packages the parallel-gradient equation and the constraint equation into one critical-point system.
🔗
🔗
The method of Lagrange multipliers solves this system to find constrained critical points. The next theorem explains why constrained extrema occur among these candidates.
🔗

Why is this true?.

Suppose \(\mathbf{a}\) is a local extremum of \(f\) on \(S\text{.}\) The directional derivative
\begin{equation*} D_{\mathbf{v}}f(\mathbf{a}) \end{equation*}
must be \(0\) for every unit vector \(\mathbf{v}\) tangent to \(S\) at \(\mathbf{a}\text{.}\) Otherwise, moving along \(S\) in the direction \(\mathbf{v}\) or \(-\mathbf{v}\) would increase or decrease \(f\text{.}\)
🔗
By Theorem 3.6.3,
\begin{equation*} D_{\mathbf{v}}f(\mathbf{a}) = \nabla f(\mathbf{a})\cdot\mathbf{v}. \end{equation*}
Thus \(\nabla f(\mathbf{a})\) is perpendicular to every tangent direction to \(S\text{.}\) Since \(S\) is the level set
\begin{equation*} g(\mathbf{x})=k, \end{equation*}
the vector \(\nabla g(\mathbf{a})\) is also perpendicular to every tangent direction. Therefore the two gradients are parallel:
\begin{equation*} \nabla f(\mathbf{a}) = \lambda\nabla g(\mathbf{a}) \end{equation*}
for some \(\lambda\in\R\text{.}\)
🔗
The final statement follows from Theorem 6.1.2. If \(S\) is closed and bounded and \(f\) is continuous, absolute extrema exist. Any absolute extremum is also a local extremum on \(S\text{,}\) so it must be a constrained critical point.
🔗
🔗
Contour and constraint diagram showing normal vectors at a constrained critical point.
The figure shows a contour plot with red objective contours and a blue constraint curve. A black point on the blue curve is enlarged in a zoomed panel. In the zoomed panel, arrows indicate normal directions to the objective contour and to the constraint curve at the point, illustrating that the normals are parallel at a constrained critical point.
🔗
Figure 6.2.4. Suppose we optimize a function whose contours are the red curves, subject to the constraint shown by the blue curve. Constrained critical points occur where an objective contour is tangent to the constraint curve, so their normal vectors are parallel. From: Stanford’s MATH 51 textbook
🔗

Activity 6.2.6. A linear objective on a circle (U6-LO2).

Find the absolute extrema of \(f(x,y) = 3x + y\) subject to the constraint \(x^2 + y^2 = 10\text{.}\)
🔗
Solution.
Write \(g(x,y) = x^2 + y^2\text{.}\) Then we are finding extrema of \(f\) on the surface
\begin{equation*} S = \{ (x,y): g(x,y) = 10 \}\text{.} \end{equation*}
We calculate that
\begin{equation*} \nabla f(x,y) = (3,1) \quad\text{and}\quad \nabla g(x,y) = (2x,2y)\text{.} \end{equation*}
So the constrained critical points of \(f\) on \(S\) are the points \((x,y) \in S\) for which there exists \(\lambda\) such that
\begin{equation*} (3,1) = \lambda (2x,2y)\text{,} \end{equation*}
i.e., the points that satisfy the three equations
\begin{align*} x^2 + y^2 \amp = 10\\ 2 \lambda x = 3\\ 2 \lambda y = 1\text{.} \end{align*}
If the second and third equations hold, then \(\lambda\) cannot be zero, and we can divide both sides of the equations by \(\lambda\) to obtain that \(x = \frac{3}{2\lambda}\) and \(y = \frac{1}{2\lambda}\text{.}\) Substituting this into the first equation, we find that
\begin{equation*} \left(\frac{3}{2\lambda}\right)^2 + \left(\frac{1}{2\lambda}\right)^2 = 10\text{,} \end{equation*}
which simplifies to \(1/4 = \lambda^2\text{,}\) so either \(\lambda = 1/2\) or \(\lambda = -1/2\text{.}\) If \(\lambda = 1/2\text{,}\) then \(x = 3\) and \(y = 1\text{,}\) and if \(\lambda = -1/2\text{,}\) then \(x = -3\) and \(y = -1\text{.}\) So the two points \((3,1)\) and \((-3,-1)\) are the two constrained critical points of \(f\) on \(S\text{.}\) Since \(S\) is a circle and is closed and bounded, the absolute maximum and minimum occur among these two points. We have
\begin{equation*} f(3,1) = 10 \quad\text{and}\quad f(-3,-1) = -10\text{,} \end{equation*}
so \((3,1)\) is the absolute maximum of \(f\) on \(S\text{,}\) and \((-3,-1)\) is the absolute minimum of \(f\) on \(S\text{.}\)
🔗
🔗
🔗

Activity 6.2.7. A quadratic objective on a sphere (U6-LO2).

Find the absolute extrema of the function \(f(x,y,z) = x^2 + 2y^2 + 3z^2\text{,}\) subject to the constraint \(x^2 + y^2 + z^2 = 1\text{.}\)
🔗
Solution.
Let \(g(x,y,z) = x^2 + y^2 + z^2\text{.}\) Then \(\nabla f(x,y,z) = (2x,4y,6z)\) and \(\nabla g(x,y,z) = (2x,2y,2z)\text{.}\) A point \((x,y,z)\) is a constrained critical point of \(f\) on the sphere \(S = \{ (x,y,z): x^2 + y^2 + z^2 = 1 \}\) only when there exists \(\lambda \in \R\) so that the two equations
\begin{equation*} \nabla f(x,y,z) = \lambda \nabla g(x,y,z) \quad\text{and}\quad x^2 + y^2 + z^2 = 1 \end{equation*}
both hold, which expands to the four equations
\begin{gather*} 2x = 2\lambda x\\ 4y = 2\lambda y\\ 6z = 2\lambda z\\ x^2 + y^2 + z^2 = 1\text{.} \end{gather*}
Since \(x^2 + y^2 + z^2 = 1\text{,}\) either \(x \neq 0\) (and dividing the first equation by \(x\) we obtain \(\lambda = 1\)), \(y \neq 0\) (and dividing the second equation we obtain \(\lambda = 2\)), or \(z \neq 0\) (and dividing the third equation by \(z\) gives \(\lambda = 3\)). When \(\lambda = 1\text{,}\) the first equation automatically holds, and the second and third equations can only hold when \(y = z = 0\text{.}\) Thus the fourth equation becomes \(x^2 = 1\text{,}\) so \(x = \pm 1\text{.}\) Similarly, when \(\lambda = 2\) we have \(x = z = 0\) and \(y = \pm 1\text{,}\) and when \(\lambda = 3\) we have \(x = y = 0 \) and \(z = \pm 1\text{.}\) So the function \(f\) has six constrained critical points on \(S\text{,}\) at the points \((\pm 1,0 ,0)\text{,}\) \((0,\pm 1, 0)\text{,}\) and \((0,0,\pm 1)\text{.}\) We have
\begin{equation*} f(\pm 1,0,0) = 1 \qquad f(0,\pm 1, 0) = 2 \qquad f(0,0,\pm 1) = 3\text{.} \end{equation*}
So the absolute minima of \(f\) occur at \((\pm 1, 0, 0)\text{,}\) and the absolute maxima of \(f\) occur at \((0,0,\pm 1)\text{.}\)
🔗
🔗
🔗

Activity 6.2.8. Absolute extrema on a disk (U6-LO1, U6-LO2).

Let
\begin{equation*} f(x,y)=x^2+y^2+4x-6y \end{equation*}
on the closed disk
\begin{equation*} D=\{(x,y):x^2+y^2\leq 16\}. \end{equation*}
Find the absolute extrema of \(f\) on \(D\text{,}\) using Lagrange multipliers to analyze the circular boundary.
🔗

(a)

Find the critical points of \(f\) in the interior of \(D\) and evaluate \(f\) at each one.
🔗
Solution.
The interior critical points satisfy
\begin{equation*} \nabla f(x,y)=(2x+4,2y-6)=(0,0). \end{equation*}
Thus \((x,y)=(-2,3)\text{.}\) Since \((-2)^2+3^2=13\lt 16\text{,}\) this point lies in the interior of \(D\text{.}\) Its function value is
\begin{equation*} f(-2,3)=4+9-8-18=-13. \end{equation*}
🔗
🔗
🔗

(b)

Use Lagrange multipliers to find and evaluate all candidates on the boundary \(x^2+y^2=16\text{.}\)
🔗
Solution.
Let \(g(x,y)=x^2+y^2\text{.}\) On the boundary, the Lagrange multiplier equations are
\begin{equation*} \nabla f(x,y)=\lambda\nabla g(x,y), \qquad x^2+y^2=16. \end{equation*}
Since \(\nabla g(x,y)=(2x,2y)\text{,}\) the gradient equation becomes
\begin{align*} 2x+4 \amp=2\lambda x,\\ 2y-6 \amp=2\lambda y. \end{align*}
Equivalently,
\begin{equation*} (1-\lambda)x=-2, \qquad (1-\lambda)y=3. \end{equation*}
The value \(\lambda=1\) cannot satisfy these equations. Set \(\mu=1-\lambda\text{.}\) Then
\begin{equation*} x=-\frac{2}{\mu}, \qquad y=\frac{3}{\mu}. \end{equation*}
Substitution into the constraint gives
\begin{equation*} \frac{13}{\mu^2}=16, \end{equation*}
so \(\mu=\pm\sqrt{13}/4\text{.}\) Therefore the boundary candidates are
\begin{equation*} \left(-\frac{8}{\sqrt{13}},\frac{12}{\sqrt{13}}\right) \quad\text{and}\quad \left(\frac{8}{\sqrt{13}},-\frac{12}{\sqrt{13}}\right). \end{equation*}
On the boundary, \(x^2+y^2=16\text{,}\) so \(f(x,y)=16+4x-6y\text{.}\) Hence the corresponding values are
\begin{align*} f\left(-\frac{8}{\sqrt{13}},\frac{12}{\sqrt{13}}\right) \amp=16-8\sqrt{13},\\ f\left(\frac{8}{\sqrt{13}},-\frac{12}{\sqrt{13}}\right) \amp=16+8\sqrt{13}. \end{align*}
🔗
🔗
🔗

(c)

Compare the interior and boundary candidates to identify the absolute maximum and absolute minimum of \(f\) on \(D\text{.}\)
🔗
Solution.
The disk \(D\) is closed and bounded, and \(f\) is continuous, so the extreme value theorem guarantees that absolute extrema exist. The candidate values are
\begin{equation*} -13, \qquad 16-8\sqrt{13}, \qquad 16+8\sqrt{13}. \end{equation*}
Since \(16-8\sqrt{13}\approx -12.84\text{,}\) the absolute minimum is \(-13\) at \((-2,3)\text{.}\) The absolute maximum is \(16+8\sqrt{13}\) at
\begin{equation*} \left(\frac{8}{\sqrt{13}},-\frac{12}{\sqrt{13}}\right). \end{equation*}
🔗
🔗
🔗
🔗

Several equality constraints.

Some feasible sets are intersections of several level sets. Let
\begin{equation*} f,g_1,\ldots,g_m:\R^n\to\R \end{equation*}
be differentiable scalar-valued functions. To optimize \(f(\mathbf{x})\) subject to
\begin{equation*} g_1(\mathbf{x})=k_1,\quad\ldots,\quad g_m(\mathbf{x})=k_m \end{equation*}
means to optimize \(f\) on the feasible set
\begin{equation*} S= \left\{ \mathbf{x}\in\R^n: g_1(\mathbf{x})=k_1,\ldots,g_m(\mathbf{x})=k_m \right\}. \end{equation*}
🔗
🔗

Definition 6.2.9. Constrained critical point with several constraints.

This extends Definition 6.2.2. Let
\begin{equation*} S= \left\{ \mathbf{x}\in\R^n: g_1(\mathbf{x})=k_1,\ldots,g_m(\mathbf{x})=k_m \right\}. \end{equation*}
A feasible point \(\mathbf{a}\in S\) in the interior of the domain of \(f\) is a constrained critical point of \(f\) on \(S\) if there are scalars
\begin{equation*} \lambda_1,\ldots,\lambda_m \end{equation*}
such that
\begin{equation*} \nabla f(\mathbf{a}) = \lambda_1\nabla g_1(\mathbf{a}) +\cdots+ \lambda_m\nabla g_m(\mathbf{a}). \end{equation*}
The scalars \(\lambda_1,\ldots,\lambda_m\) are Lagrange multipliers.
🔗
🔗
By Definition 2.3.22, the condition says that
\begin{equation*} \nabla f(\mathbf{a}) \in \spans \left\{ \nabla g_1(\mathbf{a}),\ldots,\nabla g_m(\mathbf{a}) \right\}. \end{equation*}
With one constraint, this span is a line, so the condition reduces to parallel gradients.
🔗

Lagrangian formulation.

Define
\begin{equation*} L(\mathbf{x},\lambda_1,\ldots,\lambda_m) = f(\mathbf{x}) - \sum_{j=1}^m \lambda_j\bigl(g_j(\mathbf{x})-k_j\bigr). \end{equation*}
Then
\begin{equation*} \nabla_{\mathbf{x}}L = \nabla f - \sum_{j=1}^m\lambda_j\nabla g_j, \end{equation*}
while
\begin{equation*} \frac{\partial L}{\partial\lambda_j} = -\bigl(g_j(\mathbf{x})-k_j\bigr) \end{equation*}
for \(j=1,\ldots,m\text{.}\) Therefore the critical-point equations for \(L\) are exactly
\begin{equation*} \nabla f = \lambda_1\nabla g_1+\cdots+\lambda_m\nabla g_m \end{equation*}
together with
\begin{equation*} g_1(\mathbf{x})=k_1,\quad\ldots,\quad g_m(\mathbf{x})=k_m. \end{equation*}
As in the one-constraint case, the Lagrangian packages the gradient equation and all constraint equations into one system.
🔗
🔗

Why is this true?.

A unit vector tangent to \(S\) at \(\mathbf{a}\) must be tangent to every constraint level set. It is therefore perpendicular to each of
\begin{equation*} \nabla g_1(\mathbf{a}),\ldots,\nabla g_m(\mathbf{a}). \end{equation*}
🔗
At a constrained local extremum, the directional derivative of \(f\) must vanish in every allowed tangent direction. By Theorem 3.6.3,
\begin{equation*} D_{\mathbf{v}}f(\mathbf{a}) = \nabla f(\mathbf{a})\cdot\mathbf{v}, \end{equation*}
so \(\nabla f(\mathbf{a})\) is also normal to the feasible set.
🔗
When the constraint gradients are linearly independent, they span the normal directions to the intersection. Therefore \(\nabla f(\mathbf{a})\) is a linear combination of the constraint gradients.
🔗
🔗

Activity 6.2.12. A sphere and a plane (U6-LO3, U2-LO4, U4-LO1).

Find the absolute maximum and minimum values of
\begin{equation*} f(x,y,z)=x \end{equation*}
subject to
\begin{equation*} x^2+y^2+z^2=1 \end{equation*}
and
\begin{equation*} x+y+z=0. \end{equation*}
🔗
  1. Describe the feasible set geometrically. Why do absolute extrema exist?
    🔗
    🔗
  2. Show that the two constraint gradients are linearly independent at every feasible point.
    🔗
    🔗
  3. Form the Lagrangian using multipliers \(\lambda\) and \(\mu\text{.}\)
    🔗
    🔗
  4. Solve the Lagrange equations.
    🔗
    🔗
  5. Evaluate \(f\) at the candidates and identify the absolute extrema.
    🔗
    🔗
Solution.
The feasible set is the intersection of the unit sphere and the plane
\begin{equation*} x+y+z=0. \end{equation*}
It is a circle. In particular, it is closed and bounded, so absolute extrema exist by Theorem 6.1.2.
🔗
Let
\begin{equation*} g_1(x,y,z)=x^2+y^2+z^2, \qquad g_2(x,y,z)=x+y+z. \end{equation*}
Then
\begin{equation*} \nabla g_1= 2 \begin{bmatrix} x\\ y\\ z \end{bmatrix}, \qquad \nabla g_2= \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}. \end{equation*}
At a feasible point,
\begin{equation*} \nabla g_1\cdot\nabla g_2 = 2(x+y+z) = 0. \end{equation*}
Both gradients are nonzero on the feasible set. They are therefore an orthogonal set and hence linearly independent by Theorem 4.1.12.
🔗
Define
\begin{equation*} L(x,y,z,\lambda,\mu) = x - \lambda(x^2+y^2+z^2-1) - \mu(x+y+z). \end{equation*}
The critical-point equations are
\begin{equation*} 1=2\lambda x+\mu, \end{equation*}
\begin{equation*} 0=2\lambda y+\mu, \end{equation*}
\begin{equation*} 0=2\lambda z+\mu, \end{equation*}
together with
\begin{equation*} x^2+y^2+z^2=1, \qquad x+y+z=0. \end{equation*}
🔗
We cannot have \(\lambda=0\text{,}\) since the second and third equations would give \(\mu=0\text{,}\) contradicting the first equation. Thus \(\lambda\neq 0\text{.}\) Subtracting the second and third equations gives
\begin{equation*} y=z. \end{equation*}
Write \(y=z=t\text{.}\) The plane constraint gives
\begin{equation*} x=-2t. \end{equation*}
The sphere constraint becomes
\begin{equation*} 4t^2+t^2+t^2=1, \end{equation*}
so
\begin{equation*} t=\pm\frac1{\sqrt6}. \end{equation*}
The candidates are
\begin{equation*} \frac1{\sqrt6} \begin{bmatrix} 2\\ -1\\ -1 \end{bmatrix} \qquad\text{and}\qquad \frac1{\sqrt6} \begin{bmatrix} -2\\ 1\\ 1 \end{bmatrix}. \end{equation*}
Their \(f\)-values are
\begin{equation*} \frac2{\sqrt6} \qquad\text{and}\qquad -\frac2{\sqrt6}. \end{equation*}
🔗
Therefore the absolute maximum is
\begin{equation*} \frac2{\sqrt6} \end{equation*}
at
\begin{equation*} \frac1{\sqrt6} \begin{bmatrix} 2\\ -1\\ -1 \end{bmatrix}, \end{equation*}
and the absolute minimum is
\begin{equation*} -\frac2{\sqrt6} \end{equation*}
at
\begin{equation*} \frac1{\sqrt6} \begin{bmatrix} -2\\ 1\\ 1 \end{bmatrix}. \end{equation*}
🔗
🔗
🔗
🔗
PrevTopNext