KKT 条件

一、问题重述

KKT 条件的其中一种等价表述形式是：

\[\begin{aligned}\max_{x}\ \ \ &f(x)\\ s.t.\ \ \ h_j(x) &= 0,j=1,2,\cdots,q\\ g_i(x)&\le 0,i=1,2,\cdots,p \end{aligned}\]

KKT 条件宣称，如果有一个 \(x^{*}\) 是满足所有约束条件的极值点，则

\[\begin{aligned}\nabla f(x^*) &= \sum_j\lambda_j\nabla h_j(x^*)+\sum_i\mu_i\nabla g_i(x^*)\\ \lambda_j&\in\mathbb{R},\mu_i \ge 0,\mu_ig_i(x^*) = 0 \end{aligned}\]

简单说，就是在极值点处，\(f\) 的梯度是一系列等式约束 \(h_j\) 的梯度和不等式约束 \(g_i\) 的梯度的线性组合。其中，等式约束梯度的权值 \(\lambda_j\) 没有要求；不等式约束梯度的权值 \(\mu_i\) 是非负的。并且，如果某个 \(g_i(x^*)\) 严格小于 0 ，那么它的梯度不会出现在加权式中，因为此时 \(\mu_i\) 必须等于 0 . 换句话说，只有 \(x^*\) 恰好在边界 \(g_i=0\) 上的那些 \(g_i\) 的梯度才会出现在加权式中。

可以看出，KKT 条件可视为 Lagrange 乘子法的推广。

二、理解思路

对于一个优化问题，可行域是满足所有约束条件的 \(n\) 维空间区域。对于可行域中的任意一点 \(x\) ，朝着 \(v\) 方向行走一点点，倘若还在可行域中，或者偏离可行域的量是行进距离的无穷小量，则称 \(v\) 为 \(x\) 的一个可行方向。我们用 \(F(x)\) 表示 \(x\) 的所有可行方向。

如果 \(x^*\) 是一个满足所有约束条件的极值点，那么无论朝哪个可行方向走，\(f\) 的值都不会增大。换句话说，在 \(x^*\) ，让 \(f\) 增大的方向不在 \(F(x^*)\) 中。

这句话的精确表述，即为 KKT 条件。

三、几何思路

n 维空间中，\(f(x) = 0\) 构成了一个曲面，专业术语叫流形。这个曲面是 n-1 维的，因为自变量的 n 个分量只满足一个方程。

Warning

接下来，我们默认“曲面是光滑的”。

在曲面上的每一个点 \(x\)，都有一个梯度方向 \(\nabla f(x)\)，从而得到两个函数值增加/减少的方向：

\[\begin{aligned} N_f^{+} &= \{\lambda \nabla f(x),\lambda \ge 0\}\\ N_f^{-} &= \{\lambda \nabla f(x),\lambda \le 0\}\\ N_f &= N_f^{+} \bigcup N_f^{-} \end{aligned}\]

这里的 \(N_f\) 是由梯度方向张成的一维子空间，过 \(x\) 可以做一个与 \(N_f\) 正交的 n-1 维切空间，即切平面 \(T_f\) 。

从而，在曲面 \(f(x) = 0\) 的一点 \(x\) 周围，我们把空间分成了三部分：

\[N_f^{+}+N_f^{-}+T_f = \mathbb{R}^{n}\]

子空间的“和”“直和”

子空间 \(U,W\) 的和定义为 \(U+W = \{u+w,u\in U,w\in W\}\) 。如果 \(U,W\) 的交集是空集，那么称其为“直和”。

值得注意的是，“和”与“并集”不是一个概念。举个例子，三维空间中，一条直线与一个不共面的平面，和是整个三维空间，但并集仅仅是该直线和平面上的所有点。

接下来，我们考察满足不同约束的点的可行方向。

对于等式约束 \(h(x) = 0\) ，可行解 \(x\) 必然在曲面上，也就是说它只能在曲面上移动。由于曲面是光滑的，所以它的可行方向是切平面方向，我们用 \(T_h\) 表示。这是一个 n-1 维的切空间。

对于不等式约束 \(g(x) < 0\) ，可行解 \(x\) 必然在曲面外面，在曲面的其中一侧，它无论朝哪个方向行进一小步，都不会到曲面上来甚至穿越曲面。所以，它的可行方向是 \(\mathbb{R}^n\) 。

对于不等式约束 \(g(x) \le 0\) （考虑可行解 \(x\) 在边界上的情况，我们称之为“起作用的不等式约束”），\(x\) 要么在曲面上移动，要么往 \(g < 0\) 的一侧跑，所以其可行方向是 \(N_g^{-}+T_g\) 。这是一个 n 维的半空间。

