Lagrange multipliers

Worked solutions

Problem 1

1. Near $x^*$ the curve is traced by a path $r(t)$ with $r(0) = x^*$ and a nonzero velocity $r'(0)$, which is tangent to the curve.$\nabla g(x^*) \neq 0$ guarantees this: the implicit function theorem then solves $g = c$ for one coordinate in terms of the other near $x^*$, so the curve is a smooth graph there.
2. $g(r(t)) = c$ for every small $t$, so $\nabla g(x^*)^\top r'(0) = 0$.The path stays on the curve, so $g$ is constant along it; differentiate with the chain rule, $\tfrac{d}{dt}g(r(t)) = \nabla g(r(t))^\top r'(t)$, at $t = 0$.
3. $t \mapsto f(r(t))$ has a local maximum or minimum at $t = 0$, so $\nabla f(x^*)^\top r'(0) = 0$.A differentiable function of one variable has derivative $0$ at an interior local extremum; the same chain rule gives the derivative.
4. In the plane, the vectors orthogonal to the nonzero vector $r'(0)$ form a line through the origin, and $\nabla g(x^*) \neq 0$ spans it.A line through the origin is spanned by any nonzero vector on it, and step 2 puts $\nabla g(x^*)$ on it.
5. $\nabla f(x^*) = \lambda\nabla g(x^*)$ for some number $\lambda$: both gradients are orthogonal to the tangent $r'(0)$, and in the plane those vectors form a single lineStep 3 puts $\nabla f(x^*)$ on the same line as $\nabla g(x^*)$, so it is a multiple of it. Geometrically, the level curve of $f$ through $x^*$ touches the constraint curve there: if $\nabla f$ had a component along the tangent, moving along the curve in that direction would increase $f$. In $\mathbb{R}^n$ the same argument runs over every tangent direction of the surface $g = c$.

Problem 2

1. $\nabla f = (y, x)^\top$ and $\nabla g = (1, 2)^\top$ for $g(x, y) = x + 2y$.$\partial(xy)/\partial x = y$ and $\partial(xy)/\partial y = x$; $g$ is linear, so its partial derivatives are its coefficients.
2. $y = \lambda$ and $x = 2\lambda$.$\nabla f = \lambda\nabla g$, one equation per component.
3. $2\lambda + 2\cdot\lambda = 8$, so $\lambda = 2$ and $(x, y) = (4, 2)$, with $f = 8$.Substitute step 2 into the constraint $x + 2y = 8$: the third equation, which fixes $\lambda$.
4. Along the line $x = 8 - 2y$, so $f = (8 - 2y)y = 8 - 2(y - 2)^2$.Parametrise the constraint by $y$, then complete the square: $8y - 2y^2 = 8 - 2(y^2 - 4y + 4)$.
5. maximum $f = 8$ at $(4, 2)$, with $\lambda = 2$; there is no minimumStep 4 is a downward parabola in $y$: it peaks at $y = 2$ with value $8$ and goes to $-\infty$ as $\lvert y\rvert$ grows. The line is unbounded, so the single candidate needed this separate argument. At $(4, 2)$, $\nabla f = (2, 4)^\top = 2\,(1, 2)^\top$.

Problem 3

1. $\nabla f = (2x, 1)^\top$ and $\nabla g = (2x, 2y)^\top$ for $g(x, y) = x^2 + y^2$.Partial derivatives term by term.
2. $2x = 2\lambda x$, $1 = 2\lambda y$ and $x^2 + y^2 = 1$.$\nabla f = \lambda\nabla g$ by components, and the constraint.
3. $2x(1 - \lambda) = 0$, so $x = 0$ or $\lambda = 1$.Move everything to one side and factor rather than divide by $x$, which may be $0$. A product is $0$ when either factor is, so both cases must be followed.
4. Case $x = 0$: $y^2 = 1$, so $y = 1$ or $y = -1$, with $\lambda = \tfrac12$ or $-\tfrac12$.The constraint, then $\lambda = 1/(2y)$ from the second equation. $y^2 = 1$ has two roots and both are candidates.
5. Case $\lambda = 1$: $1 = 2y$ gives $y = \tfrac12$, and then $x^2 = \tfrac34$, so $x = \pm\tfrac{\sqrt3}2$.The second equation, then the constraint.
6. $f(0, 1) = 1$, $f(0, -1) = -1$ and $f(\pm\tfrac{\sqrt3}2, \tfrac12) = \tfrac34 + \tfrac12 = \tfrac54$.Evaluate $f$ at all four candidates.
7. maximum $\tfrac54$ at $(\pm\tfrac{\sqrt3}2, \tfrac12)$; minimum $-1$ at $(0, -1)$; the candidate $(0, 1)$, with $f = 1$, is neitherThe circle is closed and bounded, so the maximum and minimum exist and are among the four candidates; comparing values picks them. Near $(0, 1)$ the circle is $y \approx 1 - \tfrac{x^2}2$, so $f \approx 1 + \tfrac{x^2}2$: that candidate is only a local minimum along the circle.

