Constrained optimization
The method of Lagrange multipliers
Consider an implicitly defined manifold $M = \set{ g = c}$ for some $C^1$ function $g \colon \R^n \to \R^m$. Suppose we want to optimize a function $f \colon \R^n \to \R$ under the constraint $g = c$.
Definition 1. We say $f$ attains a constrained local minimum at the point $a$, subject to the constraint $g = c$ if $g(a) = c$ and there exists $r > 0$ such that for every $x \in B(a, r) \cap \set{g = c}$ we have $f(x) \geq f(a)$. (A constrained local maximum is defined similarly.)
Theorem 2 (Lagrange multipliers). Let $U \subseteq \R^n$ be open, $f \colon U \to \R$ be $C^1$, $g \colon U \to \R^m$ be $C^1$, $c \in \R^m$. Suppose $f$ attains a constrained local extremum at some point $a \in \set{g = c}$, and $\rank(Dg_a) = m$. Then there exist $\lambda_1$, …, $\lambda_m$ such that \begin{equation}\label{e:lagrange}\tag{L} \grad f(a) = \sum_{i = 1}^m \lambda_i \grad g_i(a) \,. \end{equation}
Example 3. Visualize maximizing the function $f(x) = x_1$ subject to the constraint $\abs{x} = 1$.
Remark 4. To use Lagrange multipliers, we have to solve for the unknowns $a_1$, …, $a_n$ and $\lambda_1$, …, $\lambda_m$ (which is $n + m$ unknowns total). We have $g(a) = c$ (which is $m$ equations), and the condition equation \eqref{e:lagrange}, which is $n$ equations. This is a total of $n + m$ unknowns and $n + m$ equations, which formally matches our equation to unknown count.
Wrong proof of Theorem 2. Many books prove Theorem 2 incorrectly as follows. Define the Lagrangian $L$ by \begin{equation} L(x, \lambda) = f(x) + \lambda \cdot (g(x) - c) \,. \end{equation} Now compute derivatives and check that at any local extrema of $L$ we must have both the constraint $g(a) = c$ and the condition \begin{equation} \grad f(a) + \sum_{i = 1}^m \lambda_i \grad g_i(a) = 0 \,. \end{equation} Flipping signs of $\lambda$, they incorrectly conclude Theorem 2.
This is not correct! It shows unconstrained local extrema of $L$ satisfy both the constraint and \eqref{e:lagrange}. Of course, constrained local extrema of $f$ need not be unconstrained local minima of $L$, and so the above proof is incorrect.
We will provide a correct proof by proving a more general fact.
Lemma 5. Let $M \subseteq \R^n$ be a $C^1$-manifold, $U \supseteq M$ be open and $f \colon U \to \R$ be $C^1$. If $f$ attains a constrained local extremum at some point $a \in M$, then \begin{equation} \grad f(a) \in N M_a \,. \end{equation}
Proof sketch. Pick any $C^1$ curve $\gamma \colon (-r, r) \to M$ such that $\gamma(0) = a$, note that $f \circ \gamma$ has a local extremum at $0$. The chain rule now implies $D f_a \gamma’(0) = 0$.
Proof sketch of Theorem 2. Find $U’ \ni a$ open so that $\rank Dg_x = m$ for all $x \in U’$. Now $M = U’ \cap \set{g = c}$ is a $d$-dimensional manifold, and by the lemma $\grad f_a \in N M_a$. Since we know that $\grad g_1(a)$, …, $\grad g_m(a)$ form a basis of $N M_a$, the theorem follows.
Examples and Problems
Problem 6. Let $f \colon \R^d \to \R$. Given $(x, y) \in \R^{d+1}$ define $g(x, y) = y$. Show that the method of Lagrange multipliers can be applied to extremize the function $g$ subject to the constraint $y = f(x)$, and verify that the method shows $\grad f = 0$ at constrained local extrema. (This should not be a surprise, since constrained local extrema of $g$ are simply local extrema of $f$.)
Problem 7. Given $a, b > 0$, maximize $x y$ subject to the constraint $\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$.
Problem 8. The plane $x + y + 2z = 2$ intersects the paraboloid $z = x^2 + y^2$ in an ellipse. Find the points on this ellipse that are nearest to and farthest from the origin.
Problem 9. Maximise the volume of an open box given the surface area is $3 a^2$. (That is, maximise $xyz$ under the constraint $xy + 2(yz + zx) = 3a^2$.)
Problem 10. Maximise the volume of a cylinder given that the total surface area is $6\pi a^2$. [For fun, check if the proportions of your optimal cylinder agrees with your standard coke can; if not, write to Coco-cola with a proposal to save money and the environment…]
Problem 11. Prove the Cauchy–Schwartz inequality in $\R^d$ by extremizing $x \cdot y$ subject to the constraint $\abs{x} = a$ and $\abs{y} = b$.
Remark 12. This is of course, not a correct proof of the Cauchy–Schwartz inequality as we certainly used it in order to derive Theorem 2.
Problem 13 (Inequality of the means). If $x_i \geq 0$, then \begin{equation*} \frac{1}{n} \sum_1^n x_i \geq \paren[\Big]{ \prod_1^n x_i }^{1/n}. \end{equation*}
Hint. There are several proofs of this; but the one relevant here is to maximize $\prod x_i$ under the constraint $\sum x_i = c$.
Proposition 14 (Young’s inequality). If $p, q > 1$ and $1/p + 1/q = 1$ then for every $x, y \in \R$, \begin{equation} \abs{xy} \leq \frac{\abs{x}^p}{p} + \frac{\abs{y}^q}{q}. \end{equation}
Hint. Again, this has several direct proofs; but you can do it here by constrained minimization.
Sometimes when maximising a function in the region $\set{ g \leq c }$, the maximum (or minimum) could be attained on the boundary $\set{g = c}$. In this case you can of course find all interior local maxima and minima by solving $\grad f = 0$ and looking at $Hf$. For maxima and minima on the boundary, it is often convenient to use Lagrange multipliers.
Problem 15. Find the absolute maxima and minima of $e^{-xy}$ on the set $x^2 + 4 y^2 \leq 1$.
Problem 16. Let $M \subseteq \R^n$ be a $C^1$ manifold, and $a \in \R^n - M$. Suppose there exists a point $x_* \in M$ which is the closest point in $M$ to $a$. Then show that $x_* - a \in N M_x$. In particular, if $M = \set{g = c}$ for some function $g \colon \R^n \to \R^m$ such that $\rank(Dg_{x_*}) = m$, then show that there exist $\lambda_1$, …, $\lambda_m$ such that $x - a = \sum_1^m \lambda_i \grad g_i$.
Problem 17. Let $M, N \subseteq \R^n$ be two a $C^1$ manifolds such that $M \cap N = \emptyset$. Suppose further there exists $a \in M$, $b \in N$ such that \begin{equation} \abs{a - b} = \inf_{x \in M, y \in N} \abs{x - y} \,. \end{equation} Then $a - b \in NM_a$ and $a - b \in NN_b$. (In particular if $M, N$ are implicitly defined as level sets of two functions $g, h$ respectively, then there exist $\lambda_i, \mu_j$ such that $a -b = \sum \lambda_i \grad g_i = \sum \mu_j \grad h_j$.)
Problem 18. Let $g \colon \R^n \to \R^m$ be a $C^1$ function, $c \in \operatorname{Range}(g)$, $M = \set{g = c}$, and suppose $\rank( Dg_x ) = m$ for every $x \in M$. Let $f \colon \R^n \to \R$ be $C^2$, and suppose that at some point $a \in M$, the function $f$ attains a constrained local minimum at $a$ subject to the constraint $g = c$.
- If $g \colon \R^n \to \R^m$ is linear, then show that $Hf_a$ is positive semi-definite on $TM_a$ (i.e. show $v \cdot (Hf_a v) \geq 0$ for all $v \in TM_a$).
- Show by example that if $g$ is not linear, then $Hf_a$ need not be positive semi-definite on $TM_a$.