考虑凸优化问题
假设 ,定义域为 ,最优解为 。
我们定义拉格朗日函数(Lagrangian) 为 ,
再取下确界得到拉格朗日对偶函数(Lagrange dual function)
这个拉格朗日对偶函数可不得了啦!他有两个很重要的性质:
Remarks:上面两个性质为什么重要呢?首先由于 ,这可以给出原问题最优解的一个不平凡下界,这意味着如果原问题很难求解的时候,我们可以转变思路,求解一个新的优化问题:
另一方面,由于不论原函数是否为凸优化问题,新的问题都是凸的,因此可以方便求解。下面举几个例子。
例子 1:原问题为
那么可以很容易得到拉格朗日函数为 ,对偶函数为 ,也即
。
例子 2:标准形式的线性规划(LP)
按照定义容易得到对偶问题为
例子 3:原问题为最小化范数
对偶函数为
这个推导过程中用到了共轭函数的知识。实际上上面三个例子都是线性等式约束,这种情况下,我们应用定义推导过程中可以很容易联想到共轭函数。(实际上加上线性不等式约束也可以)
例子 4:(原问题非凸)考虑 Two-way partitioning (不知道怎么翻译了...)
对偶函数为
于是可以给出原问题最优解的下界为 if 。这个下界是不平凡的,比如可以取 ,可以给出 。
上面已经多次提到对偶问题(Lagrange dual problem) 了
假如对偶问题的最优解为 ,那么我们有 。
现在我们当然想知道什么情况下可以取等号,也即 ,此时我们只需要求解对偶问题就可以获得原问题的最优解了。在此之前,我们先引入两个概念:强对偶和弱对偶。
弱对偶(weak duality):满足 ,原问题不论是否为凸,弱对偶总是成立;
强对偶(strong duality):满足 ,强对偶并不总是成立,如果原问题为凸优化问题,一般情况下都成立。在凸优化问题中,保证强对偶成立的条件为被称为 constraint qualifications。
有很多种不同的 constraint qualifications,常用到的一种为 Slater’s constraint qualification(SCQ),其表述为
SCQ:对于凸优化问题
如果存在可行解 ,使得
那么就能保证强对偶性。
Remarks:
下面再举几个例子,看一看他们的 SCQ 条件是什么。
例子 1:还是考虑线性规划(LP) 或者二次规划(QP)
那么根据 SCQ 可以得到,如果想得到强对偶性,应该有 。
例子 2:(原问题非凸) Trust Region Methods
其中 ,因此原问题不是凸的。他的对偶函数就是
注意如果不满足 或 ,则 。那么就可以得到对偶问题为
也可以等价转换为 SDP
Remarks:这里用到了舒尔补(Schur complement)的知识。考虑矩阵
其中 。那么有以下及条性质:
关于第 3 条中的第二个要求 ,对 进行奇异值分解,有 ,那么我们对任意 ,有 ,而 实际上就是向 的投影矩阵,因此就要求 。
前面给出的是 SCQ 的代数描述,那么如何证明呢?另外如何从几何角度直观理解呢?
首先我们可以考虑最简单的优化问题
定义集合 ,那么对偶函数为
如果我们画出下面这张图,阴影部分就是可行区域 ,而 则正好定义了一个支撑超平面, 就等于 轴的交点。通过取不同的 我们就可以得到不同的支撑超平面,也可以得到不同的 ,最终会有某一个 对应的是 。还需要注意这里的支撑超平面永远不可能是竖直的。
那么 体现在哪个点呢?由于对于原优化问题,我们有 ,因此体现在这个图里面就是 ,也就是上面左图当中的红色区域,而 。
理解了这张图,我们现在开始证明两件事:
注:在此之前,我们不妨加入等式约束,也即 。
弱对偶性的证明:我们有
强对偶性条件 SCQ 的证明:由 可以得到
这实际上定义了 的一个超平面。特别的有 ,因此也有
这个不等式可以自然地导出弱对偶性,当“=”成立时则可以导出强对偶性。那么什么时候取等号呢?点 为支撑点的时候!也就是说
如果在边界点 处存在一个非竖直的支撑超平面,那么我们就可以找到 使得上面的等号成立,也就是得到了强对偶性。
注意前面的分析中我们并没有提到 SCQ,那么 SCQ 是如何保证强对偶性的呢?注意 SCQ 要求存在 使得 ,这也就意味着 在 半平面上有点,因此如果支撑超平面存在的话,就一定不是垂直的。
但这又引出另一个问题,那就是支撑超平面一定存在吗?答案是一定存在,这是由原问题的凸性质决定的。为了证明这一点,我们可以引入一个类似于 epigraph 的概念:
由于原优化问题为凸的,可以应用定义证明集合 也是凸的,同时 ,那么集合 在 点就一定存在一个支撑超平面。又由 SCQ 可知这个支撑超平面一定不是竖直的,因此就可以得到强对偶性了。
注: 也成立。
前面讨论拉格朗日函数的时候都只考虑了标量函数,如果约束函数为广义不等式,也即
那么他的拉格朗日函数就是
对偶函数就是
其同样满足 。对偶问题为
强对偶性以及 Slater's Condition 是类似的。
对于 SDP 问题
拉格朗日函数就是
对偶函数为
对偶问题就是
强对偶性以及 Slater's Condition 是类似的。
注意我们说强对偶性需要严格满足不等式约束(也即最优解需要满足 而不能是 ),但如果存在线性不等式约束,则可以取到等号(也即 )。这就会出现下面的现象: