龙空技术网

透彻理解凸优化中的对偶与KKT条件

AI火箭营 368

前言:

现时同学们对“约束最值问题”大概比较讲究,看官们都需要学习一些“约束最值问题”的相关文章。那么小编同时在网络上汇集了一些对于“约束最值问题””的相关资讯,希望我们能喜欢,朋友们快快来了解一下吧!

本文通过非常简洁和形象的方式说明解释凸优化中的对偶理论和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) 在强对偶条件下, 是必要的。

标签: #约束最值问题