【数学基础】KKT条件

继前面讲的拉格朗日乘子法。拉格朗日乘子法主要用于求解等式约束的问题，当约束加上不等式之后，情况变得更加复杂，首先来看一个简单的情况，给定如下不等式约束问题：

对应的 Lagrangian 与图形分别如下所示：

上面这段话可能描述的不够清楚。我总结一下。上图左表达的是，当我们要找的局部最优解（或者全局最优解）刚好就在约束条件的可行区域内部（这个时候最优解对应的是g(x)0，在等式约束中就没有这个限制。

看完这张图你可能会觉得这和我上面讲的不一样，但实际上是一样的。这一段不是在解释为什么为什么一定要大于0，而是在解释当取到最优解的时候，（用我上面的话来讲就是）最优点就落在，约束条件的圆心与目标函数的圆心相连直线与边界相交的那个点上。它是在解释为什么两者是平行的（线性相关的）。

其实按照我之前的理解来就好了，图中的梯度只画了一个目标函数的，容易搞混了，在红点处其实还有一个反方向的约束条件的梯度。

可见对于不等式约束，只要满足一定的条件，依然可以使用拉格朗日乘子法解决，这里的条件便是 KKT 条件。接下来给出形式化的 KKT 条件 首先给出形式化的不等式约束优化问题：

列出 Lagrangian 得到无约束优化问题：

经过之前的分析（算上拉格朗日乘子法处理等式约束那一篇文章的），便得知加上不等式约束后可行解 x（局部最优解或全局最优解，可能有多个，要代原式中判断） 需要满足的就是以下的 KKT 条件：

注意这边L只对x求偏导。

满足 KKT 条件后极小化 Lagrangian 即可得到在不等式约束条件下的可行解。 KKT 条件看起来很多，其实很好理解:

(1) ：拉格朗日取得可行解的必要条件；

(2) ：这就是以上分析的一个比较有意思的约束，称作松弛互补条件；

(3) ∼∼ (4) ：初始的约束条件；

(5) ：不等式约束的 Lagrange Multiplier 需满足的条件。

其实这边有个问题，约束函数一般是取到等号的，不然很有可能就无解了。

还有两个约束就是原本的不等式约束

用这6个等式联立方程组解出x，就好了。在例子原文中作者啰嗦了一大堆。但实际上就是这个道理。不过对于这种求解方程组的工作，会有一些更高效的方法去做。如SMO算法。以后有时间会再详细讲解的。

SVM 中的支持向量便是来自于此，需要注意的是 KKT 条件与对偶问题也有很大的联系，下一篇文章就是拉格朗日对偶。

从拉格朗日乘子法到KKT条件，讲了这么多，对于拉格朗日乘子或者在做什么似乎还没有明了的讲过。

拉格朗日乘子加入到目标函数中，有两个作用：

参考文章：

约束优化方法之拉格朗日乘子法与KKT条件

解密SVM系列（一）：关于拉格朗日乘子法和KKT条件