Proof of Lagrange Multipliers

Throughout, the arithmetic and order of $\mathbb{R}$ are used through The Structure of ℝ as a Field and an Ordered Ring (i), The Structure of ℝ as a Field and an Ordered Ring (ii), Arithmetic and Order Rules in the Real Numbers, Stated for ℝ (v), Arithmetic and Order Rules in the Real Numbers, Stated for ℝ (ix), Rules of Arithmetic and Order in an Ordered Field (iii) and The Quotient 1/x, Order Rules for Sums, and Nesting of Closed Intervals in ℝ (i); norms and distances in $\mathbb{R}^{n}$ through Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square (ii), Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square (v), Properties of the Euclidean Norm on $\mathbb{R}^n$: Square, Distance, Vanishing, Coordinate Bounds, Homogeneity, Triangle Inequalities and Expansion of a Square (vi) and Standard Basis Vectors of ℝ^q: Coordinates, Orthonormality and Unit Length (iii); and the metric spaces $(\mathbb{R}^{n},d_{E})$ and $(\mathbb{R},d_{\mathbb{R}})$ through $\mathbb{R}^n$ with the Euclidean Distance Is a Complete Metric Space with Coordinatewise Convergence (i) and The Absolute Value Metric on the Real Numbers (i); and the identity $e_{i}\cdot e_{j}=\delta_{ij}$ for $i,j\in[n]$ through Lines, Scalar Multiples, Basis Directions, Small Balls and Matrix Rows in ℝⁿ (viii) with $t=1$ and Lines, Scalar Multiples, Basis Directions, Small Balls and Matrix Rows in ℝⁿ (ii).

We first deduce (ii) from (i). Let $g:U\to\mathbb{R}^{1}$ be the map whose single component is $g_{1}=\varphi$; it is of class $C^{1}$ on $U$ (Functions of Class Cᵏ on an Open Subset of ℝⁿ (iii)), and $M=\{x\in U:g(x)=0\}$. Since $\nabla\varphi(a)\neq0$, some partial derivative $\partial_{j}\varphi(a)$ is nonzero. The Jacobian matrix $Dg(a)$ is the single row $\nabla\varphi(a)^{\top}$, so with $\sigma(1)=j$ the $1\times1$ matrix $\bigl(\partial_{j}\varphi(a)\bigr)$ is invertible; and $m=1<n$ because $n\ge2$. Hence (i) gives $\lambda\in\mathbb{R}^{1}$ with

$$\nabla f(a)=\lambda_{1}\,\nabla\varphi(a),$$

and $\lambda_{1}$ is the required multiplier.

We now prove (i). Put $r=n-m$, a natural number since $m<n$. The plan is to renumber the coordinates so that the $m$ chosen columns of $Dg(a)$ come last, to solve the equation $g=0$ for the last $m$ coordinates by the implicit function theorem, and to apply the first-order condition for a local extremum to $f$ along the resulting parametrization of $M$.

Renumbering the coordinates. Extend $\sigma$ to a bijection $\pi:[n]\to[n]$ with $\pi(r+l)=\sigma(l)$ for $l\in[m]$, by enumerating the $r$ indices outside $\sigma([m])$ as $\pi(1),\dots,\pi(r)$. Let $P\in\mathcal{M}_{n}(\mathbb{R})$ be the permutation matrix with $Pe_{i}=e_{\pi(i)}$ for $i\in[n]$. Since $\pi$ is injective,

$$(Pe_{i})\cdot(Pe_{j})=e_{\pi(i)}\cdot e_{\pi(j)}=\delta_{ij},$$

