算法
$\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) 构造并求解约束最优化问题
\[\begin{aligned}&\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\\ &\alpha_i \ge 0,\quad i=1,2,\cdots,N\end{aligned}\]求得最优解 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)^T$ .
$\qquad$ (2) 计算
\[w^*=\sum_{i=1}^N\alpha_i^*y_ix_i\]并选择 $\alpha^*$ 的一个正分量 $\alpha_j^* \gt 0$，计算
\[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^*)\]导出思路
通过原始算法的最优化问题，构造拉格朗日函数：
\[L(w,b,\alpha)=\frac 1 2\|w\|^2-\sum_{i=1}^N \alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i,\quad \alpha_i \ge 0\]对偶问题为极大极小问题：
\[\max_\alpha\min_{w,b}L(w,b,\alpha)\](1) 求 $\min_{w,b}L(w,b,\alpha)$
\[\left. \begin{array}{l} \ \nabla_wL(w,b,\alpha)=0\\ \ \nabla_bL(w,b,\alpha)=0 \end{array} \right\} \Rightarrow \left\{ \begin{array}{l} \ w=\sum_{i=1}^N\alpha_iy_ix_i\\ \ \sum_{i=1}^N\alpha_iy_i=0 \end{array} \right.\] \[\Rightarrow\min_{w,b}L(w,b,\alpha)=-\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\](2)求$\min_{w,b}L(w,b,\alpha)$对 $\alpha$ 的极大，并将极大转换为极小，最终得到最优化问题：
\[\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\\ &\alpha_i \ge 0,\quad i=1,2,\cdots,N\end{align}\]$b^*$ 由 KKT 条件得出 .
