> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/lihang-tongjixuexifangfa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/lihang-tongjixuexifangfa/7/8.md).

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

原始问题：

$$
\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）就是原始问题的对偶问题