当前位置:   article > 正文

拉格朗日对偶性_拉格朗日原始对偶

拉格朗日原始对偶

说明

在约束优化问题中,常常用拉格朗日对偶性来将原始问题转为对偶问题,通过解对偶问题的解来得到原始问题的解。

0 为什么要利用对偶?

首先要明确,对偶问题的解不一定直接等于原问题的解(弱对偶),但是,对偶问题有两点性质。

1.1 满足某些条件时,对偶问题直接等于原问题的解(强对偶)

1.2 无论原始问题是否是凸的,对偶问题都是凸优化问题

1.3(重点)凸优化问题的局部最优就是全局最优

显然,在某些情况下,直接对对偶问题求解可以得到原问题的解,而且对偶问题是凸优化,易于求解。所以利用对偶来求解是很有用的。

1、原始问题

考虑原始的优化问题如下
在这里插入图片描述
观察上面的最优化问题,便是在一定的约束条件下求解函数的极值,我们上面已经说过拉格朗日乘子法啦,所以这里便用到了。先定义拉格朗日函数
在这里插入图片描述需要明确:其中α≥0、λ任意,均为拉格朗日乘子,i=1,2,…,k且j=1,2,…,m

如果按照我们按照拉格朗日乘子法的思路,则应该让L(x,α,β)对x以及参数α和β进行求导,然后得出结果带入原始便可求出我们需要的最优解。

但需要注意两点:
(1)这里参数α和λ总共k+m个,如果全部求偏导工作量太大,不现实;
(2)并且大家有没有想过,这个问题可能根本就没有最优解这种情况存在。

针对上面情况,我们便引出了换一种思路,那就是利用对偶问题,也就是将原问题转化成其对偶问题进行求解。

下面和大家先说一下对偶问题的基本思想,然后我们再继续从上面的问题出发,推导其对偶问题,进行求解。

对偶问题的性质:无论原命题的形式如何,对偶问题都是一个凸优化问题,还记得凸优化问题的好处吧,那就是局部最优解就是全局最优解,并且容易求解,所以我们将问题转化为其对偶问题就简化了问题的求解思路。

上面我们利用拉格朗日乘子法得到了如下式子:
在这里插入图片描述

现在我们自定义一个函数如下:
在这里插入图片描述在这里插入图片描述
分析上面的自定义函数有:
在这里插入图片描述对上面的式子进行分析:

(1)式说明,当目标函数的约束条件都满足时,g(x)≤0,α≥0,αg(x)≤0,所以在对α求最大值时maxαg(x)=0,又因为h(x)=0,所以则自定义的函数便是上面需要求解的目标函数f(x),
(2)则是只要目标函数的约束条件只有一个不满足,则自定义的函数便等于无穷大!即只要满足约束条件时自定义的函数才会变成目标函数f(x).
如果我们对自定义函数pθ(x)求最小值,则pθ(x)的最小值一定是满足约束条件的f(x)的最小值。

所以我们便可以认为自定义的函数pθ(x) 是对原理优化问题中的约束条件进行了吸收,是原来的约束优化问题变为无约束优化问题(相对于原来变量x 无约束了),即我们可以将最初的优化问题写成:

在这里插入图片描述
上式便是我们需要优化的原问题。

2、 对偶问题

原问题的对偶问题便是:
在这里插入图片描述同时,我们定义原始问题的最优值为P*
在这里插入图片描述
同时,我们定义对偶问题的最优值为Q*
在这里插入图片描述

3、原始问题和对偶问题的关系

可以得知Q⩽P,因为P是先求最大的一块区域然后在这块区域求最小,Q是先求最小的一块区域然后在这块区域求最大,最大里面的最小,总会比最小里面的最大要大(或等于)。

Q⩽P,称为弱对偶,对于所有优化问题都成立,这个时候我们可以得到原始问题的一个下界。

如果Q*=P*,称为强对偶,满足某些条件才成立,这时可以用解对偶问题替代原始问题。那么满足什么样的条件可以得到强对偶呢?

如果原问题是一个凸优化,并且不等式约束g(x)是严格可行的,即存在x对所有i有gi(x)<0,那么强对偶成立。这里需要注意的是,这里的条件只是强对偶成立的一种情况,对于非凸的问题也有可能是强对偶。
slater条件:存在x对所有i有gi(x)<0,那么强对偶成立。
强对偶成立时,将拉格朗日函数分别对原变量x和对偶变量α和λ分别求导,令导数等于零(还需要满足KKT条件),即可求解对偶问题的解,也就求得了原问题的解。

4、 对偶求解和拉格朗日乘子法求解

对于拉格朗日乘子法求解,当原问题是凸优化的时候,考虑满足KKT的条件,对于拉格朗日函数求导等于0即可得到解。

对于对偶问题求解,转换为对偶函数求解,为了得到原始问题的解,要求强对偶,而在强对偶(不一定满足原问题凸优化)的情况下,考虑满足KKT的条件,对于拉格朗日函数求导等于0即可得到解。

当原问题是凸优化的时候,强对偶和KKT条件是互为充要条件的。

参考资料
支持向量机(SVM)必备知识(KKT、slater、对偶)
拉格朗日对偶性

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/740370
推荐阅读
相关标签
  

闽ICP备14008679号