Lagrange 乘数法与 KKT 条件

KKT 条件，即 Karush-Kuhn-Tucker 条件，有时也只取后二人之名为 Kuhn-Tucker 条件。

引入

我们先看一个例子：

\[ \begin{gather} \forall x,y\in \mathbb{N_+}, x+y=1, 求 (\frac1x+\frac4y)_{\min} \end{gather} \]

中学方法直接使用“贴一法”，即可得到

\[ \begin{gather} (\frac1x+\frac4y)(x+y)\geq 5+2\sqrt{\frac{4x}y\cdot\frac yx}=9 \end{gather} \]

但是我们现在来学习一种新的方法去解这个问题： Lagrange 乘数法。

---

内容

在数学最优问题中，** Lagrange 乘数法**(Lagrange Multiplier Method)是一种寻找变量受一个或多个条件限制的多元函数的极值的方法。 这种方法将一个有 \(n\) 个变量、\(p\) 个不等式约束条件和 \(q\) 个等式约束条件的最优化问题转换为一个有 \(n+p+q\) 个变量的方程组的极值问题，其变量不受任何约束。

这种方法引入了一种新的标量未知数，即 Lagrange 乘数：约束方程的梯度的线性组合里每个向量的系数。

要解

\[ \begin{gather} \min \mathrm{or} \max\ f(\mathbf x) \\ \text{s.t.} \begin{cases} g_i(\mathbf x)\leq0, & i=1,2,\dots,p \\ h_j(\mathbf x)=0, & j=1,2,\dots,q \end{cases} \end{gather} \]

我们可以构造 Lagrange 函数

\[ \begin{gather} \mathcal{L}(\mathbf x,\lambda,\mu)=f(\mathbf x)+\sum_{i=1}^p\lambda_ig_i(\mathbf x)+\sum_{j=1}^q\mu_jh_j(\mathbf x) \end{gather} \]

其中 \(\lambda=[\lambda_1,\lambda_2,\dots,\lambda_p]^\intercal\)，\(\mu=[\mu_1,\mu_2,\dots,\mu_q]^\intercal\) 为 ** Lagrange 乘子**。

有方程组

\[ \begin{gather} \begin{cases} \frac{\partial\mathcal{L}}{\partial x_i}=0, & i=1,2,\dots,n \\ \lambda_ig_i(\mathbf x)=0, & i=1,2,\dots,p \\ \lambda_i\geq0, & i=1,2,\dots,p \end{cases} \end{gather} \]

满足上式的点，成为 KKT 点。

---

简单推导

对于二元函数，我们有如下简单推导：

对于目标函数 \(z=f(x,y)\)，有约束条件 \(g(x,y)=0\)。对 \(g(x,y)=0\)，进行隐函数求导，得

\[ \begin{gather} \frac{\mathrm{d}y}{\mathrm{d}x}=-\frac{g'_x}{g'_y} \end{gather} \]

不妨令 \(y=y(x)\)，则 \(z=f(x,y)=f(x,y(x))\)。

要找到驻点，即目标函数导数为零，有

