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

原始问题：

$$\begin{aligned} \min_{w,b,\xi} \quad \frac{1}{2}||w||^2 + C \sum_{i=1}^N\xi_i && {1} \\ s.t. \quad y_i(w\cdot x_i+b)\ge 1-\xi_i \\ \quad \quad \xi_i \ge 0, i = 1,2,\cdots,N \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 \quad 0 \le a_i \le C, i=1,2,\cdots,N && {2} \end{aligned}$$

原始问题公式（1）到对偶问题公式（2）的推导过程

1. 将原始问题（1）稍加变形

   $$\begin{aligned} \min_{w,b,\xi} \quad \frac{1}{2}||w||^2 + C \sum_{i=1}^N\xi_i && {3} \\ s.t. \quad 1-\xi_i - y_i(w\cdot x_i+b) \le 0 \\ \quad \quad -\xi_i \le 0, i = 1,2,\cdots,N \end{aligned}$$
2. 写出拉格朗日函数

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

   $$\begin{aligned} \nabla_wL(w, b, \xi, a, \mu) = w - \sum_{i=1}^Na_iy_ix_i = 0 \\ \nabla_bL(w, b, \xi, a, \mu) = -\sum_{i=1}^Na_iy_i = 0 \\ \nabla_{\xi_i}L(w, b, \xi, a, \mu) = C - a_i - \mu_i = 0 && {5} \end{aligned}$$
4. 将等式（5）代入公式（4）得到对偶函数：

   $$\begin{aligned} L(w, b, \xi, a, \mu) = \frac{1}{2}||w||^2 + C \sum_{i=1}^N\xi_i + \sum_{i=1}^Na_i(1-\xi_i - y_i(w\cdot x_i+b)) - \sum_{i=1}^N\mu_i\xi_i \\ = \frac{1}{2}(w \cdot w) + \sum_{i=1}^N(C-a_i-\mu_i)\xi_i + \sum_{i=1}^Na_i - w \cdot w - b\sum_{i=1}^Na_iy_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. 公式(6)为对偶函数 公式（5）能得出以下限制条件：

   $$\begin{aligned} \sum_{i=1}^Na_iy_i=0 \\ 0 \le a_i \le C, i=1,2,\cdots,N && {7} \end{aligned}$$
6. 公式（6）结合公式（7）就是原始问题的对偶问题