so $P$ is orthogonal by Rules for Orthogonal Matrices: Inverse, Products, Isometry, Columns, Determinant, Orthonormal Extension and Expansion (iv). Consequently $P^{-1}=P^{\top}$ and $\lVert Pz\rVert=\lVert z\rVert$ for every $z\in\mathbb{R}^{n}$, by Rules for Orthogonal Matrices: Inverse, Products, Isometry, Columns, Determinant, Orthonormal Extension and Expansion (i) and Rules for Orthogonal Matrices: Inverse, Products, Isometry, Columns, Determinant, Orthonormal Extension and Expansion (iii). Put $\tilde U=\{z\in\mathbb{R}^{n}:Pz\in U\}$. This set is open: for $z\in\tilde U$ there is $\varepsilon>0$ with $B(Pz,\varepsilon)\subseteq U$ (Lines, Scalar Multiples, Basis Directions, Small Balls and Matrix Rows in ℝⁿ (x)), and then $B(z,\varepsilon)\subseteq\tilde U$, because $\lVert Pz'-Pz\rVert=\lVert z'-z\rVert$. On $\tilde U$ let $\tilde f=f\circ P$ and $\tilde g=g\circ P$, and put $\tilde a=P^{\top}a$ and

$$\tilde M=\{z\in\tilde U:\tilde g(z)=0\}=\{z\in\tilde U:Pz\in M\}.$$

By Constants, Affine Functions, Sums, Products and Quotients of Cᵏ Functions (ii) and Composites of Cᵏ Functions Are of Class Cᵏ (ii), $\tilde f$ and $\tilde g$ are of class $C^{1}$ on $\tilde U$, and the chain rule gives

$$\nabla\tilde f(\tilde a)=P^{\top}\nabla f(a),\qquad D\tilde g(\tilde a)=Dg(a)\,P ,$$

so that column $r+l$ of $D\tilde g(\tilde a)$ is column $\sigma(l)$ of $Dg(a)$. Since $P$ preserves distances and maps $\tilde M$ onto $M$, the restriction $\tilde f|_{\tilde M}$ has a local maximum, respectively a local minimum, at $\tilde a$ relative to $\tilde M$ whenever $f|_{M}$ has one at $a$ relative to $M$ (Local Maximum of a Function Relative to a Subset of a Metric Space (i), Local Minimum of a Function Relative to a Subset of a Metric Space (i)).

