基于拉格朗日乘子法与 KKT 条件的 SVM 数学推导

1. 引言

上一篇文章中，我们通过数学推导，将 SVM 模型转化为了一个有不等式约束的最优化问题。 SVM 数学描述的推导

这看上去是一个非线性规划的复杂问题，在《高等数学》中，我们已经学习过这类问题如何来求解。 — KKT 条件，本文我们就来详细了解一下 KKT 的推导过程。

2. 有等式约束的最优化问题 — 拉格朗日乘子法

我们首先需要了解如何处理一个有等式约束的最优化问题。

2.1. 问题描述

下图展示了直角坐标系内目标函数 z = f(x, y) 的几何曲面（粉色），以及 φ(x, y) = 0 的约束曲面（蓝色）

我们将三维曲面映射到二维直角坐标系中的等高线画出来。

我们要找的就是红色曲线与高度最大等高线的交点，那么如何找到这个点就是我们要解决的问题。

2.2. 公式推导

3. 有不等式约束的最优化问题 — KKT 条件

当约束加上不等式之后，情况变得更加复杂起来。

此时，极值点 (x0, y0) 有两种可能：

1. (x0, y0) 在 g(x) < 0 的区域内
2. (x0, y0) 在 g(x) = 0 的边界上

3.1. 极值点在约束条件区域内

下图展示了 (x0, y0) 在 g(x) < 0 的区域内的情况：

无论是两图中的那种情况，最优化问题的极值点就是 f(x, y) 的极值点，也就是说约束条件失去了作用，此时我们只需要通过求导法则就可以得到 z=f(x, y) 的极值点。 计算出来 f(x, y) 的极值点后，带入约束条件，如果满足则求解成功，否则说明极值点在约束条件边界上。

3.2. 极值点在约束条件边界上

在这种情况下，我们成功将不等式约束的优化问题转化为了有等式约束的优化问题，根据上面我们推导出的拉格朗日乘子法就可以计算出极值点。 (x0, y0) 的取值，以及拉格朗日乘子 λ 的值。

4. SVM 数学描述推导

于是，问题转换成为：

5. 参考资料

同济大学《高等数学》第七版。 https://blog.csdn.net/the_lastest/article/details/78136692。 http://www.cnblogs.com/ooon/p/5721119.html。 https://www.cnblogs.com/ooon/p/5723725.html。