对偶问题的理解

1. 为什么要使用对偶问题（SVM）

1. 对偶问题将原始问题中的约束转为了对偶问题中的等式约束

2. 方便核函数的引入

3. 改变了问题的复杂度。由求特征向量w转化为求比例系数a，在原始问题下，求解的复杂度与样本的维度有关，即w的维度。在对偶问题下，只与样本数量有关。

---

2. 寻找最优值的下界

我们首先要引入包含不等式约束的优化问题，标准形式如下：

$$\begin{array}{ccccc}\min \quad & f(x)\\{\rm{s}}{\rm{.t}}{\rm{.}}\quad & {h_i} = 0,\quad i = 1,...,m\\ & {g_j} \le 0,\quad j = 1,...,n\end{array} \quad\quad\quad(1)$$

$f(x)$是目标函数，而后面分别是一系列的不等式约束和等式约束。

我们首先明确几个概念：

• 可行点（可行解）：所有满足约束的点x。
• 可行域：所有可行点组成的点集，记为R。正式写出来就是：

$$R = \left\{ {x|{h_i}(x) = 0,{g_j}(x) \le 0} \right\}$$

• 最优点（最优解）：满足约束（也就是处于可行域之内）并且使目标函数达到最小的点，记为$x^*$。
• 最优值：如果找到了$x^*$，$p^* = f(x^*)$ 就是最优值。

明确了这些概念以后我们就接着说下面的内容了。

与等式约束的情况类似，我们定义拉格朗日函数如下：

$$L(x,{\boldsymbol{\lambda }},{\boldsymbol{\mu }}) = f(x) + \sum\limits_{i = 1}^m {{\lambda _i}{h_i}(x) + \sum\limits_{j = 1}^n {{\mu _j}{g_j}(x)} }$$

在这里需要强调的是，所有的${\mu}_i$必须是大于等于0的（也即是不等式约束对应的乘子要求大于等于0，我们记为$\boldsymbol{\mu }$≥0，意思是每个都${\mu}_i$≥0）。

接下来我们定义拉格郎日对偶函数（the Lagrange dual function）如下：

$$\Gamma (\boldsymbol\lambda ,\boldsymbol\mu ) = \mathop {\inf }\limits_x L(x,\boldsymbol\lambda ,\boldsymbol\mu ) = \mathop {\inf }\limits_x \left( f(x) + \sum\limits_{i = 1}^m {{\lambda _i}{h_i}(x) + \sum\limits_{j = 1}^n {{\mu _j}{g_j}(x)} } \right)\quad\quad\quad(2)$$

所以拉格朗日对偶函数$\Gamma (\boldsymbol\lambda ,\boldsymbol\mu )$就是把$L(x,\boldsymbol\lambda ,\boldsymbol\mu )$看成$x$的函数所找到的最小值。找到这个最小值有什么意义呢？

我们先把结论写下来，这个结论十分重要，是本次论述的目的：

对偶函数$\Gamma (\boldsymbol\lambda ,\boldsymbol\mu )$产生了原问题（1）最优值$p^*$的一个下界，也就是说，对于任意的$\lambda$≥0和任意的$\mu$来说，有：

$$\Gamma (\boldsymbol\lambda ,\boldsymbol\mu )\le {p^*} \quad\quad\quad(3)$$

这个结论显而易见！但是我们还是来证明一下：

$$\begin{array}{l}\Gamma (\boldsymbol\lambda ,\boldsymbol\mu ) = \mathop {\inf }\limits_x L(x,\boldsymbol\lambda ,\boldsymbol\mu )\\ \le f({x^*}) + \sum\limits_{i = 1}^m {{\lambda _i}{h_i}({x^*}) + \sum\limits_{j = 1}^m {{\mu _j}{g_j}({x^*})} } \\ \le f({x^*}) = {p^*}\end{array}$$

最后两行的推导是考虑到$x^*$是在可行域R内的，所以有（1）中的约束条件，并且有$\mu≥0$

