凸二次规划问题推导

线性可分支持向量机的策略是求得一个几何间隔最大的分离超平面，用数学语言表示以下约束最优化问题：

$$\begin{aligned} \max_{w,b} \quad \gamma \\ s.t. \quad y_i(\frac {w}{||w||} \cdot x_i + \frac{b}{||w||}) \ge \gamma, i = 1,2,\cdots,N && {1} \end{aligned}$$

考虑到几何间隔和函数间隔的关系$\text{几何间隔}\gamma = \frac {\text{函数间隔} \hat \gamma}{||w||}$，则约束最优化问题为：

$$\begin{aligned} max_{w,b} \quad \frac {\hat \gamma}{||w||} \\ s.t. \quad y_i(w \cdot x_i + b) \ge \gamma_i, i = 1,2,\cdots,N && {2} \end{aligned}$$

在公式（2）中，函数间隔$\hat \gamma$的取值不影响最优化问题的解，因此令$\hat \gamma = 1$，则约束最优化问题为：

$$\begin{aligned} max_{w,b} \quad \frac {1}{||w||} \\ s.t. \quad y_i(w \cdot x_i + b) \ge 1, i = 1,2,\cdots,N && {3} \end{aligned}$$

由于最大化$\frac {1}{||w||}$和最小化$\frac{1}{2}||w||^2$是等价的，则约束最优化问题为：

$$\begin{aligned} min_{w,b} \quad \frac {1}{2}||w||^2 \\ s.t. \quad y_i(w \cdot x_i + b)-1 \ge 0, i = 1,2,\cdots,N && {4} \end{aligned}$$

这是一个凸二次规划问题，使用凸二次规划问题求解，结果用于算法线性可分SVM