1. 经典的 Lagrange 乘子法

经典的 Lagrange 乘子法是针对等式约束下的非线性方程最优化问题，将其转化为一个方程组的求解问题，具体形式如下：

\[ \left\{ \begin{aligned} &\max f(\mathbf{x})\\ &s.t. g(\mathbf{x})=0 \end{aligned} \right. \]

其中\(\mathbf{x}\in R^N\)，\(f,g:R^N \to R\)，对于上述问题引入 Lagrange 乘子\(\lambda \in R\)，定义 Lagrange 函数\(L(\mathbf{x},\lambda)\)：

\[ L(\mathbf{x},\lambda) = f(\mathbf{x}) - \lambda \,g(\mathbf{x}) \]

则\(\mathbf{x}\)取到最优解的必要条件为\((\mathbf{x}, \lambda)\)满足如下方程组：

\[ \left\{ \begin{aligned} \nabla f(\mathbf{x}) - \lambda \nabla g(\mathbf{x}) &= 0\\ g(\mathbf{x}) &= 0 \end{aligned} \right. \]

注意这只是必要条件，解出的\(\mathbf{x}\)只能保证是一个驻点，需要继续验证是否取到唯一的最值。(如果\(f\)是凸函数，则显然\(\mathbf{x}\)是唯一的)

几何意义：取\(R^N=R^2\)的情形，如图所示，\(w=f(\mathbf{x})=f(x,y)\)等值线如下图，\(g(\mathbf{x})=g(x,y)=0\) 限制为一个圆，\(P\)点是一个满足的解，但方程组的解可能不唯一。

通常我们讨论的 Lagrange 乘子法只涉及最优化方面，从最简单的问题出发，然后会从不等式约束、凸优化、机器学习等角度进行推广和应用。本文会从另外的角度入手，考虑泛函语境下的 Lagrange 乘子法。本文以及下一篇的最终目的是理解这样一句话：在不可压流满足的 Stokes 方程组中，压强是作为 Lagrange 乘子存在的。

2. 线性方程组求解与 Lagrange 乘子法

对于一般的线性方程组

\[ Ax=b \]

其中\(A\in R^{m\times n},b\in R^m\)给定，待求解向量\(x \in R^n\)，可以分成三种情形：

  • 线性方程组存在唯一解；
  • 线性方程组存在无穷多的解，此时可以要求给出最小范数的解\(x_0\)； \[ \min_{Ax=b} \Vert x \Vert \]
  • 线性方程组无解，即为矛盾方程组，此时可以在最小二乘的意义下求解。若\(A\)无法保证列向量线性无关，最小二乘解仍然不唯一，此时可以要求最小范数的最小二乘解\(x_0\)。 \[ \begin{aligned} \min_{x \in R^n} \Vert Ax-b \Vert\\ \min_{x \in \text{argmin} \Vert Ax-b \Vert} \Vert x \Vert \end{aligned} \]

2.1 最小二乘法

对于最小二乘法得到的解\(x_0\)，必然满足法方程

\[ A^T A x = A^T b \]

当\(A\)列向量线性无关时，\(A^T A\)对称正定，存在唯一的最小二乘解\(x_0 = (A^T A)^{-1} A^T b\)。

最小二乘法实际上求解的是二次泛函\(\widetilde{J}_{ls}(x)\)的极小值点

\[ \widetilde{J}_{ls}(x) = (Ax-b)^T (Ax-b) = x^T A^T A x - 2b^T A x + b^T b \]

或者记作\(J_{ls}(x)\)

\[ J_{ls}(x) = \frac12 x^T A^T A x - b^T A x \]

2.2 对称正定问题——最速下降法

对于对称正定的方阵\(M\)，求解

\[ M x = f \]

显然方程组一定存在唯一解，并且问题等价于求解如下泛函\(\phi(x)\)的极小值点

\[ \phi(x) = \frac12 x^T M x - f^T x \]

最速下降和共轭梯度法等都是针对这个二次泛函\(\phi(x)\)不断调整\(x\)，移动到极小值点\(x_0\)。

上述最小二乘的\(J_{ls}(x)\)就是对于法方程\(M=A^T A\)得到的\(\phi(x)\)。最小二乘法的求解往往可以化归为对称正定方程组的求解，当然也可以根据 QR 分解来处理。

2.3 限制子空间中的最小二乘法

取线性子空间\(Ker(C)\)为限制空间，\(C\)为已知的矩阵

\[ Ker(C)=\{x | Cx=0 \} \]

显然有\(C\)的列向量线性相关，否则\(Ker(C)=\{0\}\)是平凡的。可以要求\(C\)的行向量线性无关，通常\(C\)的行数远小于列数。

在限制子空间\(Ker(C)\)中求解最小二乘问题

\[ \min_{Cx=0} \Vert Ax-b \Vert \]

也就是求解法方程\(A^T A x = A^T b\)对应的\(J_{ls}(x)\)的极小值点。

\[ J_{ls}(x) = \frac12 x^T A^T A x - b^T A x \]

引入 Lagrange 乘子\(\Lambda\)，得到

\[ L(x,\Lambda) = J_{ls}(x) + x^T C^T \Lambda \]

对 Lagrange 函数\(L(x,\Lambda)\)求导即

\[ \begin{aligned} \nabla_x L(x,\Lambda) &= \nabla J_{ls}(x) + C^T \Lambda = A^T A x - A^T b+ C^T \Lambda = 0\\ \nabla_{\Lambda} L(x,\Lambda) &= x^T C^T = 0 \end{aligned} \]

整理即

\[ \begin{bmatrix} A^T A & C^T \\ C & 0 \end{bmatrix} \begin{bmatrix} x\\ \Lambda \end{bmatrix} = \begin{bmatrix} A^T b\\ 0 \end{bmatrix} \]

假设\(A\)列满秩，即\(A^TA\)对称正定，此时最小二乘解唯一。Lagrange 乘子\(\Lambda\)满足

\[ \begin{aligned} Cx = C (A^T A)^{-1} \left( A^T b - C^T \Lambda \right) = 0\\ C(A^T A)^{-1} C^T \Lambda = C(A^T A)^{-1} A^T b \end{aligned} \]

必然存在可逆的\(P\)，使得\(P^T P =A^T A\)，记 \(Q=P^{-T} C^T\)

\[ C(A^T A)^{-1} C^T = C P^{-1} P^{-T} C^T = Q^T Q \]

由于\(C^T\)列满秩，\(P\)可逆，因此\(Q = P^{-T} C^T\)仍然是列满秩的，\(Q^T Q\)对称正定，Lagrange 乘子\(\Lambda\)是存在唯一的，扩充后的方程组

\[ \begin{bmatrix} A^T A & C^T \\ C & 0 \end{bmatrix} \begin{bmatrix} x\\ \Lambda \end{bmatrix} = \begin{bmatrix} A^T b\\ 0 \end{bmatrix} \]

存在唯一解\((x,\Lambda)\)，其中的\(x\)即为唯一的最小二乘解。

2.4 限制子空间中的对称正定问题

同上，取线性子空间\(Ker(C)\)为限制空间，\(C\)为已知的矩阵

\[ Ker(C)=\{x | Cx=0 \} \]

\(C\)的列向量线性相关，\(C\)的行向量线性无关，通常\(C\)的行数远小于列数。

在限制子空间\(Ker(C)\)中求如下二次泛函\(\phi(x)\)的极小值，其中\(M\)对称正定

\[ \phi(x)= \frac12 x^T M x - f^T x \]

引入 Lagrange 乘子\(\Lambda\)，得到

\[ L(x,\Lambda) = \phi(x) + x^T C^T \Lambda \]

对 Lagrange 函数\(L(x,\Lambda)\)求导即

\[ \begin{aligned} \nabla_x L(x,\Lambda) &= \nabla \phi(x) + C^T \Lambda = M x - f + C^T \Lambda = 0\\ \nabla_{\Lambda} L(x,\Lambda) &= - x^T C^T = 0 \end{aligned} \]

整理即

\[ \begin{bmatrix} M & C^T \\ C & 0 \end{bmatrix} \begin{bmatrix} x\\ \Lambda \end{bmatrix} = \begin{bmatrix} f\\ 0 \end{bmatrix} \]

与前文一样的分析可知，扩充后的方程组存在唯一解\((x_0,\Lambda_0)\)。

虽然在全空间中上述问题等价于求解\(Mx=f\)，并且显然存在唯一解\(x_1=M^{-1}f\)，但是在限制子空间中这并不成立：

  1. 扩充后的方程组仍然存在唯一解\((x_0,\Lambda_0)\)；
  2. 得到的唯一解\(x_0\)，对于\(Mx=f\)通常不能严格成立，余量\(Mx-f = -C^T \Lambda\)；
  3. \(Mx-f\)余量为零，等价于\(\Lambda=0\)，几何意义就是\(x_1\)恰好落在限制子空间\(Cx=0\)中，此时\((x_0,\Lambda_0)=(x_1,0)\)

3. 泛函与 Lagrange 乘子法

我们需要更抽象的数学工具得到更一般的 Lagrange 乘子法。

对于 Hilbert 空间\(H\)，\(J\)是定义在\(H\)上的一个下凸的 Frechet 可微的泛函\(J:H\to R\)。这里 Frechet 可微的含义为：对于\(\forall v \in H\)，存在\(f_v \in H^*\)使得下式成立：

\[ J(v+w) = J(v) + \langle f_v,w \rangle + o(\Vert w \Vert) \]

其中 \(\langle f_v, w\rangle\)表示有界线性泛函 \(f_v \in H^*\)作用到元素 \(w \in H\)上，余项的范数是关于\(\Vert w \Vert\)的高阶无穷小。此时记作\(\nabla J(v) = f_v \in H^*\)，视作\(J\)在\(v\)处的"导数"：

\[ J(v+w) = J(v) + \langle \nabla J(v),w \rangle + o(\Vert w \Vert) \]

3.1 等价性的命题

Lagrange 乘子法的核心思想就是把限制子空间的最优化问题转化为全空间的方程组求解问题，这个转化至少是必要的。从泛函的角度，我们也有相应的命题。

对于定义在\(H\)上的一个下凸的 Frechet 可微的泛函\(J\)，在限制子空间\(V\)的最优化问题等价于"Frechet 导数"落在\(^{\perp}V\)内：

\[ J(u) = \min_{v \in V} J(v) \iff \nabla J(u) \in ^{\perp}V \]

证明如下： 如果在\(u_0\)处取到最小值，则易知

\[ \langle \nabla J(u_0),v\rangle = 0,\, \forall v \in V \]

因此\(\nabla J(u_0) \in ^{\perp}V\)。反过来，利用下凸的性质，任取\(v \in V\)，\(t > 0\)，有

\[ J(v)-J(u) \ge \frac{1}{t}\left( J(u+t(v-u)) - J(u)\right) \overset{t \to 0^+}\to 0 \]

因此\(J(u) \le J(v)\)取到最小值，命题得证。(如果\(J\)可微但没有下凸性质，则右侧只是必要条件而非充分条件)

3.2 存在性的命题

对于更特殊的情形，我们可以把\(\nabla J(u) \in ^{\perp}V\)具体化，引入 Lagrange 乘子的存在性。

假设有另一个 Hilbert 空间\(M\)，对于限制子空间\(V\)我们取为一个有界线性算子\(T:H\to M^*\)的 Kernel，即

\[ V = Ker(T) = \{ v \in H \,|\, Tv = 0 \in M^*\} \]

我们需要\(T\)的共轭算子\(T^*:M \to H^*\)，共轭算子根据定义即对于任意\(u\in H,w\in M\)下式都成立

\[ \langle Tu,w\rangle = \langle T^* w,u\rangle \]

我们取\(T^*\)的值域

\[ Im(T^*) = \{ u^* \in H^* \,|\, u^* = T^* w,\, \exists\, w \in M\} \]

断言：\(^{\perp}V=Im(T^*)\)的闭包，(如果 \(T^*\) 是闭值域算子，则闭包等于自身)，验证一下：

  • 若\(u^* = T^* w \in Im(T^*)\)，则有 \[ \langle u^*, v\rangle = \langle T^* w, v\rangle = \langle w,T v\rangle = 0, \,\, \forall v \in V=Ker(T) \]
  • 若\(u^* \in H^*\)满足 \(u^* \in ^{\perp}Ker(T) \subset ^{\perp}(Im(T^*)^\perp)\)，根据 HBT 定理的推论可证明\(u^* \in Im(T^*)\)的闭包。(见张恭庆的泛函分析上册)

此时等价性的命题就变成了

\[ J(u) = \min_{v \in Ker(T)} J(v) \iff \nabla J(u) \in \overline{Im(T^*)} \]

如果\(T^*\)是单射的闭算子，则存在更直接的结论，也就是 Lagrange 乘子的存在性命题：

\[ J(u) = \min_{v \in Ker(T)} J(v) \iff \nabla J(u) = T^* w \in Im(T^*) \]

其中的\(w \in M\)若存在则唯一，\(w\)就是我们需要的 Lagrange 乘子。

假设算子\(T^*\)满足条件：存在\(C > 0\)使得

\[ \Vert T^* w\Vert_{H^*} \ge C \Vert w \Vert_M, \forall w \in M \]

则我们可以据此推出\(T^*\)是单射的闭算子，从而满足存在性命题需要。

3.3 小结

我们给出泛函语言下的 Lagrange 乘子法:

对于两个 Hilbert 空间 H,M，有界线性算子\(T: H \to M^*\)是单射的闭算子，定义在\(H\)上的一个下凸的 Frechet 可微的泛函\(J\)，考虑两个问题：

  1. 在限制子空间\(V=Ker(T)\)求泛函\(J\)的极小值点\(u\) \[ J(u) = \min_{v \in Ker(T)} J(v) \]
  2. 求解\((u,w)\in H \times M\)满足如下方程组 \[ \left\{ \begin{aligned} \nabla J(u) &= T^* w\\ T(u) &= 0 \end{aligned} \right. \]

两个问题等价，方程组存在唯一解\((u_0,w_0)\)，其中的\(u_0\)就是\(J\)的极小值点，\(w\)称为 Lagrange 乘子。如果\(J\)没有下凸性，则问题 2 只是问题 1 的必要条件。

3.4 例子

我们用限制子空间的对称正定问题，来说明上述泛函语言下的 Lagrange 乘子法是经典的 Lagrange 乘子法的在齐次限制条件下的推广。

在有限维空间\(R^n\)中取一组单位正交的列向量\(\{a_1,\cdots,c_k\}(k < n)\)，取限制子空间\(V\)为它们的正交补

\[ V=\{x \in R^n | a_i^T x = 0, \forall i=1,\cdots,k\} \]

记 \(C=(a_1,\cdots, a_k)^T \in R^{k \times n}\)，显然

\[ V = Ker(C)=\{ x \in R^n | Cx=0 \} \]

并且有

\[ ^{\perp}V = \text{span}\{a_1,\cdots,a_k\} \]

(这里的正交只是为了理解更加直观，实际上要求线性无关即可)如果我们定义\(T:R^n \to R^k\)

\[ Tx = C x \]

那么\(V=Ker(C)=Ker(T)\)。显然\(T\)是有界线性算子，并且是单射的闭算子。

接下来我们引入定义在\(R^n\)的泛函\(J\)，其中矩阵\(M\)对称正定

\[ J(x) = \frac12 x^T M x - f^T x \]

容易验证它是下凸的，并且是可微的

\[ \nabla J(x) = M x - f \]

根据泛函语言下的 Lagrange 乘子法，\(J(x)\)在限制子空间的极小值问题转化为下列方程组的求解

\[ \left\{ \begin{aligned} Mx - f = \nabla J(u) &= T^* w = C^T w\\ C x = T(x) &= 0 \end{aligned} \right. \]

其中\(w \in R^k\)是引入的 Lagrange 乘子，记\(\Lambda = -w\)，又得到了限制子空间中的对称正定线性方程组问题的扩充方程组

\[ \begin{bmatrix} M & C^T \\ C & 0 \end{bmatrix} \begin{bmatrix} x\\ \Lambda \end{bmatrix} = \begin{bmatrix} f\\ 0 \end{bmatrix} \]