原始问题转换为对偶最优化问题

原始问题为：

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

公式（1）到公式（2）的推导过程

1. 定义拉格朗日函数

   $$\begin{aligned} L(w, b, a) = \frac {1}{2}||w||^2 - \sum_{i=1}^Na_i(y_i(w \cdot x_i + b)-1) \\ = \frac {1}{2}||w||^2 - \sum_{i=1}^Na_iy_i(w \cdot x_i) - b\sum_{i=1}^Na_iy_i + \sum_{i=1}^Na_i && {3} \end{aligned}$$
2. L(w, b, a)分别对w，b求偏导，并令偏导为0

   $$\begin{aligned} \nabla_wL(w, b, a) = w - \sum_{i=1}^Na_iy_ix_i = 0 \\ \nabla_bL(w, b, a) =\sum_{i=1}^Na_iy_i = 0 && {4} \end{aligned}$$
3. 公式（4）解得以下等式：

   $$\begin{aligned} w = \sum_{i=1}^Na_iy_ix_i \\ \sum_{i=1}^Na_iy_i = 0 && {5} \end{aligned}$$
4. 公式（5）代入公式（3）得：

   $$\begin{aligned} L(w, b, a) = \frac {1}{2}||w||^2 - \sum_{i=1}^Na_iy_i(w \cdot x_i) - b\sum_{i=1}^Na_iy_i + \sum_{i=1}^Na_i \\ = \frac {1}{2}(w\cdot w) - (w\cdot w) + \sum_{i=1}^Na_i \\ = -\frac {1}{2}(w\cdot w) + \sum_{i=1}^Na_i \\ = -\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 && {6} \end{aligned}$$

   【？】把公式（5）代入公式（3）展开推导的方式没有推出来

5. 公式（6）就是原始问题的对偶函数$\Psi(w, b, a)$。 根据对偶问题的求解步骤，此时要求对偶函数$\Psi(w, b, a)$。

6. 将最大化问题转化为最小化问题，得到公式（2）