机器学习导论（附录）–拉格朗日对偶与KKT条件

4,804次阅读

共计 2811 个字符，预计需要花费 8 分钟才能阅读完成。

首先是拉格朗日原问题(强调强调强调，一会我们还会回来看这里的，这里我们将原问题记为p∗)：

min f 0 (x)

s . t . f i (x) \leq 0, i = 1, \dots, m

h i (x) = 0, i = 1, \dots, p

注意：这里我们要求fi 和hi的定义域都是非空的，此时的定义域记为D，但是这里我们并不要求原问题是凸的

拉格朗日对偶的中心思想是在目标函数中考虑上约束条件，也就是引入拉格朗日算子，得到增广目标函数，也就是拉格朗日函数

L (x, λ, μ) = f 0 (x) + \sum i = 0 m λ i f i (x) + \sum i = 1 p μ i h i (x)

也就是说，我们现在优化的对象除了x，还加上了m个λi，p个μi，这时候定义域变成了D×Rm×Rp

我们定义拉格朗日函数的对偶函数为

g (λ, μ) = inf x \in D L (x, λ, μ) = inf x \in D f 0 (x) + \sum i = 0 m λ i f i (x) + \sum i = 1 p μ i h i (x)

也就是说，我们定义对偶函数为拉格朗日函数的下界，那么问题来了，如果拉格朗日函数没有下界呢？没关系，这时候我们就让对偶函数为−∞即可。

由于对偶函数g(λ,μ)是关于(λ,μ)仿射函数的逐点下确界，所以
不管原问题是不是凸的，其对偶函数一定凹的
（参考前面的讨论，注意前面讨论的是凸性，但是凸性与凹性换几个地方就行了）

引入对偶，使得原问题的求解变成了讨论“求原问题的下界”。为什么呢？因为对于λ≥0，都有g(λ,μ)≤p∗，简单验证一下：
如果一个x^是可行的解，那么fi(x^)≤0,hi(x^)=0，由于λ≥0，从而

\sum i = 0 m λ i f i (x) + \sum i = 1 p μ i h i (x)

第一项为负数，第二项为0，所以

L (x^, λ, μ) = f 0 (x^) + \sum i = 0 m λ i f i (x^) + \sum i = 1 p μ i h i (x^) \leq f 0 (x^)

因而

g (λ, μ) = inf x \in D L (x, λ, μ) \leq L (x^, λ, μ) \leq f 0 (x^)

即每个可行点，都有g(λ,μ)≤f0(x^)

上面的公式好枯燥，给大家看一张图就明白了

在图中，实线代表的是目标函数f0，而虚线代表的是约束条件f1，彩色的点线代表λ取不同值的时候对应的拉格朗日函数L(x,λ)=f0(x)+λf1(x)（本来有十条的，但是最近撸太多手抖实在画不动了………画5条大家也能看的懂吧….），我们可以看到，在约束条件可行(f1(x)≤0)的区间内，拉格朗日函数都是小于目标函数的。我们可以看到，在可行区间内，目标函数的最值将在x = -0.46处取得p∗=1.54

下面我们来看一看对偶函数的图像：

其中实线代表的是对偶函数，而虚线代表的是目标函数f0的最优值p∗=1.54，从图像中，我们可以发现，对偶函数确实是原问题的一个下界，此外，我们也可以发现：在原问题中，目标函数f0，约束条件f1都不是凸的，但对偶函数是凹的

为了更好地理解，我们再举一个例子，一个优化问题：

min x T x

s . t . A x = b

这个问题是等式约束，很简单，我们用高数上面的知识就可以解决了，我们取拉格朗日函数

L (x, μ) = x T x + μ T (A x - b)

然后求导，令其为0

Δ x L (x, μ) = 2 x + A T μ = 0

求得

x = - 1 2 A T μ

这时候目标函数最小，好，现在我们来看看如果讨论对偶会怎么样
首先对偶函数为

g (μ) = inf x L (x, μ)

代入最优解x=−12ATμ

g (μ) = inf x L (- 1 2 A T μ, μ) = - 1 4 μ T A A T μ - b T μ

