凸二次规划问题求解

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

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

将原始问题转换为对偶最优化问题（推导过程）：

$$\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*$（推导过程）

通过$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$$

分类决策函数（推导过程）：

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