Problem 4

1. $\nabla S = (y + 2z,\ x + 2z,\ 2x + 2y)^\top$ and $\nabla g = (yz,\ xz,\ xy)^\top$ for $g = xyz$.Partial derivatives, holding the other two variables fixed.
2. $y + 2z = \lambda yz$, $x + 2z = \lambda xz$ and $2x + 2y = \lambda xy$.$\nabla S = \lambda\nabla g$ by components.
3. $xy + 2xz = \lambda xyz$, $xy + 2yz = \lambda xyz$ and $2xz + 2yz = \lambda xyz$.Multiply the three equations by $x$, $y$ and $z$: every right side becomes $\lambda xyz$, and nothing has been divided.
4. $2xz = 2yz$, so $x = y$.Subtract the second equation from the first. $xyz = 32$ makes every dimension nonzero, so dividing by $2z$ is safe.
5. $xy = 2yz$, so $x = 2z$.Subtract the third equation from the first, then divide by $y \neq 0$.
6. $xyz = 2z\cdot2z\cdot z = 4z^3 = 32$, so $z = 2$ and $x = y = 4$.Substitute steps 4 and 5 into the constraint.
7. $\lambda = \dfrac{y + 2z}{yz} = \dfrac{8}{8} = 1$.The first equation of step 2; Problem 9 uses this value.
8. $x = y = 4$, $z = 2$; least area $48$$S = 16 + 16 + 16$. It is the minimum: with $z = 32/(xy)$ the area is $xy + 64/y + 64/x$, which grows without bound as $x$ or $y$ goes to $0$ or to $\infty$, so a minimum exists inside and must be a candidate, and this is the only one. The base is square and the height is half its side.

Problem 5

Write the plane as $a^\top x = 14$ with $a = (1, 2, 2)^\top$.

1. Minimise $\|x - p\|^2$ subject to $a^\top x = 14$.Squaring is increasing on nonnegative numbers, so the square has the same minimiser as the distance and no square root to differentiate.
2. $\nabla\|x - p\|^2 = 2(x - p)$ and $\nabla(a^\top x) = a$.$\|x - p\|^2 = \sum_i(x_i - p_i)^2$ differentiates term by term; $a^\top x$ is linear.
3. $2(x - p) = \lambda a$, so $x = p + \tfrac\lambda2a$.Stationarity: the closest point is reached from $p$ by moving along the normal $a$ of the plane.
4. $a^\top x = a^\top p + \tfrac\lambda2a^\top a = 5 + \tfrac92\lambda = 14$, so $\lambda = 2$.Substitute into the constraint; $a^\top p = 1 + 2 + 2$ and $a^\top a = 1 + 4 + 4$.
5. $x^* = (1, 1, 1)^\top + (1, 2, 2)^\top = (2, 3, 3)^\top$, and $\|x^* - p\| = \|a\| = 3$.$\tfrac\lambda2 = 1$, so $x^* - p = a$; check $a^\top x^* = 2 + 6 + 6 = 14$.
6. closest point $(2, 3, 3)^\top$; distance $3$It is the minimum: any other point of the plane is $x^* + z$ with $a^\top z = 0$, and $z \perp a = x^* - p$ gives $\|x^* + z - p\|^2 = 9 + \|z\|^2$. In general step 4 gives distance $\lvert d - a^\top p\rvert/\|a\|$ for the plane $a^\top x = d$, here $9/3$.

