凸优化问题

凸优化问题

凸优化问题

优化问题

我们用

描述在所有满足

我们称

  • x为优化变量

  • 函数f0为目标函数费用函数

  • 不等式fi(x)≤0成为不等式约束,相应的函数fi称为不等式约束函数

  • 方程组hi(x)=0称为等式约束,相应的函数hi称为等式约束函数

  • 如果没有约束,我们称问题为无约束问题

对目标和所有约束函数有定义的点的集合

称为上述优化问题的定义域。当点x∈D满足约束

时,x是可行的。当上述优化问题至少有一个可行点时,我们称为是可行的,否则称为不可行。所有可行点的集合称为可行集约束集

上述优化问题的最优值p*定义为

如果x*是可行的,并且f0(x*)=p*,我们称x*为最优点,或x*解决了上述优化问题。所有解的集合称为最优集,记为

如果上述优化问题存在最优解,我们称最优值是可得可达的,称问题可解。如果Xopt是空集,我们称最优值是不可得或者不可达的(这种情况常在问题无下界时发生)。

凸优化问题定义

凸优化问题是形如

的问题,其中f0,...,fm为凸函数。

对比上式的问题和上届的一般的优化问题,凸优化问题有三个附加的要求:

  • 目标函数必须是

  • 不等式约束函数必须是

我们立即注意到一个重要的性质:凸优化问题的可行集是凸的,因为它是问题定义域

(这是一个凸集)、m个(凸的)下水平集

以及p个超平面

的交集。因此,在一个凸优化问题中,我们是在一个凸集上极小化一个凸的目标函数

对偶

拉格朗日函数

如上一章节所示,标准形式的优化问题如下:

其中,自变量x∈R^n,设问题的定义域为

是非空集合,优化问题的最优值为p*。注意到这里并没有假设上述问题是凸优化问题。

Lagrange对偶的基本思想是在目标函数中考虑上述问题的约束条件,即添加约束条件的加权和,得到增广的目标函数。

定义上述问题的Lagrange函数L为

拉格朗日对偶函数

最优值的下界

下面来很容易地验证这个重要性质。

这是因为左边的第一项非正,而第二项为零。根据上述不等式,有

通过线性逼近来理解下界性质

可通过示性函数进行线性逼近来理解拉格朗日函数和其给出下界的性质。

首先将原问题重新描述为一个无约束问题

,我们随之可以得到,对偶函数是原问题最优函数值的一个下界

拉格朗日对偶函数和共轭函数

前面“共轭函数”一节提到的函数f的共轭函数f*为

事实上,共轭函数和拉格朗日对偶函数紧密相关。下面的问题说明了一个简单的联系,考虑问题

(虽然此问题没有什么挑战性,目测就可以看出答案)。上述问题的拉格朗日函数为

,其对偶函数为

更一般地(也更有用地),考虑一个优化问题,其具有线性不等式以及等式约束,

利用函数f0的共轭函数,我们可以将问题(上式)的对偶函数表述为

拉格朗日对偶问题

可以讲这个问题表述为优化问题

Lagrange对偶问题是一个凸优化问题,这是因为极大化的目标函数是凹函数(因为它包含负的共轭函数,而共轭函数是凸函数),且约束集合是凸集。因此,对偶问题的凸性和原问题是否是凸优化问题无关。

弱对偶性

Lagrange对偶问题的最优值,我们用d*表示,根据定义,这是通过Lagrange函数得到的原问题最优值p*的最好下界。特别地,我们有下面简单但是非常重要的不等式

即使原问题不是凸问题,上述不等式依然成立。这个性质称为弱对偶性

定义差值p*-d*是原问题的最优对偶间隙。它给出了原问题最优值以及通过Lagrange对偶函数所能得到的最好(最大)下界之间的差值。最优对偶间隙总是非负的。

强对偶性和Slater约束准则

如果等式d*=p*成立,即最优对偶间隙为零,那么强对偶性成立。这说明从Lagrange对偶函数得到的最好下界是紧的。

对于一般情况,强对偶性不成立。但是,如果原问题是凸问题,即可以表述为如下形式

其中,函数f0,...,fm是凸函数,强对偶性通常(但不总是)成立。有很多研究成果给除了强对偶性成立的条件(除了凸性条件外),这些条件称为约束准则

满足上述条件的点有时称为严格可行,这是因为不等式约束严格成立。

Slater条件是说:存在x,使不等式约束中的“小于等于号”要严格取到“小于号”

Slater定理说明,当Slater条件成立(且原问题是凸问题)时,强对偶性成立。

拉格朗日对偶的解释

强弱对偶性的极大极小描述

可以将原、对偶优化问题以一种更为对称的方式进行表达,为了简化讨论,假设没有等式约束;事实上,现有的结果很容易就能拓展到有等式约束的情形。

首先,我们注意到

。这意味着我们可以将原问题的最优值写成如下形式

根据对偶函数的定义,有

因此弱对偶性可以表述为下述不等式

