算法
$\qquad$ 输入：线性可分训练集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$，其中 $x_i\in \Bbb R^n,y_i\in\{-1,+1\}$
$\qquad$ 输出：分离超平面和分类决策函数
$\qquad$ (1) 选择惩罚参数 $\color{red}{C\gt 0}$，构造并求解凸二次规划问题
\[\begin{align}&\min_\alpha \quad\frac 1 2 \sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N \alpha_i\\ &\text {s.t.}\qquad \sum_{i=1}^N\alpha_iy_i=0\\ &\color{red}{0 \le\alpha_i\le C },\quad i=1,2,\cdots,N\end{align}\]求得最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)^T$ .
$\qquad$ (2) 计算
\[w^*=\sum_{i=1}^N\alpha_i^*y_ix_i\]并选择 $\alpha^*$ 的一个分量 $\color{red}{0\lt\alpha_j^* \lt C}$，计算
\[b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)\]$\qquad$ (3) 求得分离超平面
\[w^*\cdot x+b^*=0\]分类决策函数：
\[f(x)=\text {sign}(w^*\cdot x+b^*)\]导出思路
原始问题为：
\[\begin{align}\min_{w,b,\xi}\quad &\frac 1 2\|w\|^2+C\sum_{i=1}^N\xi_i\\ \text{s.t.} \quad &y_i(w\cdot x_i+b)\ge 1-\xi_i,\quad i=1,2,\cdots,N\\ &\xi_i \ge 0,\quad i=1,2,\cdots,N\end{align}\]拉格朗日函数是
\[L(w,b,\xi,\alpha,\mu)\equiv \frac 1 2 \|w\|^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\alpha_i(y_i(w\cdot x_i+b)-1+\xi_i)-\sum_{i=1}^N\mu_i\xi_i\]其中，$\alpha_i\ge 0$，$\mu_i \ge 0$
后续步骤和线性可分支持向量机对偶算法导出思路相似。
一点说明
$b$ 的解不唯一，所以实际计算时可以取在所有符合条件的样本点上的平均值。
