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

原始问题为：

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