前言

在SVM中有一个求极小值的问题转换过程，转换为一个对偶问题，但是我不太清楚这个问题为什么可以转换，而且还不太清楚为什么这么转换？不太明确转换后有什么优点，写个文章来了解这些内容。

原始问题转换

$\min \quad \frac{1}{2} ||w||^2 \\ s.t. \quad y_i(x_i+b) >=1 \qquad \text{i=1,2...,n}$
拉格朗日乘子之后的公式为：
$F(w,b,a)= \frac{1}{2} ||w||^2+\sum_{i=1}^{n}a_{i}[1-y_i(wx_i+b)] \\ s.t. \quad a_i>=0$
优化问题为：
$\min \quad F(w,b,a)= \frac{1}{2} ||w||^2+\sum_{i=1}^{n}a_{i}[1-y_i(wx_i+b)]$

• 有一个疑惑，为什么是$1-y_i(wx_i+b)<=0$?

我们假设有一个最优解$w^*$，则得到最小值$f(w^*)= \frac{1}{2} ||w^*||^2$，则会发现一些：
$\min \quad F(w^*,b,a)<= f(w^*)$
最优解$w^*$，使得$1-y_i(wx^*+b)<=0$，则$\sum_{i=1}^{n}a_{i}[1-y_i(w^*x_i+b)]<=0$，这里$a_i>=0$，所以上述公式必然成立，但一般我们会把问题假设为如下所示：
$\max_{a_i>0} \quad F(w,b,a)= \frac{1}{2} ||w||^2+\sum_{i=1}^{n}a_{i}[1-y_i(wx_i+b)]$

因为有这种考虑：

• 满足约束条件$1-y_i(wx_i+b)<=0$，要想使得$\max \limits_{a_i>0} \quad F(w,b,a)= \frac{1}{2} ||w||^2$，则$a_i=0$
• 不满足约束条件，$1-y_i(wx_i+b)>0$，则$\max \limits_{a_i>0} \quad F(w,b,a)$可以是无穷大，也就无解了

我比较奇怪就是为什么要$\max \limits_{a_i}$，而不是$\min \limits_{a_i}$？我觉得如果是求最小值，则有：

• 满足约束条件$1-y_i(wx_i+b)<=0$，要想使得$\min \limits_{a_i>0} \quad F(w,b,a) \to -\infty$，则$a_i \to +\infty$，无解
• 不满足约束条件，$1-y_i(wx_i+b)>0$，则$\min \limits_{a_i>0} \quad F(w,b,a)= \frac{1}{2} ||w||^2$，则$a_i =0$

似乎$\max \limits_{a_i}$、$\min \limits_{a_i}$效果是一样的，这只是我个人的理解，没有数学理论的支持，感兴趣的朋友可以自己去了解一下背后的数学知识。不过从另一个角度来分析：逼近。可能会有一些结果，从上面的一个公式来继续分析：
$\min \quad F(w^*,b,a)<= f(w^*)$
该公式说明存在满足约束条件的$w^*$，那这样$F(w^*,b,a)$只能去逼近这个$f(w^*)$，所以是求$F(w^*,b,a)$的最大值，也就是：
$\min_{w_i} \max_{a_i>0} \quad F(w,b,a)$

先分析$\max_{a_i>0} \quad F(w,b,a)$，得到的结果是逼近$\frac{1}{2} ||w||^2$，然后再通过$\min_{w_i}\frac{1}{2} ||w||^2$从而达到目的。我们最终的公式为：
$\min_{w_i} \max_{a_i>0} \quad F(w,b,a)= \frac{1}{2} ||w||^2+\sum_{i=1}^{n}a_{i}[1-y_i(wx_i+b)]$
$\max$可以使得我们得到最接近$\frac{1}{2} ||w||^2$的$F(w,b,a)$，然后再求$\min \frac{1}{2} ||w||^2$，很多博客里称$\quad \min \limits_x \max \limits_{a_i>0} F(w,b,a)$为原始问题，接下来就是求解该原始问题的对偶问题。

对偶问题

于是我们可以转换问题为$min-max$问题：
$\min_{w} \max_{a_i>0} \quad \frac{1}{2} ||w||^2+\sum_{i=1}^{n}a_{i}[1-y_i(wx_i+b)]$

对偶问题就是将min与max位置互换，为什么可以互换？确实是可以互换的，但是不太清楚原理，先直接放定理：若原始问题和对偶问题都有最优值，则对偶问题最优值$d^∗$小于或等于原始问题最优值$p^∗$。公式表示就是如下：
$d^*=\min_{w}\max_{a_i}F(w,b,a_i) <= \max_{a_I}\min_{w}F(w,b,a_i) =p^*$
其实我是非常想学习这个对偶问题的转换，其相关知识涉及最优化理论、运筹学等数学知识，需要时间去研读。不过就这个问题继续转换，就是得到原问题的对偶问题，这中间的转换主要是：

• $\min_{w}F(w,b,a_i)$ 对w、b求偏导，偏导等于零，求极值，得到：
  $w=\sum_{i}a_iy_ix_i \\ \sum_{i}ay=0$

• 将w、b结果代入到原公式中得到：
  $max_{a_i>0}-\frac{1}{2}\sum_{i} \sum_{j}a_{i}a_{j}y_{i}y_{j}(x_i * x_j) + \sum_{i}a_i \\ s.t. \sum_i a_iy_i =0 \\ a_i>=0$
  在对这个函数求解，求解方法有SMO方法，也可以通过求极值方法，假设我们得到了$a$的值，然后再通过

$w=\sum_{i}a_iy_ix_i$
求解b 稍微复杂些，根据$y=wx+b$求的：
$b = y_j-\sum_{i}a_iy_i(x_i*x_j)$
这里$y_j$是支持向量的点，并不是所有样本数据集，是$a_j>0$的点，而且也不是只有一个，应该有多个，最后求解平均值作为b的值。

转换为对偶问题的优点

• 对偶问题往往更易于求解
• 自然引入核函数，推广到非线性分类问题的求解

总结

对偶问题还是比较难理解，本文没有去分析其原理，而且本文是基于一个min问题来看到对偶问题，如果是一个max问题，它的对偶问题如何，其实也是一样的，思想是换成了求上限，对上限求min，逼近真实值，大家可以看下参考博客的知乎，Cyber的回答，这篇文章会继续完善。

参考博客

深入理解SVM之对偶问题
如何通俗地讲解对偶问题？尤其是拉格朗日对偶lagrangian duality？