2 拉格朗日对偶（Lagrange duality） 先抛开上面的二次规划问题，先来看看存在等式约束的极值问题求法，比如下面的最优化问 题： 目标函数是 f(w)，下面是等式约束。通常解法是引入拉格朗日算子，这里使用 来表示算子， 得到拉格朗日公式为 L 是等式约束的个数。 然后分别对 w 和 求偏导，使得偏导数等于 0，然后解出 w 和 。至于为什么引入拉格朗日 算子可以求出极值，原因是 f(w)的 dw 变化方向受其他不等式的约束，dw 的变化方向与 f(w)的梯度垂直时才能获得极值，而且在极值处，f(w)的梯度与其他等式梯度的线性组合 平行，因此他们之间存在线性关系。（参考《最优化与 KKT 条件》） 然后我们探讨有不等式约束的极值问题求法，问题如下： 我们定义一般化的拉格朗日公式 这里的 和 都是拉格朗日算子。如果按这个公式求解，会出现问题，因为我们求解的是最 小值，而这里的 已经不是 0 了，我们可以将 调整成很大的正值，来使最后的函数结 果是负无穷。因此我们需要排除这种情况，我们定义下面的函数： 

这里的 P 代表 primal。假设 或者 ，那么我们总是可以调整 和 来使得 有最大值为正无穷。而只有 g 和 h 满足约束时， 为 f(w)。这个函数的精妙之处 在于 ，而且求极大值。 因此我们可以写作 这样我们原来要求的 min f(w)可以转换成求 了。 我们使用 来表示 。如果直接求解，首先面对的是两个参数，而 也是不等式 约束，然后再在 w 上求最小值。这个过程不容易做，那么怎么办呢？ 我们先考虑另外一个问题 D 的意思是对偶， 将问题转化为先求拉格朗日关于 w 的最小值，将 和 看作是 固定值。之后在 求最大值的话： 这个问题是原问题的对偶问题，相对于原问题只是更换了 min 和 max 的顺序，而一般更换 顺序的结果是 Max Min(X) <= MinMax(X)。然而在这里两者相等。用 来表示对偶问题 如下： 下面解释在什么条件下两者会等价。假设 f 和 g 都是凸函数，h 是仿射的（affine， ）。并且存在 w 使得对于所有的 i， 。在这种假设下，一定存在 使得 是原问题的解， 是对偶问题的解。 

还有 另外， 满足库恩-塔克条件 （Karush-Kuhn-Tucker, KKT condition），该条件如下： 所以如果 满足了库恩-塔克条件，那么他们就是原问题和对偶问题的解。让我们再 次审视公式（5），这个条件称作是 KKT dual complementarity 条件。这个条件隐含了 如果 ，那么 。也就是说， 时，w 处于可行域的边界上，这时才 是起作用的约束。而其他位于可行域内部（ 的）点都是不起作用的约束，其 。 这个 KKT 双重补足条件会用来解释支持向量和 SMO 的收敛测试。 这部分内容思路比较凌乱，还需要先研究下《非线性规划》中的约束极值问题，再回头看看。 KKT 的总体思想是将极值会在可行域边界上取得，也就是不等式为 0 或等式约束里取得， 而最优下降方向一般是这些等式的线性组合，其中每个元素要么是不等式为 0 的约束，要 么是等式约束。对于在可行域边界内的点，对最优解不起作用，因此前面的系数为 0。