非线性优化中的 KKT 条件该如何理解？ 第1页

普通本科数学教材中都会介绍Lagrange乘子法，用于求解带等式约束的极值问题，KKT条件是拉格朗日乘子法的推广，由于表述比较繁琐，知名度较低。也许是因为出现在SVM模型的推导中，机器学习研究者倒是对其有所耳闻。

然而，KKT条件是一个具有很强几何意义的结论，下面我们将给出这样一个“直观”、优美的解释。

一、问题重述

KKT条件有几个不同的等价表述方式，我们只讨论其中一种，其他表述可以类似地推得。给定优化问题：

也就是说，自变量 是一个n维向量，要最大化一个目标函数 ，满足若干等式和不等式约束。KKT条件宣称，如果有一个点 是满足所有约束的极值点，则

简单说，就是在极值点处， 的梯度是一系列等式约束 的梯度和不等式约束 的梯度的线性组合。在这个线性组合中，等式约束梯度的权值 没有要求；不等式约束梯度的权值 是非负的，并且如果某个 严格小于0，那这个约束不会出现在加权式中，因为对应的权值 必须为0。换句话说，只有 恰好在边界 上的那些 的梯度才会出现在加权式中。如果去掉不等式约束的部分，那么上式就是拉格朗日乘子法的精确表述。

二、理解思路

给定一个优化问题，我们把满足所有约束条件的n维空间区域称为可行域。从可行域中的每一个点 朝某个方向 出发走一点点，如果还在可行域中，或者偏离可行域的程度很小，准确地说，偏移量是行进距离的高阶无穷小量，那么我们就说 是一个可行方向。我们用 表示点 的所有可行方向的集合 。

对于可行域中的一个极大值点 ，它的可行方向集合为 ，从 朝 中的某个方向走一小步，那么落点仍然（近似）在可行域中。 是局部最大值点就意味着在这些可行方向上目标函数 不能增大，从而我们得到下面这样一个结论：

在极值点 ，让目标函数增大的方向不能在 中。

把这句话精确表达出来，就得到了KKT条件的数学表述。

三、单约束的可行方向

满足等式 的点 ，在n维空间里构成了一个(通常是光滑的)曲面，专业称谓叫流形。这个曲面是n-1维的，因为自变量的n个分量只满足一个方程，因而曲面上有n-1个自由度。例如在二维空间里 是一条一维的直线，在三维空间中 是一张二维曲面。

在这些曲面上每一点 都存在一个梯度方向 ，沿着这个方向函数值 增大，沿着它的逆方向 函数值减小，这两个方向我们记为

是两条射线的并，是由梯度方向张成的一维子空间。与这个一维子空间正交的n-1一维空间，被称为切空间或者切平面 ，自变量在 中的方向上移动时，函数值 变化不大。我们都知道对于光滑的曲面，如果把它在一点 上无限放大，最终会近似成为平面，这个平面就是 。（如果你不明白这段在说什么，请拖到最下方看注1。）下图是一个例子：

从而，在曲面 上一点 周围，我们把空间分成了三部分：

下面来看看等式约束和不等式约束的可行方向，也就是这样一些方向，朝它们移动一点，约束依然近似满足。

1 如果点 满足等式约束 ，那么在切平面方向 上滑动，这个等式约束依然近似满足，所以可行方向为 。

2 如果点 满足不等式约束 ，说明它在 曲面 的某一侧，并且不在边界上，所以无论朝哪个方向跑，它仍然满足约束 ，可行方向为 。

3 如果点 满足 ，因为约束条件是 ， 可以朝切平面 中的方向滑动，保持在 上，也可以往 的负梯度方向 跑，让 值减小，不等式约束依然成立。但是不能往正梯度方向跑，因为会造成 ，违背不等式约束。所以可行方向是 ，这是n维空间的一半，或者n-1维子空间与一条垂直于它的射线的并。

三种情况我们总结在下表中：

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

四、多约束的可行方向

上面我们讨论了一个约束的情况，假如有两个约束或者多个约束，那么这些约束的交集就是更低维的“曲面”。比如在三维空间中，两张曲面的交集是一维曲线。对于这些“交集”上的点，或者同时满足多个约束的点，我们仍然可以讨论它的可行方向：让这些点朝可行方向移动，能够近似满足所有条件。仔细琢磨不难发现：

满足多个约束的点的可行方向是每个约束的可行方向的交集。

为了便于理解，我们举两个例子：

例1：两个等式约束 和 是三维空间中的二维曲面，二者的交是一维曲线（下图中蓝白相间的部分），考虑曲线上的一个点 ，这一点作为曲线上的一点，切空间是一维的，也就是曲线的切线，而这条切线恰好是两个等式约束的切平面的交。

例2：等式约束 是下图右边的球面，不等式约束 是左边绿色球面外面的空间区域，同时满足二者的可行域是右边球面露在左边球面外面的部分（红白相间的部分）。为保持两个约束仍然满足，点 既可以在两球面交线上滑动 ，也可以朝右边球面上移动 ，所以可行方向是下图右边那半块玻璃。同时，可行方向也是 的可行方向、平面 （下图中右边那块平面玻璃）和 在边界上的可行方向、半空间 （下图中左面那块平面玻璃靠上的所有区域）的交集。

五、KKT条件的证明

我们在第二小节中说过，KKT条件等价于在极值点 ，目标函数增大的方向不能在可行方向 中，可行方向是指 朝它移动一点点，仍然满足约束条件的方向。

目标函数增大的方向是 ，这就意味着

或者

就是说， 在 中不能有分量，或者说投影是0，这个式子等价于：

我们下面把所有约束分为三部分：

1 等式约束 ，可行方向是 ;

2 不等式约束， ， 在边界上， ，可行方向是 ;

3 不等式约束， ， 不在边界上， ，可行方向是 。

那么同时满足所有有约束的点的可行方向就是所有这些可行方向的交集：

第三部分直接消失了，从而在KKT表达等式中不会出现不在边界上的不等式约束。再利用集合的德摩根公式可得：

整理一下，得：

这就是KKT条件。

注1：方向的线性结构

在上面的论述中我们使用了定义在方向上的线性结构，这里详细解释一下。

大家都知道曲线和曲面生活在欧几里德空间。欧式空间是这样一种空间，其上定义了内积运算，从而可以测量长度、角度，并且这些几何量与人们的日常直觉吻合。笛卡尔建立了直角坐标系，从而我们可以在欧式空间上建立线性结构，让它等价（同构）于 。

“方向”这个术语并不单独存在，它依附于一个点，从一个点出发的方向才有意义。因为在我们的问题中这个点固定在某个极值点 ，起始点可以被省略，我们直接说某个方向。所有这些方向又构成了一个线性空间 ，这就好像如果你把坐标原点移到 ，那么从 出发的一个向量 可以带我们去 的任意一处。

假设有两个（从 出发的）方向的集合 和 ，我们可以定义它们的并集是 ，举一个简单的例子，假设在 中， 是与x轴平行的所有方向，那么

，

是三维线性空间的一个一维子空间。 是yz平面上的所有方向，那么

，是一个二维子空间。因为二者的并集是全空间：

又因为二者交集只有0元素，

或者 ，

我们说二者互为补集或者

。

推广一下就是说，如果一维直线 不在n-1维平面

上，那么它们的并集是全空间，但是二者不一定互为补集。当一维子空间恰好由n-1维平面的法线方向张成时，二者互补。