SVM 通过最大化间隔实现分类，支持硬间隔、软间隔和核方法三种策略。

问题分类与策略

约束优化基础

原问题：

$$\min_x f(x) \quad s.t. \quad m_i(x) \le 0, \quad n_j(x) = 0$$

Lagrange 函数：

$$L(x, \lambda, \eta) = f(x) + \sum_i \lambda_i m_i(x) + \sum_j \eta_j n_j(x)$$

对偶关系：$\max_{\lambda,\eta}\min_x L \le \min_x\max_{\lambda,\eta} L$

凸优化满足 Slater 条件时强对偶成立，KKT 条件为充要条件：

1. 可行域：$m_i(x^) \le 0, \quad n_j(x^) = 0, \quad \lambda^* \ge 0$
2. 互补松弛：$\lambda^* m_i(x^*) = 0$
3. 梯度为零：$\nabla_x L(x^, \lambda^, \eta^*) = 0$

Hard-margin SVM

最大化间隔：

$$\mathop{argmin}_{w,b} \frac{1}{2}w^Tw \quad s.t. \quad y_i(w^Tx_i+b) \ge 1$$

对偶问题：

$$\max_\lambda -\frac{1}{2}\sum_{i,j}\lambda_i\lambda_j y_i y_j x_i^T x_j + \sum_i \lambda_i \quad s.t. \quad \lambda_i \ge 0$$

KKT 条件给出解：

$$\hat{w} = \sum_{i=1}^N \lambda_i y_i x_i, \quad \hat{b} = y_k - w^Tx_k$$

仅支撑向量（$\lambda_i > 0$）参与决策边界构建。

Soft-margin SVM

引入松弛变量处理不可分数据：

$$\mathop{argmin}{w,b} \frac{1}{2}w^Tw + C\sum{i=1}^N \xi_i \quad s.t. \quad y_i(w^Tx_i+b) \ge 1-\xi_i, \quad \xi_i \ge 0$$

损失等价于 Hinge 函数：$\max{0, 1-y_i(w^Tx_i+b)}$

Kernel Method

通过特征变换 $\phi(x)$ 将数据映射到高维空间。核函数直接计算变换后的内积：

$$k(x, x’) = \phi(x)^T\phi(x’)$$

正定核条件：对称性 + Gram 矩阵半正定。

常用核函数如高斯核：$k(x,x’) = \exp(-\frac{|x-x’|^2}{2\sigma^2})$