我们会发现，对偶函数是二次凹函数，并且有

- 1 4 μ T A A T μ - b T μ \leq inf {x T x | A x = b}

拉格朗日对偶，通过引入参数λ,μ，可以让原问题得到一个与λ,μ相关的下界（这时候跟x没什么关系了）。但现在的问题就是，究竟哪个下界才是最好的？因为下界有很多个，所以应该选取哪个下界？
答案是：最大的下界是最好的，这个解我们记为d∗

从上面的图，大家也可以看到，对偶函数的最大值最接近原问题的最优解，由于对偶问题总存在这么一个等式d∗≤p∗（即使原问题不是凸的这个不等式也成立），所以，p∗−d∗也被称为最优对偶间隙

举一个对偶的例子，比如线性规划，其标准式为

min C T x

s . t . A x = b

x \geq 0

我们取拉格朗日函数

L (x, λ, μ) = C T x - \sum i = 1 n λ i x i + μ T (A x - b) = - b T μ + (C + A T μ - λ) T x

则对偶函数为

g (λ, μ) = inf x L (x, λ, μ) = - b T μ + inf x (C + A T μ - λ) T x

由于线性函数只有为常数的时候才有下界，所以g(λ,μ)又可以写为

g (λ, μ) = - b T μ, 如果 A T μ - λ + c = 0

g (λ, μ) = - \infty, 其他

强烈抗议：没法进行公式堆叠啊！！！！！！！！！

上面是对偶函数，我们说过，对偶函数刻画的是一个下界，哪个下界是最好的呢？最大的是最好的，所以，对偶问题可以表述为maxg(λ,μ)
也就是

max - b T μ

s . t . A T μ - λ + c = 0

λ \geq 0

上面这个问题还可以进一步缩写为

max - b T μ

s . t . A T μ + c \geq 0

这就是线性规划标准形式的对偶问题，这种表述也称之为不等式形式线性规划

好，我们我们从不等式形式线性规划出发，也就是现在我们的原问题是：

max C T x

s . t . A T x \leq b

（注：跟上边的不等式形式符号变了，但表达没变）

我们取拉格朗日函数

L (x, λ) = C T x + λ T (A x - b) = - b T λ + (A T λ + C) T x

那么对偶函数就是

g (λ) = inf x L (x, λ) = - b T λ + inf x (A T λ + C) T x

同样，由于线性函数只有恒为常数的时候才有下界，因此对偶函数可以写为

g (λ) = - b T λ, 如果 A T λ + c = 0

g (λ) = - \infty, 其他

强烈抗议：没法进行公式堆叠啊！！！！！！！！！
还是那句话，哪个下界是最好的呢？最大的是最好的，所以maxg(λ)可以表述为

max - b T λ

s . t . A T λ + c = 0

λ \geq 0

你看，这又回到标准型的线性规划了。

在拉格朗日对偶之后，d∗≤p∗总是成立的，这个我们也叫做弱对偶性，如果说我们能够使得d∗=p∗，那么这时候我们求解对偶问题就相当于求解原问题了，大家看前面的图，对偶问题显然不等价于原问题的。那么什么时候对偶问题等价于原问题呢（这种情况叫做强对偶）？一般情况下，如果原问题是凸的，那么这个问题具有强对偶，也就是对偶问题的最优解等于原问题的最优解（不绝对，也有例外的）。

如何判定一个问题是否具有强对偶性呢？一个判据是Slater条件，这里不讲，另一个就是大家所知到的KKT条件了。如果说一个问题，它满足KKT条件，那么这个问题就具有强对偶性，求取对偶问题就相当于求取原问题。但如果不满足KKT条件呢？那就不能这么做了。

而恰好，SVM问题里面都是满足KKT条件的，所以SVM里面求取对偶解就相当于求取原问题的解。那么我们为什么要求它的对偶呢？因为kernel，通过对偶之后得到一个向量内积的形式，也就是xTx这种形式，而这种形式是kernel所擅长处理的。如果没有对偶，就没有后面的kernel映射，SVM也实现不了非线性分割。

正文完

请博主喝杯咖啡吧！