Problem 6

1. $f(x) = x^\top Ax$ and $g(x) = x^\top x$ with $c = 1$; $\nabla f = 2Ax$ and $\nabla g = 2x$.The gradient of $x^\top Ax$ is $(A + A^\top)x$, which is $2Ax$ for symmetric $A$; $x^\top x$ is the case $A = I$.
2. $2Ax = \lambda\cdot2x$, that is $Ax = \lambda x$.Stationarity: the candidates are the unit eigenvectors of $A$, and the multiplier is the eigenvalue.
3. At a candidate, $f = x^\top Ax = \lambda\,x^\top x = \lambda$.Substitute $Ax = \lambda x$, then the constraint $x^\top x = 1$.
4. The unit sphere is closed and bounded, so the maximum exists and is a candidate; the largest candidate value is $\lambda_{\max}(A)$.By step 3 the candidate values are exactly the eigenvalues; likewise the minimum is the smallest eigenvalue.
5. For the given $A$: $\det(A - \lambda I) = (2 - \lambda)^2 - 1 = 0$, so $\lambda = 3$ or $1$, with eigenvectors $(1, 1)^\top$ and $(1, -1)^\top$.$2 - \lambda = \pm1$; then $A(1,1)^\top = (3,3)^\top$ and $A(1,-1)^\top = (1,-1)^\top$.
6. $\max_{\|x\|=1}x^\top Ax = \lambda_{\max}(A)$, attained at a unit eigenvector; here the maximum is $3$ at $\pm\tfrac1{\sqrt2}(1,1)^\top$ and the minimum $1$ at $\pm\tfrac1{\sqrt2}(1,-1)^\top$Check: $x = \tfrac1{\sqrt2}(1,1)^\top$ gives $x^\top Ax = \tfrac12(2 + 1 + 1 + 2) = 3$. This is why the first principal component, the direction of largest variance $x^\top\Sigma x$, is the top eigenvector of the covariance matrix.

Problem 7

Every $p_i$ is taken positive. The derivative of $-t\log t$ tends to $+\infty$ as $t \to 0^+$, so moving a little probability onto an empty outcome always raises $H$, and the maximum is not on the boundary.

1. $\dfrac{\partial H}{\partial p_i} = -\log p_i - 1$.Product rule on $-p_i\log p_i$; no other term of $H$ contains $p_i$.
2. Normalisation only: $-\log p_i - 1 = \lambda$ for every $i$.$\nabla H = \lambda\nabla g$ with $g = \sum_ip_i$, whose gradient is the all-ones vector.
3. $p_i = e^{-1-\lambda}$, the same for every $i$, so $p_i = \tfrac1n$ and $H = -\sum_i\tfrac1n\log\tfrac1n = \log n$.Solve step 2 for $p_i$; then $\sum_ip_i = 1$ fixes the common value.
4. This is the maximum.$-t\log t$ has second derivative $-1/t < 0$, so $H$ is concave, and on a constraint set cut out by linear equations a stationary point of a concave function is its maximum. The entropy page proved the same bound with the KL divergence.
5. With the mean: $-\log p_i - 1 = \lambda + \beta x_i$.Two constraints, two multipliers: $\nabla H = \lambda\nabla(\sum_ip_i) + \beta\nabla(\sum_ip_ix_i)$, and the second gradient is the vector of values $x_i$.
6. $p_i = e^{-1-\lambda}e^{-\beta x_i}$, and $\sum_ip_i = 1$ gives $e^{-1-\lambda} = 1/\sum_je^{-\beta x_j}$.Exponentiate step 5; the factor $e^{-1-\lambda}$ is the same for every $i$, so normalisation determines it.
7. For $x = (0, 1, 2)$ write $r = e^{-\beta}$: $p = \dfrac{(1, r, r^2)}{1 + r + r^2}$, with mean $\dfrac{r + 2r^2}{1 + r + r^2} = \dfrac47$.$e^{-\beta x_i} = r^{x_i}$, and the mean is $\sum_ip_ix_i$; the remaining constraint fixes $\beta$.
8. $7r + 14r^2 = 4 + 4r + 4r^2$, so $10r^2 + 3r - 4 = (2r - 1)(5r + 4) = 0$, and $r = \tfrac12$.Cross-multiply and collect terms; $r = e^{-\beta} > 0$ rules out $-\tfrac45$.
9. $\beta = \log 2$ and $p = \dfrac{(1, \tfrac12, \tfrac14)}{7/4} = (\tfrac47, \tfrac27, \tfrac17)$.$e^{-\beta} = \tfrac12$; $1 + \tfrac12 + \tfrac14 = \tfrac74$. Check: mean $\tfrac27 + \tfrac27 = \tfrac47$.
10. Normalisation only: $p_i = \tfrac1n$, $H = \log n$. With the mean: $p_i = \dfrac{e^{-\beta x_i}}{\sum_je^{-\beta x_j}}$, and for $x = (0,1,2)$, $\mu = \tfrac47$: $\beta = \log 2$, $p = (\tfrac47, \tfrac27, \tfrac17)$The second form is the softmax of $-\beta x$, the Gibbs distribution; $\beta = 0$ gives back the uniform distribution, whose mean here is $1$. A mean below $1$ needs $\beta > 0$, which tilts the probability toward small $x_i$. The concavity argument of step 4 again makes it the maximum.

