在讲拉格朗日对偶之前,我们首先复习一下拉格朗日乘数法.

拉格朗日乘数法-等式约束

求此方程的最小值:

同时需要满足条件:

令:

image.png

图中蓝色是,红色是,什么时候能保证最小且与相交呢?答案是相切的时候,此时两个方程的梯度方向相同,大小不同,所以有:

其中为拉格朗日乘子.

实际上,还有更简便的方式,定义:

这个函数被称之为拉格朗日函数,将所有方程的偏微分设为零,得到一个方程组,最小值是以下方程组的解中的一个:

拉格朗日乘数法-不等式约束

情况一

求极值:

同时需要满足不等式约束:

image.png

可以看到,这个不等式约束有和没有没区别.

情况二

换一个不等式约束:

image.png

在不等式约束下,最小值是在边缘相切的地方取得:
image.png

此外这里的方向相反,否则约束条件就不起作用了:
image.png
所以再增加一个条件:

KKT条件

综合上面的所有情况,同时包含等式和不等式约束的一般优化问题:

KKT条件为:

这个方程组也就是所谓的KKT条件。

KKT条件是为最优解的必要条件.

拉格朗日对偶

image.png
拉格朗日对偶是拉格朗日乘数法的一个扩展.

对于带有等式和不等式多个约束条件的优化问题:

转换成拉格朗日函数

这里的是拉格朗日乘数.对于

不难得出如果符合约束条件

如果不符合约束条件

由此我们可以得出一个和原始问题等价的问题:

稍后我们会用到这个公式,我们现在再来看一个问题:

下表D表示对偶,现在我们来看一下对偶优化问题

不难证明

(小的里面挑出来的大的,一定小于等于大的里面挑出来的小的).当满足一定条件时,可以取等号,即

如果我们能证明满足条件,那么我们就可以用求对偶函数的方式来求原函数.让我们来看看这些条件是什么.

假设函数是凸函数,是仿射函数.进一步假设约束是连续的,这就意味着有使在所有i上成立.

在上述假设之下,一定存在为原始问题的解,是对偶问题的解.使,并且遵从KKT条件:

如果满足以上条件,则:


参考:
https://zhuanlan.zhihu.com/p/26514613
https://mp.weixin.qq.com/s/SnHGG7ZEZ9SJapPmWhhHpQ

posted @ 2018-12-08 12:08:36
评论加载中...

发表评论