# 凸二次规划问题求解

要求解的带约束最优化问题为：

$$
\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   && {1}
\end{aligned}
$$

将原始问题转换为对偶最优化问题（[推导过程](https://windmising.gitbook.io/lihang-tongjixuexifangfa/svm/6)）：

$$
\begin{aligned}
\min_a \quad \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^Na_ia_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^na_i   \\
s.t. \quad \sum_{i=1}^Na_iy_i = 0 \\
 \quad a_i \ge 0, i = 1,2,\cdots, N && {2}
 \end{aligned}
$$

通过公式（2）求解$$a*$$（[推导过程](5)）

通过$$a*$$求出$$w*$$和$$b*$$：

$$
\begin{aligned}
w* = \sum_{i=1}^Na_i^*y_ix_i  \\
b* = y_j - \sum_{i=1}^Na_i^*y_i(x_i \cdot x_j)  && {3}
\end{aligned}
$$

通过公式（3）得到：\
分离超平面：

$$
\sum_{i=1}^Na_i^*y_i(x\cdot x_i) + b^* = 0
$$

分类决策函数（[推导过程](5)）：

$$
f(x) = sign(\sum_{i=1}^Na_i^*y_i(x\cdot x_i) + b^*)
$$
