SVM 拉格朗日函数法求解 - 以(1; 1)，(1; 0)，(0; 1)为例

首先，根据 SVM 的目标函数形式，我们需要最小化$\frac{1}{2}|w|^2$，同时满足所有样本点的约束条件 $y_i(w^Tx_i+b) \geq 1$。

为了方便求解，我们可以把目标函数变形为最大化 $\frac{1}{2}|w|^2$ 的负数 $-\frac{1}{2}|w|^2$。

接下来，我们可以构建拉格朗日函数：

$$\ L(w,b,\alpha) = -\frac{1}{2}|w|^2 + \sum_{i=1}^m \alpha_i(1-y_i(w^Tx_i+b))\ $$

其中，$\alpha_i$ 是拉格朗日乘子，用于将约束条件引入目标函数中。

接下来，我们需要求解拉格朗日函数的偏导数，并令其等于 0，求解出 $w$、$b$ 和 $\alpha$ 的值。

$$\ \begin{aligned}\ \frac{\partial L}{\partial w} &= -w + \sum_{i=1}^m \alpha_i y_i x_i = 0 \ \frac{\partial L}{\partial b} &= \sum_{i=1}^m \alpha_i y_i = 0 \ \frac{\partial L}{\partial \alpha_i} &= 1 - y_i(w^Tx_i+b) = 0\ \end{aligned}\ $$

由第一个式子可知，

$$\ w = \sum_{i=1}^m \alpha_i y_i x_i\ $$

由第二个式子可知，

$$\ \sum_{i=1}^m \alpha_i y_i = 0\ $$

将 $w$ 带入拉格朗日函数中，得到

$$\ \begin{aligned}\ L(w,b,\alpha) &= -\frac{1}{2}|w|^2 + \sum_{i=1}^m \alpha_i(1-y_i(w^Tx_i+b)) \ &= -\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j y_i y_j x_i^Tx_j + \sum_{i=1}^m \alpha_i - \sum_{i=1}^m \alpha_i y_i b \ &= -\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j y_i y_j x_i^Tx_j + \sum_{i=1}^m \alpha_i\ \end{aligned}\ $$

因此，我们需要求解这个二次规划问题：

$$\ \begin{aligned}\ \min_{\alpha} \quad & \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j y_i y_j x_i^Tx_j - \sum_{i=1}^m \alpha_i \ s.t. \quad & \sum_{i=1}^m \alpha_i y_i = 0 \ & \alpha_i \geq 0, \quad i=1,2,\cdots,m\ \end{aligned}\ $$

解出 $\alpha$ 后，我们可以根据 $w=\sum_{i=1}^m \alpha_i y_i x_i$ 计算出 $w$ 的值。

接下来，我们需要找到支持向量。对于任意一个 $\alpha_i > 0$ 的样本点，它都是支持向量。因为只有支持向量对决策边界的位置有影响。

对于支持向量，我们可以利用它们的 $\alpha_i$ 和对应的 $y_i$ 值，计算出 $b$ 的值：

$$\ b = y_i - \sum_{j=1}^m \alpha_j y_j x_j^Tx_i\ $$

最终的 SVM 模型就是：

$$\ f(x) = \text{sign}(\sum_{i=1}^m \alpha_i y_i x_i^Tx+b)\ $$

其中，$\alpha_i$ 是通过求解二次规划问题得到的拉格朗日乘子。