前言:
现时同学们对“约束最值问题”大概比较讲究,看官们都需要学习一些“约束最值问题”的相关文章。那么小编同时在网络上汇集了一些对于“约束最值问题””的相关资讯,希望我们能喜欢,朋友们快快来了解一下吧!本文通过非常简洁和形象的方式说明解释凸优化中的对偶理论和KKT条件,并回答以下问题:
1、 对偶问题是如何解决原始问题的?
2、 什么是弱对偶?什么强对偶?
3、 强对偶的条件是什么?
4、 KKT条件与对偶的关系是怎么样的?
5、 KKT条件的必要性和充分性。
拉格朗日对偶
给定一个非线性规划问题,称为原始问题,存在另一个与之非常相关的非线性规划问题,就是拉格朗日对偶问题。为什么引入拉格朗日对偶?当原始问题不方便解决,特别是有不等式约束时,往往不便用函数微分方式处理,也就是不方便使用一阶、二阶导数来求解问题,我们用拉格朗日对偶就能很容易的解决。
在凸函数和适当的约束条件下,原始和对偶问题具有相同的最优目标值。
我们step by step来逐步分析:
原始问题:
对偶问题:
为了更形象直观,我们作一个变换,把f(x)映
射到z轴,把g(x)映射到y轴,变换后的区域如下图所示:
按照原始问题,我们要找符合约束的目标值的最小值,也就是在y<=0时的z的最小值。这样转化之后原来的不等式约束,就变得非常简单了,很明显图示红点就是符合要求的最小值。
现在看对偶问题是怎么求解目标的,先看z+uy的最小值,在变换后的坐标体系中,z+uy约束下求最值是线性规划问题,也就是求直线α=z+uy在与G区域保持接触的前提下,在z轴的截距的最小值。所以,我们假定u是一个常数,因为θ(u)是关于u的函数,现在在G区域平行移动直线,移动方向是(-u,-1),如图所示。
现在看到与G区域相切的直线能够使截距最小,但是,注意我们刚才在移动的过程中,把u当作常数,也就是说,对于一个固定的直线(u为常数),移动该直线使之滑过G区域,目标是在Z轴截距最小,就是要使该直线与G区域左下方边缘相切。而对偶问题:
是关于u的,要求θ(u)的最大值,也就是斜率是变量,刚才我们对直线α=z+uy是平移,现在要旋转,旋转的目标是求截距的最大值。
刚才一会求最小,一会儿求最大,有的人可能就晕乎了,我们现在总结如下:
1、 对于某直线平移,此时自变量是原问题的变量,使之与Z轴的截距是最小的,这个确保是在G区域左下边缘找切线。
2、 现在有一个直线簇,就是1中直线的集合(斜率变化),此时变量是对偶问题的变量;
3、 在这个直线簇中,找到截距最大的。
最后,我们看到,对偶问题和原始问题一样,目标点也是
。
以上我们看到,对偶问题和原始问题的解一样,我们把这种对偶叫做强对偶。
注意到,由于集合G的非凸性,对偶问题的解和原始问题的解有一个差距,就是对偶间隙(duality gap)。
对偶间隙
现在通过数学推导证明对偶间隙:
设原始问题:
对偶问题:
针对原问题的拉格朗日函数为:
对偶问题与拉格朗日函数的关系是:
我们有重要结论:
证明如下:
叫做对偶间隙(duality gap)
由下确界性质,设p*
为原问题的最优解,那么
我们把对偶问题的最优解记为d*
叫最优对偶间隙,如果强对偶,则有d*=p*
Slater条件,如果原问题是严格可行,且是凸问题,那么有
限于篇幅本文不给出slater条件的证明,这个证明过程是比较复杂,而且很有逻辑的,后边专门发文讲解。
KKT条件
假定
分别是原始问题、对偶问题的解,并且对偶问题是强对偶,那么
解释一下这个证明过程,第二个等号,是因为我们的对偶问题的最优目标值就是拉格朗日函数最小值(下确界),小于等于号,是因为最优解时的目标值一定不小于关于x的下确界。
所以有
这就是KKT条件中非常著名的互补松弛条件;
接下来,根据互补松弛条件,我们有
也就是说,x*
是拉格朗日函数的最小值时的解。所以有:
这就是KKT条件中的稳定性条件。
这两个条件再加上原问题、对偶问题的可行性,我们就得到KKT条件:
KKT条件的充分性:
如果
满足KKT条件,那么它们就分别是原始问题和对偶问题的解。
总结:
(1) 总是充分的;
(2) 在强对偶条件下, 是必要的。
标签: #约束最值问题