\[ \begin{gather} \frac{\mathrm{d}z}{\mathrm{d}x}=f'_x+f'_y\cdot y'(x)=0 \end{gather} \]

所以，

\[ \begin{align} \frac{\mathrm{d}z}{\mathrm{d}x} & = f'_x+f'_y\cdot\frac{\mathrm{d}y}{\mathrm{d}x} \\ & = f'_x-f'_y\cdot\frac{g'_x}{g'_y} \\ & = 0 \end{align} \]

等式左右同乘以 \(g'_y\)，得

\[ \begin{gather} f'_xg'_y-f'_yg'_x=0 \end{gather} \]

令

\[ \begin{gather} \lambda=-\frac{f'_x}{g'_x}=-\frac{f'_y}{g'_y} \end{gather} \]

得

\[ \begin{gather} \begin{cases} f'_x+\lambda g'_x=0 \\ f'_y+\lambda g'_y=0 \end{cases} \end{gather} \]

以上就推导出了 Lagrange 乘数法，同理可以推广至多元函数。

---

解决“引入”例题

\[ \begin{gather} \min\ \frac1x+\frac4y \\ \text{s.t.} \begin{cases} x+y=1 \\ x,y\in \mathbb{N_+} \end{cases} \end{gather} \]

构造

\[ \begin{gather} \mathcal{L}(x,y,\lambda)=f(x,y)+\lambda\cdot g(x,y) \end{gather} \]

其中 \(f(x,y)=\frac1x+\frac4y, g(x,y)=x+y-1\)。带入，得

\[ \begin{gather} \mathcal{L}(x,y,\lambda)=\frac1x+\frac4y+\lambda(x+y-1) \end{gather} \]

然后得到方程组

\[ \begin{gather} \begin{cases} \frac{\partial\mathcal{L}}{\partial x}=-\frac1{x^2}+\lambda=0 \\ \frac{\partial\mathcal{L}}{\partial y}=-\frac4{y^2}+\lambda=0 \\ x+y-1=0 \end{cases} \end{gather} \]

解得

\[ \begin{gather} \begin{cases} x=\frac1{\sqrt\lambda} \\ y=\frac2{\sqrt\lambda} \end{cases} \end{gather} \]

将 \(x,y\) 代入 \(g(x,y)\) 中，得 \(\frac3{\sqrt\lambda}=1\)。所以 \(\lambda=9, x=\frac13, y=\frac23\)，\(\min\ \frac1x+\frac4y=9\)。

---

其他

求解：

\[ \begin{gather} \min x_1^2+x_2^2 \\ \text{s.t.} \begin{cases} x_1+x_2=1 \\ x_2<3 \end{cases} \end{gather} \]

构造 Lagrange 函数

\[ \begin{gather} \mathcal{L}(x_1,x_2,\lambda_1,\lambda_2)=x_1^2+x_2^2+\lambda_1(x_1+x_2-1)+\lambda_2(x_2-3) \\ \begin{cases} \frac{\partial\mathcal{L}}{\partial x_1}=2x_1+\lambda_1 & = 0\\ \frac{\partial\mathcal{L}}{\partial x_2}=2x_2+\lambda_1+2\lambda_2 & = 0\\ x_1+x_2-1 & = 0 \\ x_2-3 & \leq 0 \\ \lambda_2(x_2-3) & = 0 \\ \lambda_2 & \geq 0 \end{cases} \end{gather} \]

利用 KKT 条件求解问题是解决约束优化的通用方法。

---

不等式约束中的 \(\lambda\) 的取值

当条件是不等式约束时，问题比较复杂些，但可以转化成等式约束的问题。

例：

\[ \min_x f(x)\ \text{s.t.}\ g(x)\leq0 \]

首先看目标函数 \(f(x)\) 在无约束条件下的最优点，显然要么在有效域 \(\mathbb{K}\) 内(\(g(x)\leq0\))，要么在有效域 \(\mathbb{K}\) 外(\(g(x)>0\))。

• 情况 1(如图 A)：若 \(f(x)\) 在无约束条件下的最优点在 \(g(x)\leq0\) 的区域内，则约束条件 \(g(x)\leq0\) 不起作用，可直接求 \(\min_x f(x)\)，相当于 \(\lambda=0\)；

• 情况 2(如图 B)：若 \(f(x)\) 在无约束条件下的最优点在 \(g(x)>0\) 的区域内，则 \(f(x)\) 在约束条件下的最优点必然在 \(g(x)\leq0\) 区域的边界上，即 \(g(x)=0\)，这样此类问题便转化成了等式约束。目标函数为 \(\min_{x,\lambda} L(x,\lambda)=f(x)+\lambda g(x)\)。要想取得最优解，需分别令 \(x,\lambda\) 的偏导等于零。假设取得最优解时 \(x\) 坐标为 \(x^*\)，则有 \(\nabla f(x^*)+\lambda\nabla g(x^*)=0\)。

如果我们要求目标函数的 min 值，而约束条件又是 \(\leq\) 固定值，则梯度 \(\nabla f(x^*)\) 与 \(\nabla g(x^*)\) 的方向相反。因为我们希望最小化 \(f(x)\)，梯度 \(\nabla f(x)\) 在点 \(x\) 的最陡上升方向应该指向有效域 \(\mathbb{K}\) 的内部，因为最优解最小值是在边界取得的，但 \(\nabla g(x)\) 指向有效域 \(\mathbb{K}\) 的外部(即 \(g(x)\geq0\) 的区域)，因为约束是小于等于 0。

根据上面所述“\(\nabla f(x^*)+\lambda\nabla g(x^*)=0\)”及“梯度 \(\nabla f(x^*)\) 与 \(\nabla g(x^*)\) 的方向相反”两个条件，可以推出 \(\lambda>0\)。

综上所述，必有 \(\lambda g(x)=0\)。

所以，原不等式约束问题就转化为

\[ \begin{cases} \min_{x,\lambda} L(x,\lambda)=f(x)+\lambda g(x) \\ \lambda\geq0 \\ \lambda g(x)=0 \end{cases} \]

对于上式，实际上可以解读为 \(\min_x\ \max_\lambda L(x,\lambda)\)，即求最大值的最小值。

另外有关梯度 \(\nabla f(x^*)\) 与 \(\nabla g(x^*)\) 的方向问题，根据目标函数求极大值还是极小值，以及约束条件是小于还是大于等情况不同，结论也是不同的。

\(\min_x\ f(x)\)	\(g(x)\leq0\)	梯度 \(\nabla f(x^*)\) 与 \(\nabla g(x^*)\) 的方向相反	\(\lambda\geq0\)
\(\min_x\ f(x)\)	\(g(x)\geq0\)	梯度 \(\nabla f(x^*)\) 与 \(\nabla g(x^*)\) 的方向相同	\(\lambda\leq0\)
\(\max_x\ f(x)\)	\(g(x)\leq0\)	梯度 \(\nabla f(x^*)\) 与 \(\nabla g(x^*)\) 的方向相同	\(\lambda\leq0\)
\(\max_x\ f(x)\)	\(g(x)\geq0\)	梯度 \(\nabla f(x^*)\) 与 \(\nabla g(x^*)\) 的方向相反	\(\lambda\geq0\)