要理解这个不等式$\Gamma (\boldsymbol\lambda ,\boldsymbol\mu )\le {p^*}$有两个直观的解释：

解释一：线性逼近的解释

解释二：交换max和min的次序

这两个解释说明了一个问题，就是不等式（3）是怎么来的（具体见原文）。

总结如下：

如果我们把拉格朗日函数看做是x的函数，然后取下确界（注意：是在整个定义域里取下确界，而不是仅仅在可行域里取值，也就是说取下确界时对x是没有约束的），那么得到的结果就是原优化问题（1）的最优值的一个下界。

---

3. 对偶问题

回忆上一节，对如下的原问题：

$$\begin{array}{ccccc}\min \quad & f(x)\\{\rm{s}}{\rm{.t}}{\rm{.}}\quad & {h_i} = 0,\quad i = 1,...,m\\ & {g_j} \le 0,\quad j = 1,...,n\end{array} \quad\quad\quad(1)$$

我们定义了拉格朗日对偶函数：

$$\Gamma (\boldsymbol\lambda ,\boldsymbol\mu ) = \mathop {\inf }\limits_x L(x,\boldsymbol\lambda ,\boldsymbol\mu ) = \mathop {\inf }\limits_x \left( f(x) + \sum\limits_{i = 1}^m {{\lambda _i}{h_i}(x) + \sum\limits_{j = 1}^n {{\mu _j}{g_j}(x)} } \right)\quad\quad\quad(2)$$

然后我们证明了：$\Gamma (\boldsymbol\lambda ,\boldsymbol\mu )\le {p^*}$，其中$p^*$是原问题的最优值。

也就是说我们找到了原问题最优值的一个下界。既然我们找到了一个下界，显然我们要找到它最好的下界。什么是最好的下界的？显然就是所有下界当中最大的那一个。所以我们要把最大化，当然我们还要记得我们需要限制。我们把要优化的函数和约束条件正式写下来就是：

$$\begin{array}{ccccc}\mathop {\max }\limits_{\boldsymbol\lambda ,\boldsymbol\mu } \quad & \Gamma (\boldsymbol\lambda ,\boldsymbol\mu )\\s.t.\quad & \boldsymbol\mu \ge 0\end{array}\quad\quad\quad(4)$$

与原问题（1）相对应，我们把上面的问题（4）称作拉格朗日对偶问题（Lagrange dual problem）。显然，对偶问题的最优值$d^*$就是我们可以获得的$p^*$的最优下界，也就是所有下界中离$p^*$最近的一个，它们的关系是：

$${d^*} \le {p^*}$$

我们把这个不等式叫做弱对偶性质（Weak Duality）。

顺其自然，我们可以引出一个重要的概念，对偶间隙，其定义为${d^*} - {p^*}$，用文字叙述就是原问题的最优值与通过拉个郎日对偶函数获得的其最好（最大）的下界之差。由不等式（4）可以看出，对偶间隙肯定是大于等于0的。

那么有没有可能在某种情况下，对偶间隙消失了呢？也就是说对偶问题的最优值与原问题的最优值相等了呢？

我们将要叙述一下Slater条件：

Slater条件：

$f(x)$和$g_j(x)$均为凸函数，$h_i(x)$为仿射函数，则存在$x$满足：

$$\begin{array}{l}{h_i}(x) = 0\\{g_j}(x) < 0\end{array}$$

Slater条件即是说存在$x$，使不等式约束中的“小于等于号”要严格取到“小于号”。

此时

$${d^*} = {p^*}$$
这种情况称为强对偶性质（Strong Duality）。

下面的问题是，如果对偶间隙消失了，会发生什么有趣的现象呢？

如果对偶间隙消失了，也就是说，如果对偶问题存在着最优点$λ^*$,$μ^*$并且使其对应的最优值等于$p^*$.
这样我们就可以$λ^*$,$μ^*$推出我们要优化的$x^*$.

---

第一节转自狂徒归来
第二三节转自王国龙_成长
参考周志华《机器学习》