我们现在已经拿到支持向量机的目标函数，这是一个带有不等式约束的最小化问题。本章节，我们会从基础的 KKT 条件入手，讲解其解决带约束优化问题的核心逻辑，再推导原始问题如何转化为对偶问题，最后结合对偶系数的取值规则，弄懂支持向量的判定依据，完整梳理优化求解的核心原理。

1. KKT 条件

在很多优化问题中，我们希望找到一个变量，使目标函数最小，但是变量需要满足一些限制。比如下面的例子：

我们先直接看这个问题，如果没有约束，只需要求导令其等于 0，就可以求得 x=5。但是加入约束以后，就不能这么简单求解，因为要需要同时考虑：目标函数、约束条件。那我们应该怎么求解？我们可以利用数学工具 KKT 条件，其步骤是：

首先，使用拉格朗日乘子法，将目标函数和约束条件组合到一起，构造拉格朗日函数。
然后，利用 KKT 条件刻画原问题的最优解，并通过驻点条件消去原问题中的变量，得到对偶问题。
最后，求解对偶问题，再根据 KKT 条件反推出原问题的最优解。

第一步：使用拉格朗日乘子法，将目标函数和约束条件组合到一起，构造拉格朗日函数。

\(\lambda\) 称为拉格朗日乘子。

原始问题是一个 min 问题，现在变成了 min-max 问题。如果把它当做简单的 min 问题，那么：当满足约束时，可以通过无限增大 \(\lambda\) 来降低目标函数，使得约束条件变成了降低目标函数值的手段。所以，我们对内层进行 max，即：当解满足约束条件就停止，不作为降低目标函数值的手段。不满足约束条件时便施加无限惩罚，从而迫使外层优化搜寻符合约束的合理解。

第二步：利用 KKT 条件刻画原问题的最优解，并通过驻点条件消去原问题中的变量，得到对偶问题。

在有约束的优化问题中，最优解并不是随便取的，它必须同时满足 4 条规则，这就是 KKT 条件。理解了这四条规则，我们就能一步步把原问题转化为它的对偶问题。

接下来，我们利用第 4 点驻点条件，将原始关于 \(x\) 的问题，转换为关于 \(\lambda\) 的问题，这就是原问题的对偶问题，知道了 \(\lambda\) 就可以求出 \(x\) 。

我们将 \(x\) 代入到拉格朗日函数中，得到关于 \(\lambda\) 的函数，这就是原问题的对偶问题。数学上的对偶，是指一个优化问题可以转换为另一个与之对应的优化问题。两个问题描述的是同一个优化目标，但它们关注的变量和求解视角不同。

第三步：求解对偶问题，再根据 KKT 条件反推出原问题的最优解。

接下来，对 \(\lambda\) 求导令其等于 0，得到 \(\lambda = 4\)，由此得到 \(x = 3\)。将计算结果代入互补松弛条件中，4(3-3)=0，满足。

2. 对偶求解

支持向量机目标函数形式和前面的简单例子类似，只不过稍微复杂一些。我们仍然可以套用前面的解题思路。

第一步：使用拉格朗日乘子法，将目标函数和约束条件组合到一起，构造拉格朗日函数。

接下来，我们增加将目标和约束合成一个拉格朗日函数，把带约束的最小化问题，变成一个无约束的问题:

这里需要注意，原来优化的是 min 问题，现在则变成一个 min–max 问题？

在拉格朗日函数中，前两项对应的是原始优化目标，后两项对应的是约束条件。如果在引入拉格朗日函数之后，仍然把整个问题当作一个单纯的最小化问题来处理，就会出现一个严重的问题：为了使拉格朗日函数的值尽可能小，算法并不一定需要真正优化前两项的目标函数，而是可以通过操纵约束项来不断降低整体数值。

具体来说，当约束条件被满足时，对应的约束项是小于等于零的，同时拉格朗日乘子 α 又被限制为非负。在这种情况下，只要不断增大 α，就可以让拉格朗日函数的值持续下降，从而把“满足约束”错误地当成了一种可以用来降低目标函数的手段。

这显然违背了约束的初衷，因为约束的作用并不是参与优化打分，而只是用来区分解是否合法。正因为如此，约束条件不能被当作一个可以被无限优化的项，而必须被冻结在一个恰当的状态。为此，在拉格朗日函数中对拉格朗日乘子引入最大化（max）：当约束被满足时，最大化会使约束项达到其允许的最大值，从而不再对整体目标产生影响。

这样，max 负责通过调整拉格朗日乘子，使约束条件发挥本来的限制作用，而不是成为降低目标函数值的手段。min 负责调整模型参数 \(w、b、\xi\)，在满足约束条件的情况下优化原始目标函数，寻找最优分类超平面。

转换为拉格朗日函数后，优化问题的本质和原来的约束优化问题是等价的，原始目标函数的优化含义并没有改变。

第二步：利用 KKT 条件刻画原问题的最优解，并通过驻点条件消去原问题中的变量，得到对偶问题。

原问题是一个关于 \(w、b、\xi\) 的优化问题，我们现在使用 KKT 条件将问题转换为对偶问题，即：求解 \(\alpha_{i}\)，从而求解出 \(w、b、\xi\) 。

接下来，我们利用 KKT 条件的驻足条件，消去 \(w、b、\xi\)，得到只与 \(\alpha\) 有关的问题：

第三步：求解对偶问题，再根据 KKT 条件反推出原问题的最优解。

我们通过求解每个样本对应的拉格朗日乘子 \(\alpha_{i}\)，可以进一步得到超平面的关键参数 \(w\) 和 \(b\)。支持向量机的优化问题属于凸优化问题，理论上存在全局最优解。但是，由于需要同时优化大量样本对应的 \(\alpha_{i}\)，并且这些变量受到约束相互关联，因此实际求解的难点在于如何高效计算，实际中通常采用序列最小优化（SMO）等算法。我们这里就不介绍 SMO 算法了，假设求解之后得到每个样本对应的 \(\alpha_{i}\)，我们就可以得到决策函数。