强对偶性可以表述为下述不等式

==========================================================

==========================================================

事实上,上面的不等式是否成立和L的性质无关:对任意f,下式成立:

这个一般性的等式称为极大极小不等式。若等式成立,即

我们称f(以及W和Z)满足极大极小性质或者鞍点性质。当然,强极大极小性质只在特殊情况下成立,例如函数f是满足对偶性问题的Lagrange函数。

鞍点解释

其中,

对策解释

我们可以通过一个连续零和对策来理解上面的极大极小不等式,极大极小等式(如下式所示),以及鞍点性质(如下图所示)。

如果局中人甲选择w∈W,局中人乙选择z∈Z。那么甲支付给乙支付额f(w,z)。甲希望极小化f,而乙当然希望极大化f了,因为想要拿更多的钱嘛。

(1)设甲先做出选择,乙知道甲的选择后,再做出选择。

而甲知道乙将基于自己选择的w∈W来采取此措施,所以,甲会选择w∈W使得最坏情况下的支付额尽可能得小。因此甲选择w为

,这样甲付给乙的支付额为

,这样甲需付给乙的支付额为

极大极小不等式说明(直观上显然)这样一个事实,后选择的人具有优势,即如果在选择的时候,已经知道对手的选择,则更具有优势。换言之,如果甲必须先做出选择,乙获得的支付额更大。当鞍点性质成立时,做出选择的顺序对最后的支付额没有影响。

此问题的最优对偶间隙恰是后选择的局中人所具有的优势,即当知道对手的选择后再做出选择的优势。如果强对偶性成立,知晓对手的选择不会带来任何优势。

最优性条件

互补松弛性

第一个等式说明最优对偶间隙为零,第二个等式是对偶函数的定义。第三个不等式是根据Lagrange函数关于x求下确界小于等于其在x=x*处的值得来。最后一个不等式的成立是因为下式

。因此,在上面的式子链中,两个不等式取等号。

另外一个重要的结论是

事实上,求和项的每一项都非正,因此有

或者等价地

粗略地讲,上式意味着在最优点处,除了第i个约束起作用的情况(fi(x*)=0),最优Lagrange乘子的第i项都为零。

KKT最优性条件

现在假设函数f0,...,fm, h1,...,hp可微(因此定义域是开集),但并不假设这些函数是凸函数。

非凸问题的KKT条件

因此,我们有

我们称上式为Karush-Kuhn-Tucker(KKT)条件。

总之,对于目标函数和约束函数可微的任意优化问题,如果强对偶性成立,那么任意一对原问题最优解和对偶问题最优解必须满足KKT条件。即KKT条件是一组解成为最优解的必要条件

凸问题的KKT条件

总结上面两段:当原问题是凸问题时,KKT条件是一组解成为最优解的充分条件;当强对偶性成立,KKT条件是一组解成为最优解的必要条件

也就是说,当一个问题满足下面两个条件:

  • 原始问题是凸的,即凸优化问题

  • 满足Slater条件

KKT条件的用途:

KKT条件在优化领域有着重要作用。在一些特殊的情况下,是可以求解KKT条件的(因此也可以求解优化问题)。更一般地,很多求解凸优化问题的方法可以认为或者理解为求解KKT条件的方法。

KKT条件可以用于如下方面:

  • 有时候可以直接从KKT条件里得到最优的解析解。

  • 等式约束的优化问题,可以通过KKT条件转化为无约束方程求零点问题。

  • 有不等式约束的优化问题,可以使用KKT条件来简化,帮助求解。

KKT条件的力学解释

可以从力学角度(这其实也是最初提出Lagrange的动机)对KKT条件给出的一个较好的解释。我们可以通过一个简单的例子描述这个想法。下图所示系统包含两个连在一起的模块,左右两端是墙,通过三段弹簧将它们连在一起。

模块本身的宽度是w>0,且它们之间不能互相穿透,也不能穿透墙。

弹性势能可以写成模块位置的函数

其中,ki>0是三段弹簧的劲度系数。在满足以下不等式的约束

的条件下极小化弹性使能可以得到平衡位置x*。这些约束也称为运动约束,它描述了模块的宽度w>0,且不同的模块之间以及模块和墙之间不能穿透,通过求解如下优化问题可以得到平衡位置

这是一个二次规划问题。

  • 运动约束

  • 非负约束

  • 互补松弛条件

  • 零梯度条件

通过解对偶问题求解原问题

唯一。那么,如果上式的解是原问题的可行解,那么它一定就是原问题的最优解;如果它不是原问题的可行解,那原问题本身就不存在最优解,即原问题的最优解无法达到。

当对偶问题比原问题更容易求解时,比如说对偶问题可以解析求解或者有某些特殊的结构容易求解,上述方法很有效。

参考资料

  • 《凸优化》Boyd

本文绝大部分内容就是摘抄浓缩的此书的前240页,以方便快速学习此书中与机器学习相关的核心内容。

"共轭函数"一小节部分参考了此博客。

Last updated