Problem 8

1. The constraints are $a_i^\top x = b_i$ for $i = 1, \dots, m$, where $a_i^\top$ is row $i$ of $A$; give them multipliers $\nu_1, \dots, \nu_m$, collected in $\nu \in \mathbb{R}^m$.One multiplier per constraint; $\nu$ avoids a clash with the eigenvalue $\lambda$ of Problem 6.
2. $x = \sum_i\nu_ia_i = A^\top\nu$.Stationarity: $\nabla\tfrac12\|x\|^2 = x$ and $\nabla(a_i^\top x) = a_i$. The columns of $A^\top$ are the $a_i$, so the sum is $A^\top\nu$.
3. $AA^\top\nu = b$, so $\nu = (AA^\top)^{-1}b$.Substitute into $Ax = b$. $AA^\top$ is $m\times m$ and invertible because the rows of $A$ are independent.
4. $x^* = A^\top(AA^\top)^{-1}b$.Substitute $\nu$ back into step 2.
5. Any other solution is $x^* + z$ with $Az = 0$, and $\|x^* + z\|^2 = \|x^*\|^2 + 2\nu^\top Az + \|z\|^2 = \|x^*\|^2 + \|z\|^2$.$x^{*\top}z = \nu^\top Az = 0$, so the cross term vanishes; every other solution is longer, and $x^*$ is the minimum.
6. For the given $A$: $AA^\top = \begin{bmatrix}2&1\\1&2\end{bmatrix}$, $(AA^\top)^{-1} = \tfrac13\begin{bmatrix}2&-1\\-1&2\end{bmatrix}$, and $\nu = \tfrac13(1, 1)^\top$.Entry $(i, j)$ of $AA^\top$ is row $i$ dotted with row $j$; the determinant is $3$, and the $2\times2$ inverse swaps the diagonal and negates the off-diagonal.
7. $x^* = A^\top\nu = \tfrac13(1, 0, 1)^\top + \tfrac13(0, 1, 1)^\top = \tfrac13(1, 1, 2)^\top$.$A^\top\nu$ is $\nu_1$ times the first row of $A$ plus $\nu_2$ times the second. Check: $Ax^* = \tfrac13(1 + 2,\ 1 + 2)^\top = (1, 1)^\top$.
8. $x^* = A^\top(AA^\top)^{-1}b$; for this $A$ and $b$, $x^* = (\tfrac13, \tfrac13, \tfrac23)^\top$$x^*$ lies in the row space of $A$, orthogonal to the null space: here $(\tfrac13, \tfrac13, \tfrac23)\cdot(1, 1, -1) = 0$. It is the pseudoinverse solution $A^+b$ of the least-squares page, the wide-matrix counterpart of $(A^\top A)^{-1}A^\top b$.

