支持向量机（Support Vector Machines SVM）是一种二分类模型，它的目标是在特征空间中寻找对于所有样本距离最大的超平面。与感知机不同的是，在线性可分的情况下，SVM可以得到唯一的解。
假设训练集样本为：$T= \{(x_{1},y_{1}),(x_{2},y_{2}), … ,(x_{N},y_{N}) \}$，其中$x_{i}$ $ \in $ $\mathbb R^{n}$表示样本的属性，$y_{i}$ $\in$ $ \{ +1, -1\}$表示样本的标签，$i=1,2,…,N$。
设SVM所求的超平面为$w \cdot x + b = 0$ 其中$w \in \mathbb R^{n}$，$b \in \mathbb R$，定义某个样本点$(x_{i}, y_{i})$到超平面$w \cdot x + b = 0$的距离为：
$$d_{i} = \frac{y_{i}(w \cdot x_{i} + b)}{\parallel w \parallel}$$
令$d = \min d_{i} $， $i=1,2,…,N$,则SVM的目标函数为：
$$\begin{cases}
\ \max \qquad d \\\
\ s.t. \qquad \frac{y_{i}(w \cdot x_{i} + b)}{\parallel w \parallel} \geq d \qquad i=1,2,…,N \end{cases}$$
令$ d = \frac{\hat d} {\parallel w \parallel}$，则上式可化为：
$$\begin{cases}
\ \max \qquad \frac{\hat d} {\parallel w \parallel} \\\
\ s.t. \qquad y_{i}(w \cdot x_{i} + b) \geq \hat d \qquad i=1,2,…,N \end{cases}$$
由于超平面$w \cdot x + b = 0$可以对其参数进行任意大小的缩放，即对于任意的标量$\lambda$，都有$\lambda(w \cdot x)$ $ + \lambda b = 0$，$\hat d$为一个标量，它的大小对于最终的参数求解并无影响，因此可以令$\hat d = 1$。并且$\max \frac{1}{\parallel w \parallel}$等价于$\min \frac{1}{2}\parallel w \parallel^{2}$。因此上式等价为：
$$\begin{cases}
\ \min \qquad \frac{1} {2}\parallel w\parallel^{2} \\\
\ s.t. \qquad y_{i}(w \cdot x_{i} + b) \geq 1 \qquad i=1,2,…,N \end{cases} \qquad (1)$$
接下来可以通过拉格朗日对偶性，求解该问题的对偶问题，从而得到原始问题的最优解。引入拉格朗日因子$\lambda _ {i} \geq 0, i=1,2,…,N$，则拉格朗日函数为：
$$L(w,b,\lambda) = \frac{1} {2}\parallel w\parallel^{2} + \sum_{i=1}^{N} \lambda _ {i}(1-y_{i}(w \cdot x_{i} + b)) \qquad (2)$$
由于$\lambda _ {i} ( 1-y_{i}(w \cdot x_{i} + b)) \leq 0, i=1,2,…,N$，因此 $$\frac{1} {2}\parallel w \parallel^{2} \geq L(w,b,\lambda)，等号成立的条件为：\sum_{i=1}^{N} \lambda _ {i}(1-y_{i}(w \cdot x_{i} + b)) = 0 \qquad (3)$$
所以(1)可以等价为：
$$\min\limits_{w,b} \max\limits_{\lambda} L(w,b,\lambda) \qquad (4) $$
根据拉格朗日对偶性，上述等式的对偶问题是极大极小问题：
$$\max\limits_{\lambda} \min\limits_{w,b} L(w,b,\lambda) \qquad (5)$$
对于上式，先求解$\min\limits_{w,b} L(w,b,\lambda)$.首先对其关于$w$与$b$分别求偏导，并令其为0：
$$\frac{\partial L}{\partial w} = w - \sum_{i=1}^{N} \lambda_{i}y_{i}x_{i}=0 \qquad \frac{\partial L}{\partial b} = - \sum_{i=1}^{N}\lambda_{i}y_{i}=0$$
则：
$$w = \sum_{i=1}^{N} \lambda_{i}y_{i}x_{i} \qquad \sum_{i=1}^{N}\lambda_{i}y_{i}=0 \qquad (6)$$
将上述结果带入到拉格朗日函数可得：
$$L(w,b,\lambda) = - \frac{1}{2} \sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_{i}\lambda_{j}y_{i}y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^{N} \lambda _{i} \qquad (7)$$
则(5)可以化为：
$$\begin{cases}
\ \max \qquad - \frac{1}{2} \sum_{i=1}^{N}\sum_{j=1}^{N}\lambda_{i}\lambda_{j}y_{i}y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^{N} \lambda _{i} \\\\\\
\ s.t.\qquad \sum_{i=1}^{N}\lambda_{i}y_{i}=0 ,\qquad\lambda_{i} \geq 0 \qquad i=1,2,…,N \end{cases} \qquad (8)$$
通过上式可以求出原始问题的对偶优化问题，求解该问题可以借用序列最小化算法（Sequential minimal optimization SMO）。使用对偶问题求解带来的一大好处是：在求解中只使用了原始样本属性的内积形式$x_{i} \cdot x_{j}$，这为之后引入核函数提供了很大的便利。
另外考虑(3)中的等号成立的条件，由此可知：
$$\begin{cases}
\ 当 y_{i}(w \cdot x_{i} + b) > 1 时，\lambda_{i} = 0\\\
\ 当 y_{i}(w \cdot x_{i} + b) = 1 时，\lambda_{i} \geq 0 \end{cases} \qquad (9)$$
因此只有样本$i$满足：$y_{i}(w \cdot x_{i} + b) = 1$时，该样本对于最终的结果才会有影响。这些样本处于边界位置，被称为__支持向量__。
通过(8)可以解出$\lambda_{i}(i=1,2,…,N)$的值，然后将其带入(6)中，可以解出参数$w$的解。另外当$\lambda_{j} > 0$时，对应的样本点为支持向量，该点满足条件：$y_{j}(w \cdot x_{j} + b) = 1$。将参数$w$的解带入该条件中，可以得出参数$b$的解。因此最终的解形式为：
$$\begin{cases}
\ w = \sum_{i=1}^{N} \lambda_{i}y_{i}x_{i}\\\\\
\ b = y_{j} - \sum_{i=1}^{N} \lambda_{i}y_{i}(x_{i} \cdot x_{j}) \qquad \lambda_{j} > 0 \end{cases} \qquad (10)$$
1.参考文档：
[1]. 统计学习方法 李航 著