Solving the constraints. Write the points of $\mathbb{R}^{n}=\mathbb{R}^{r+m}$ as $(x,y)$ with $x\in\mathbb{R}^{r}$ and $y\in\mathbb{R}^{m}$, use the blocks $D_{x}$, $D_{y}$, $\nabla_{x}$ and $\nabla_{y}$ of Functions of Class Cᵏ: Notation (vi) (with $r$ in place of $n$), and write $\tilde a=(a',b')$. Then $\tilde g(a',b')=g(PP^{\top}a)=g(a)=0$, because $PP^{\top}=I_{n}$ and $a\in M$; and by the previous paragraph $D_{y}\tilde g(a',b')$ is the matrix with entries $\bigl(Dg(a)\bigr)_{k\,\sigma(l)}$, which is invertible by hypothesis. The implicit function theorem, The Implicit Function Theorem (i) together with The Implicit Function Theorem (iii) (with $k=1$, $r$ in place of $n$, and $\tilde U$ and $\tilde g$ in place of $U$ and $F$), therefore gives open sets $A\ni a'$ and $B\ni b'$ with $A\times B\subseteq\tilde U$ and a function $h:A\to B$ of class $C^{1}$ such that $\tilde g(x,h(x))=0$ for $x\in A$, $h(a')=b'$, and

$$Dh(a')=-D_{y}\tilde g(\tilde a)^{-1}D_{x}\tilde g(\tilde a).$$

The first-order condition. Let $\Phi:A\to\mathbb{R}^{n}$, $\Phi(x)=(x,h(x))$, a map with values in $A\times B\subseteq\tilde U$. Its first $r$ component maps are the coordinate functions $x\mapsto x_{j}$, $j\in[r]$, smooth on $A$ by Constants, Affine Functions, Sums, Products and Quotients of Cᵏ Functions (iii) and hence of class $C^{1}$ (Basic Properties of Cᵏ Functions (ii)), and its last $m$ component maps are $h_{1},\dots,h_{m}$; so $\Phi$ is of class $C^{1}$ on $A$ (Functions of Class Cᵏ on an Open Subset of ℝⁿ (iii)). Let $\psi=\tilde f\circ\Phi:A\to\mathbb{R}$, that is, $\psi(x)=\tilde f(x,h(x))$; it is differentiable on $A$ by the chain rule, since $\tilde f$ and $h$ are differentiable by Basic Properties of Cᵏ Functions (v). We show that $\psi$ has a local extremum at $a'$, choosing first $\delta$ and then $\delta'$. First take $\delta>0$ from the local extremum of $\tilde f|_{\tilde M}$ at $\tilde a$, so that $\tilde f(z)\le\tilde f(\tilde a)$ (respectively $\ge$) for every $z\in\tilde M$ with $\lVert z-\tilde a\rVert<\delta$. Next, $\Phi$, being of class $C^{1}$, is continuous at $a'$ (Basic Properties of Cᵏ Functions (iv)), so there is $\delta'>0$ such that every $x\in A$ with $\lVert x-a'\rVert<\delta'$ satisfies $\lVert(x,h(x))-\tilde a\rVert<\delta$. For such $x$ the point $(x,h(x))$ lies in $\tilde M$, hence $\psi(x)\le\psi(a')$ (respectively $\ge$). Thus $\psi$ has a local maximum or a local minimum at $a'$ relative to the open set $A$, and First- and Second-Order Conditions at a Local Extremum (i) (with $A$ in place of $U$) gives $\nabla\psi(a')=0$.

The multiplier. We have $\Phi(a')=(a',h(a'))=(a',b')=\tilde a$. In block form $\Phi(x)=E_{1}x+E_{2}h(x)$, where $E_{1}\in\mathcal{M}_{n\times r}(\mathbb{R})$ has the block $I_{r}$ above the block $0_{m\times r}$ and $E_{2}\in\mathcal{M}_{n\times m}(\mathbb{R})$ has the block $0_{r\times m}$ above the block $I_{m}$. As $E_{1}$ and $E_{2}$ are constant matrices,

$$D\Phi(a')=E_{1}+E_{2}\,Dh(a')=\begin{pmatrix}I_{r}\\Dh(a')\end{pmatrix},$$

and the chain rule gives $\nabla\psi(a')=D\Phi(a')^{\top}\nabla\tilde f(\tilde a)$. Splitting $\nabla\tilde f(\tilde a)$ into $\nabla_{x}\tilde f(\tilde a)\in\mathbb{R}^{r}$ and $\nabla_{y}\tilde f(\tilde a)\in\mathbb{R}^{m}$, this reads

$$0=\nabla\psi(a')=\nabla_{x}\tilde f(\tilde a)+Dh(a')^{\top}\nabla_{y}\tilde f(\tilde a).$$

Define

$$\lambda=\bigl(D_{y}\tilde g(\tilde a)^{\top}\bigr)^{-1}\nabla_{y}\tilde f(\tilde a)\in\mathbb{R}^{m},$$

so that $\nabla_{y}\tilde f(\tilde a)=D_{y}\tilde g(\tilde a)^{\top}\lambda$. Inserting the formula for $Dh(a')$ obtained from the implicit function theorem,

$$\nabla_{x}\tilde f(\tilde a)=D_{x}\tilde g(\tilde a)^{\top}\bigl(D_{y}\tilde g(\tilde a)^{\top}\bigr)^{-1}\nabla_{y}\tilde f(\tilde a)=D_{x}\tilde g(\tilde a)^{\top}\lambda .$$

Together the two blocks say $\nabla\tilde f(\tilde a)=D\tilde g(\tilde a)^{\top}\lambda$. By the identities for $\nabla\tilde f(\tilde a)$ and $D\tilde g(\tilde a)$ found when renumbering the coordinates, this reads $P^{\top}\nabla f(a)=P^{\top}Dg(a)^{\top}\lambda$, and multiplying by $P$ gives

$$\nabla f(a)=Dg(a)^{\top}\lambda .$$

Finally, the $k$-th row of $Dg(a)$ is $\nabla g_{k}(a)^{\top}$ (Jacobian Matrix of a Function Between Euclidean Spaces (i), Gradient of a Real-Valued Function on an Open Subset of $\mathbb{R}^n$ (i)), so $Dg(a)^{\top}\lambda=\sum_{k\in[m]}\lambda_{k}\nabla g_{k}(a)$.