线形支持向量机：给定线形不可分的数据集，求解如下的软间隔最大化问题：
$$
\min_{w, b, \xi} \frac{1}{2} ||w||^2 + C \sum\limits_{i=1}^N \xi_i
$$
$$
\mathbb{s.t. } y_i(w \cdot x_i + b) \ge 1 - \xi_i, i=1,2,\dots,N \\
\xi_i \ge 0, i =1,2,\dots,N
$$
得到分类超平面：
$$
w^0 \cdot x + b^0 = 0
$$
及相应的分类决策函数：
$$
f(x)=sign(w^0\cdot x+b^0)
$$
上述问题的对偶问题为：
$$
\min_\alpha \frac{1}{2} \sum\limits_{i=1}^{N} \sum\limits_{i=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum\limits_{i=1}^{N} \alpha_i \\
\mathbb{s.t.} \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\
0 \le \alpha_i \le C, i=1, \dots, N
$$
原始最优化问题的拉格朗日函数：
$$
L(w,b,\xi,\alpha,\mu)=\frac{1}{2}||w|^2 + C\sum\limits_{i=1}^{N}\xi_i - \sum\limits_{i=1}^{N}\alpha_i(y_i(w \cdot x_i + b)-1+\xi_i) - \sum\limits_{i=1}^{N}\mu_i \xi_i
$$
对偶问题是拉格朗日函数的极大极小问题。
求$L(w,b,\xi,\alpha,\mu)$的极小：
$$
\begin{cases}
\nabla_w L(w,b,\xi,\alpha,\mu) = w-\sum\limits_{i=1}^{N} \alpha_i y_i x_i &= 0 \\
\nabla_b L(w,b,\xi,\alpha,\mu) = -\sum\limits_{i=1}^{N} \alpha_i y_i &= 0 \\
\nabla_{\xi_i} L(w,b,\xi,\alpha,\mu) = C-\alpha_i-\mu_i &= 0
\end{cases}
$$
$$
\Rightarrow
$$
$$
\begin{cases}
w = \sum\limits_{i=1}^{N} \alpha_iy_ix_i \\
\sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\
C - \alpha_i - \mu_i = 0
\end{cases}
$$
于是：
$$
\min_{w,b,\xi} L(w,b,\xi,\alpha,\mu)=-\frac{1}{2}\sum\limits_{i=1}^{N} \sum\limits_{j=1}^{N} \alpha_j \alpha_i y_i y_j (x_i \cdot x_j) + \sum\limits_{i=1}^{N} \alpha_i
$$
$$
s.t. \sum\limits_{i=1}^{N} \alpha_i y_i = 0 \\
C - \alpha_i - \mu_i = 0 \\
\alpha_i \ge 0 \\
\mu_i \ge 0
$$
设$\alpha^0 = (\alpha_1^0, \dots, \alpha_N^0)^T$是对偶问题的一个解， 若存在$\alpha^0$的一个分量$\alpha_j^0$满足$0 \le \alpha_j^0 \le C$，则原始问题的解$w^0, b^0$为：
$$
w^0 = \sum\limits_{i=1}^{N} \alpha_i^0 y_i x_i
$$
$$
b^0 = y_j - \sum\limits_{i=1}^{N} y_i\alpha_i^0 (x_i \cdot x_j)
$$
此时的分离超平面：
$$
\sum\limits_{i=1}^{N} \alpha_i^0 y_i (x \cdot x_i) + b^0 = 0
$$
分类决策函数：
$$
f(x) = sign(\sum\limits_{i=1}^{N} \alpha_i^0 y_i (x \cdot x_i) + b^0)
$$
理论上$b^0$可不唯一，实际应用中往往只出现算法叙述的情况。
线形不可分的情况下，对偶问题的解$\alpha^0$中对应于$\alpha_j^0 \gt 0$的样本点$(x_j,y_j)$的实例$x_j$称为支持向量。
线形支持向量机最优化问题
$$
\min_{w,b,\xi} \frac{1}{2} ||w||^2 + C\sum\limits_{i=1}^{N} \xi_i \\
\mathbb{s.t.} y_i(w \cdot x_i + b) \ge 1- \xi_i, i=1,2,\cdots, N \\
\xi_i \ge 0, i = 1,2,\cdots,N
$$
等价于最优化问题：
$$
\min_{w,b} \sum\limits_{i=1}^{N} [1-y_i(w \cdot x_i + b)]_+ + \lambda ||w||^2
$$
目标函数：
$$
\sum\limits_{i=1}^{N} [1-y_i(w\cdot x_i + b)]_+ + \lambda ||w||^2
$$
$$L(y(w\cdot x+b))=[1-y(w\cdot x+b)]_+$$
称为合页损失函数，其中
$$
[z]_+ =
\begin{cases}
z, z \gt 0 \\
0, z \le 0
\end{cases}
$$