Problem 9

1. $y = \lambda$, $x = 2\lambda$ and $4\lambda = c$, so $\lambda(c) = \tfrac c4$ and $(x, y) = (\tfrac c2, \tfrac c4)$.Problem 2's equations with $8$ replaced by $c$.
2. $f^*(c) = \tfrac c2\cdot\tfrac c4 = \tfrac{c^2}8$, so $\dfrac{df^*}{dc} = \tfrac c4 = \lambda(c)$.Differentiate in $c$; at $c = 8$ both are $2$, as in Problem 2.
3. In general $f^*(c) = f(x^*(c))$, so $\dfrac{df^*}{dc} = \nabla f(x^*)^\top\dfrac{dx^*}{dc}$.Chain rule through the path the optimum traces as $c$ changes.
4. $\nabla f(x^*)^\top\dfrac{dx^*}{dc} = \lambda\,\nabla g(x^*)^\top\dfrac{dx^*}{dc}$.Stationarity at the optimum, $\nabla f = \lambda\nabla g$.
5. $g(x^*(c)) = c$ for every $c$, so $\nabla g(x^*)^\top\dfrac{dx^*}{dc} = 1$.Differentiate the constraint, which holds identically in $c$, with the same chain rule.
6. $f^*(c) = \tfrac{c^2}8$ and $\lambda(c) = \tfrac c4$, so $\dfrac{df^*}{dc} = \tfrac c4 = \lambda$; in general $\dfrac{df^*}{dc} = \nabla f^\top\dfrac{dx^*}{dc} = \lambda\,\nabla g^\top\dfrac{dx^*}{dc} = \lambda$$\lambda$ is the price of the constraint: raising $c$ from $8$ to $9$ raises the maximum by about $2$ (exactly $\tfrac{81}8 - 8 = \tfrac{17}8$). For the box of Problem 4, $\lambda = 1$: the least area for volume $V$ is $S^*(V) = 3(2V)^{2/3}$, whose derivative at $V = 32$ is $1$, so one more unit of volume costs about one more unit of area.

Problem 10

1. $h(x, y) = x + y - c \le 0$ with $c = 2$ or $4$; $\nabla f = \big(2(x - 2),\ 2(y - 1)\big)^\top$ and $\nabla h = (1, 1)^\top$.The KKT conditions of Before you start need the constraint in the form $h \le 0$.
2. $2(x - 2) + \mu = 0$ and $2(y - 1) + \mu = 0$, so $x = 2 - \tfrac\mu2$ and $y = 1 - \tfrac\mu2$.Stationarity, $\nabla f + \mu\nabla h = 0$, by components.
3. Inactive case, $\mu = 0$: $(x, y) = (2, 1)$, where $x + y = 3$.Complementary slackness allows $\mu = 0$; then the point is the unconstrained minimum of $f$.
4. (a) $3 > 2$, so $(2, 1)$ is infeasible and the constraint must be active: $x + y = 3 - \mu = 2$ gives $\mu = 1$, the point $(\tfrac32, \tfrac12)$ and $f = \tfrac14 + \tfrac14 = \tfrac12$.With the inactive case ruled out, $\mu h = 0$ forces $h = 0$; and $\mu = 1 \ge 0$, so all four conditions hold.
5. (b) $3 \le 4$, so $(2, 1)$ is feasible, $\mu = 0$ satisfies all four conditions, and $f = 0$.$f \ge 0$ everywhere, so $0$ cannot be beaten.
6. (a) active: $(\tfrac32, \tfrac12)$, $\mu = 1$, $f = \tfrac12$; (b) inactive: $(2, 1)$, $\mu = 0$, $f = 0$$f$ is convex and the constraint linear, so a KKT point is the minimum. $\mu$ is a sensitivity, as in Problem 9: in (a) the minimum is $f^*(c) = \tfrac{(3 - c)^2}2$ for $c < 3$, with $\tfrac{df^*}{dc} = -1 = -\mu$ at $c = 2$, so loosening the constraint lowers the minimum at rate $\mu$; in (b) loosening it changes nothing, and $\mu = 0$.