博客 | 机器学习算法系列（二）：拉格朗日对偶性

本文原载于微信公众号：磐创AI（ID：xunixs），AI研习社经授权转载。欢迎关注磐创AI微信公众号及AI研习社博客专栏。

作者 | Ray

编辑 | 安可

出品 | 磐创AI技术团队

在约束最优化问题中，常常会利用到拉格朗日对偶性求解。在常用的机器学习算法中，支持向量机和最大熵模型都使用到该方法求最优解。因为后面将要讲到这两个算法，所以先介绍这种方法作为知识的铺垫。

对于有约束的问题，拉格朗日对偶性是将原始问题转化为最优问题，通过求解对偶问题而得到原始问题的解。

一、原始问题

假设f(x),ci(x),hj(x)是定义在Rn上的连续可微函数，最优化原始问题为：

首先，引进广义拉格朗日函数：

其中，α和β是拉格朗日乘子，且α_i≥0。

因为α_i≥0，c_i≤0，h_j等于0，所以L(x,α,β)的第二项小于等于0，第三项等于0，则可以推出：L(x,α,β)≤f(x)。

所以max L(x,α,β)=f(x)。定义：

则最优化原始问题等价于广义拉格朗日问题的极小极大问题：

定义原始问题的最优解为：

二、对偶问题

定义：

再考虑极大化上式，即：

这个广义拉格朗日的极大极小问题称为原始问题的对偶问题。

原始问题和对偶问题的关系：

如果原始问题和对偶问题都有最优解，则有：

证明：对任意的α，β和x，有

即：

由于原始问题和对偶问题都有最优值，所以：

即：

一句话总结就是对于同一个函数L，最小化后的最大值仍然小于或等于最大化后的最小值。

三、KKT条件

为了使得对偶问题的最优解也是原始问题的最优解，就必须满足KKT条件，也就是说KKT条件是其充分必要条件。接下来我们将讲解为什么要满足以下的KKT条件。

解释：

要使得对偶问题的最优解也是原始问题的最优解就要满足d_*=p_*，首先前三个条件对各变量求偏导得到他们的极值，这也是为什么要一开始要定义三个函数连续可导。

第四个条件是因为在前面已经提及L(x,α,β)的第二项小于等于0，要使得L等于f(x)，就得让第二项等于0，因为α_i≥0，c_i小于等于0，所以要保证第二项等于0，只能是每个α_i*c_i等于0。

第五个条件和第七个条件是原始问题的约束条件，第六个问题是拉格朗日乘子法需要满足的定义。

四、为什么要通过求解对偶问题来得到原始问题的最优解？

使用对偶问题求解是因为求解对偶问题比求解原始问题更加简单方便。比如在SVM中通过求解对偶问题能够使得求解的算法复杂度降低，方便核函数的引入等好处。具体为什么将在SVM讲解的时候解释。