# 凸二次规划问题推导

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

$$
\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}
$$

这是一个[凸二次规划问题](https://windmising.gitbook.io/mathematics-basic-for-ml/gao-deng-shu-xue/convex)，使用[凸二次规划问题求解](https://windmising.gitbook.io/lihang-tongjixuexifangfa/svm/5)，结果用于算法[线性可分SVM](https://windmising.gitbook.io/lihang-tongjixuexifangfa/svm/2)
