对于一个线性分类问题，有数据$Data = {x_i,y_i}_{i=1}^{N},x_i \in R^p,y_i\in {+1,-1}$, 即有N个数据样本需要分类，每个样本$x_i$为$p$维向量，$y_i$取值为 $+1 \text{or}-1$

上一节将支持向量机模型转化为如下凸二次规划问题

$$ \begin{equation}\begin{aligned}&\min {b, w} ;;;\frac{1}{2} w^{T} w\&\text { s.t. } \quad 1-y{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \leq 0 ,n=1,2,…,N\end{aligned}\end{equation} $$

通常，当$N,p$比较小的时候，可以直接交给库函数来求解。但是当$N$很大或者引入核方法后，可能会导数样本维度为巨大甚至为无穷大，此时可以通过拉格朗日乘子法引入其对偶问题来求解。

通过求解对偶问题得到原始问题的最优解，就是支持向量机的对偶算法。采用对偶算法，有优点：

• 对偶问题一般更容易求解
• 自然引入核函数，进而推广到非线性分类问题。

原优化问题的对偶问题

首先构造其拉格朗日函数，为此，对每一个不等式约束引入拉格朗日乘子$a_i ≥ 0$, I = 1,2,..,N, 拉格朗日函数如下：

$$ \begin{equation}L(w, b, \alpha)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \alpha_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right), i = 1,2,…,N\end{equation} $$

这时，原优化问题就等价于如下无约束问题：

$$ \begin{equation}\begin{aligned}&\min _{w, b} \max {\alpha} L(w, b, \alpha) \&\text { s.t. };;; \alpha{i} \geq 0, ;;i=1,2, \ldots, N\end{aligned}\end{equation} $$

原问题和以上无约束问题为什么等价？理解如下（逻辑理解，非数理证明）

上述无约束问题（P）的对偶问题（D）为如下极大极小问题：

$$ \begin{equation}\begin{aligned} &\max _{\alpha}\min {w, b} L(w, b, \alpha) \&\text { s.t. };;; \alpha{i} \geq 0, ;;i=1,2, \ldots, N\end{aligned}\end{equation} $$

所以，为了得到对偶问题的解，需要先对$L(w,b,\alpha)$对$w,b$求极小，再求对$\alpha$的极大。

1. 求$\min_{w,b}L(w,b,\alpha)$ 将拉格朗日函数$L(w,b,\alpha)$分别对$w,b$求偏导并令其为0。 先对$L(w,b,\alpha)$进行化解，如下： $$ \begin{align*}L(w, b, \alpha)&=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \alpha_{i}\left(1-y_{i}\left(w^{T} x_{i}+b\right)\right) \ &=\frac 1 2 w^Tw + \sum_{i=1}^N\alpha i - \sum{i=1}^N\alpha iy_iw^Tx_i - \sum{i=1}^N\alpha iy_i b\end{align*} $$ 对$w,b$求偏导如下： $$ \begin{align*} & \frac{\partial L(w,b,\alpha)}{\partial b} = -\sum{i=1}^N\alpha_i y_i \[5bp] &\frac{\partial L(w,b,\alpha)}{\partial w} = w-\sum_{i=1}^N \alpha_i y_i x_i \end{align*} $$ 令偏导为0,则有 $$ \begin{align} &\sum_{i=1}^N\alpha_i y_i=0 \[5bp] &w=\sum_{i=1}^N \alpha_i y_i x_i \end{align} $$ 将求得的w（式(4)）带入拉格朗日函数（式$(2)$）,并利用式(5)，可得 $$ \begin{equation*}\begin{aligned}L(w, b, \alpha) &=\frac{1}{2} \sum_{i-1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} y_{i}\left(\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j}\right) \cdot x_{i}+b\right)+\sum_{i=1}^{N} \alpha_{i} \&=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)+\sum_{i=1}^{N} \alpha_{i}\end{aligned}\end{equation*} $$ 即 $$ \begin{equation*}L\left(w, b, \lambda_{i}\right)=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \lambda_{i} \lambda_{j} y_{i} y_{j} x_{i}^{T} x_{j}+\sum_{i=1}^{N} \alpha_{i}\end{equation*} $$
2. 求$\min_{w,b}L(w,b,\alpha)$对$\alpha$的极大，即对偶问题 $$ \begin{equation}\begin{split} \max_{\alpha}& ;;;\sum_{i=1}^{N} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} \ \text { s.t. }&;;; \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \ &;;; \alpha_{i} \geq 0, i=1,2, \ldots, N \end{split}\end{equation} $$ 将上式子的目标函数由求极大转换为求极小，就得到下面与之等价的对偶最优化问题 $$ \begin{equation}\begin{split} \min_{\alpha}& ;;;\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} -\sum_{i=1}^{N} \alpha_{i}\ \text { s.t. }&;;; \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \ &;;; \alpha_{i} \geq 0, i=1,2, \ldots, N \end{split}\end{equation} $$

考虑原始最优化问题 (1) (3) 和对偶优化问题（8)。原始优化问题与对偶问题为强对偶关系。所以存在$w^,b^,\alpha^$, 使得$w^,b^$是原问题的解，$\alpha^$为对偶问题的解。这意味着求解原始问题(1)(3)可以转换为求解对偶问题(8)。此外因为是强对偶关系，所以满足KKT条件（强对偶与KKT条件为充要关系）。

假设对偶问题最优化问题对$\alpha$的解为$\alpha ^$，那么可以由$\alpha ^$根据KKT条件求得原始最优化问题对$w,b$的解$w^, b^$如下，其中$x_k$为任意一边界上的数据点。

$$ \begin{align*}\hat{w}&=\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i} \ b^* &= y_{k}-\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}^{T} x_{k} \end{align*} $$

证明 KKT条件如下：

综上，分离超平面可写为：

$$ \begin{equation*} \sum_{i=1}^{N} \alpha_{i}^{} y_{i}\left(x \cdot x_{i}\right)+b^{}=0 \end{equation*} $$

分类决策函数可以写为：

$$ \begin{equation*}f(x)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i}^{} y_{i}\left(x \cdot x_{i}\right)+b^{}\right)\end{equation*} $$

分类决策函数只依赖于输入$x$ 和训练样本输入的内积

注可以发现，$w^,b^$ 均为输入数据的线性组合。

总结

对于给定的线性可分训练数据集，可以首先求其对偶问题的解$\alpha^$，再求得原始问题的解$w^, b^*$。从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法。

具体来看，SVM原始优化问题为凸二次规划问题，由拉格朗日对偶性将原始问题转为对偶问题，因为SVM原始优化问题为凸二次规划，所以原始问题与对偶问题满足强对偶关系，所以求得对偶问题的解即为原始问题的解。因为满足强对偶关系，进而满足kkt条件，所以求解对偶问题的时候，可以用$\alpha$ 求出 $w,b$。