总结：假设一个点满足约束，可行方向是这样一些方向，在这些方向上移动一点点，点仍然近似满足约束。对于等式约束，可行方向是切空间；对于不等式约束，点在边界上，可行方向是半空间，点不在边界上，可行方向是全空间。

显然地，对于多个不同约束，其可行方向是每个约束的可行方向的交集。

四、KKT 条件的证明

在上文我们提到，KKT 条件就是“在 \(x^*\) ，让 \(f\) 增大的方向不在 \(F(x^*)\) 中”的严格表述。

我们知道，让 \(f\) 增大的方向，就是与 \(\nabla f(x^*)\) 成锐角的方向。因此，上面那句话可以用数学语言表述为

\[\forall u\in F(x^*),u\cdot \nabla f(x^*)\le 0\]

接下来，我们看看可行方向 \(F(x^*)\) 中具体包含哪些方向 \(u\) 。

对于等式约束 \(h_j(x^*)=0\) ，\(x^*\) 的可行方向是切平面方向 \(T_{h_j} = \{u|u\cdot\nabla h_j(x^*) = 0, u\in \mathbb{R}^n\}\) 。

对于起作用的不等式约束 \(g_i(x^*) \le 0\)，可行方向是 \(N_{g_i}^{-}+T_{g_i} = \{u|u\cdot\nabla g_i(x^*) \le 0, u\in\mathbb{R}^n\}\) 。

对于不起作用的不等式约束 \(g_i(x^*) \le 0\)，可行方向是 \(\mathbb{R}^n\) 。

最终的可行方向集合是上述方向的交集，即：

\[\begin{aligned} F(x^*) &= T_{h1}\bigcap T_{h_2}\bigcap\cdots\bigcap T_{h_q}\bigcap\left(N_{g_1}^{-}+T_{g_1}\right)\bigcap\left(N_{g_2}^{-}+T_{g_2}\right)\bigcap\cdots\bigcap\left(N_{g_p}^{-}+T_{g_p}\right)\bigcap\mathbb{R}^n\cdots\\ &= T_{h1}\bigcap T_{h_2}\bigcap\cdots\bigcap T_{h_q}\bigcap\left(N_{g_1}^{-}+T_{g_1}\right)\bigcap\left(N_{g_2}^{-}+T_{g_2}\right)\bigcap\cdots\bigcap\left(N_{g_p}^{-}+T_{g_p}\right)\\ &= \left\{u|\begin{aligned}u\cdot\nabla h_j(x^*)&=0,j=1,2,\cdots,q\\ u\cdot\nabla g_i(x^*) &\le 0,i =1,2,\cdots,p 且 g_i(x^*) = 0\\ u\in\mathbb{R}^n\end{aligned}\right\} \end{aligned}\]

上文要求，\(\forall u\in F(x^*),u\cdot \nabla f(x^*)\le 0\) ，不难看出

\[\begin{aligned}\nabla f(x^*) &= \sum_j\lambda_j\nabla h_j(x^*)+\sum_i\mu_i\nabla g_i(x^*)\\ \lambda_j&\in\mathbb{R},\mu_i \ge 0,\mu_ig_i(x^*) = 0 \end{aligned}\]

是满足要求的一个形式。Farkas 引理证明了该形式是唯一的，但我们这里就不再讨论了。

五、适用条件

KKT 条件成立有一个至关重要的前提：约束品性（Constraint Qualification, CQ）。它的存在，是为了保证极值点 \(x^∗\) 附近的约束交集是一个形态正常的“光滑流形”。

最常见的 CQ 被称为线性无关约束品性（LICQ）：即在极值点 \(x^∗\) 处，所有等式约束和起作用的不等式约束的梯度必须线性无关。换言之，由它们构成的雅可比矩阵必须满秩：

\[J = \begin{bmatrix}\nabla h_1(x^*)^\top\\ \vdots\\ \nabla h_q(x^*)^\top\\ \nabla g_1(x^*)^\top\\ \vdots\\ \nabla g_k(x^*)^\top \end{bmatrix}\]

以三维空间中的两个曲面 \(h_1=0\) 和 \(g_2=0\) 为例，我们可以直观地看到满秩的意义：

如果 \(\nabla h_1(x^∗)\) 与 \(\nabla g_2(x^*)\) 线性无关（不共线），代表两曲面干脆利落地“横截相交”。在这种正常情况下，两个切平面的交线就是真实曲面交线的切线，代数方程算出的结果属于可行方向集合 \(F(x^*)\)

相反，如果它们线性相关（共线），切平面重叠，说明两曲面相切了，此时交集退化成只有 \(x^*\) 这唯一的孤立点。一旦如此，可行方向集合 \(F(x^*)\) 就不复存在（为空集），代数推导出的方向成了空中楼阁，整个 KKT 条件的几何基石也就彻底崩塌了。