算法
$\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} & \quad\min_{w,b} \frac{1}{2} \|w\|^2 \\ & \quad\text{s.t.}\quad y_i(w_i\cdot x_i+b)-1\ge 0,\quad i=1,2,\cdots,N \end{aligned}\]求解最优解 $w^*，b^*$ .
$\qquad$ (2) 由此得到分离超平面：
\[w^*\cdot x+b^*=0\]分类决策函数
\[f(x)=\text{sign}(w^*\cdot x+b^*)\]导出思路
求得一个几何间隔最大的分离超平面，即为约束最优化问题：
\[\begin{align}&\max_{w,b}\quad\gamma\\&\text{s.t.}\quad y_i\left(\frac w{\|w\|}\cdot x_i+\frac b{\|w\|}\right)\ge \gamma,\quad i=1,2,\cdots,N\end{align}\]考虑到函数间隔和几何间隔的关系，最优化问题改写为
\[\begin{align}&\max_{w,b}\quad\frac{\hat\gamma}{\|w\|}\\ &\text{s.t.}\quad y_i\left(w\cdot x_i+ b\right)\ge \hat\gamma,\quad i=1,2,\cdots,N\end{align}\]函数间隔 $\hat\gamma$ 并不影响最优化问题的解，取 $\hat\gamma=1$，并注意到最大化 $\frac 1 {||w||}$ 和最小化 $\frac 1 2||w||^2$ 等价，所以最优化问题变为
\[\begin{align} & \quad\min_{w,b} \frac{1}{2} \|w\|^2 \\ & \quad\text{s.t.}\quad y_i(w_i\cdot x_i+b)-1\ge 0,\quad i=1,2,\cdots,N \end{align}\]一点说明
函数间隔
\[\hat\gamma=\min_{i=1,\cdots,N}\hat\gamma_i=y_i(w\cdot x_i+b)\]几何间隔
\[\gamma=\min_{i=1,\cdots,N}\gamma_i=\frac {y_i(w\cdot x_i+b)}{\|w\|}\]
