Login    Register account      
    
  


News Message

凸优化笔记11:对偶问题



凸优化笔记11:对偶问题



1. 拉格朗日函数

考虑凸优化问题

[公式]

假设 [公式],定义域为 [公式],最优解为 [公式]

我们定义拉格朗日函数(Lagrangian) 为 [公式][公式]

[公式]

再取下确界得到拉格朗日对偶函数(Lagrange dual function) [公式]

[公式]

这个拉格朗日对偶函数可不得了啦!他有两个很重要的性质:

  1. [公式] 是凹函数(不论原问题是否为凸问题)
  2. 如果 [公式],那么 [公式](对任意 [公式] 都成立)

Remarks:上面两个性质为什么重要呢?首先由于 [公式],这可以给出原问题最优解的一个不平凡下界,这意味着如果原问题很难求解的时候,我们可以转变思路,求解一个新的优化问题:

[公式]

另一方面,由于不论原函数是否为凸优化问题,新的问题都是凸的,因此可以方便求解。下面举几个例子。

例子 1:原问题为

[公式]

那么可以很容易得到拉格朗日函数为 [公式],对偶函数为 [公式],也即

[公式]

例子 2:标准形式的线性规划(LP)

[公式]

按照定义容易得到对偶问题为

[公式]

例子 3:原问题为最小化范数

[公式]

对偶函数为

[公式]

这个推导过程中用到了共轭函数的知识。实际上上面三个例子都是线性等式约束,这种情况下,我们应用定义推导过程中可以很容易联想到共轭函数。(实际上加上线性不等式约束也可以)

例子 4:(原问题非凸)考虑 Two-way partitioning (不知道怎么翻译了...)

[公式]

对偶函数为

[公式]

于是可以给出原问题最优解的下界为 [公式] if [公式]。这个下界是不平凡的,比如可以取 [公式],可以给出 [公式]

2. 对偶问题

上面已经多次提到对偶问题(Lagrange dual problem) 了

[公式]

假如对偶问题的最优解为 [公式],那么我们有 [公式]

现在我们当然想知道什么情况下可以取等号,也即 [公式],此时我们只需要求解对偶问题就可以获得原问题的最优解了。在此之前,我们先引入两个概念:强对偶和弱对偶。

弱对偶(weak duality):满足 [公式],原问题不论是否为凸,弱对偶总是成立;

强对偶(strong duality):满足 [公式],强对偶并不总是成立,如果原问题为凸优化问题,一般情况下都成立。在凸优化问题中,保证强对偶成立的条件为被称为 constraint qualifications

有很多种不同的 constraint qualifications,常用到的一种为 Slater’s constraint qualification(SCQ),其表述为

SCQ:对于凸优化问题
[公式] 如果存在可行解 [公式],使得
[公式] 那么就能保证强对偶性。

Remarks

  • 由于存在线性等式约束,因此实际定义域可能不存在内点,可以将这一条件放松为相对内点 [公式]
  • 如果不等式约束中存在线性不等式,那么他也不必严格小于0。也即如果 [公式],则只需要满足 [公式] 即可。

下面再举几个例子,看一看他们的 SCQ 条件是什么。

例子 1:还是考虑线性规划(LP) 或者二次规划(QP)

[公式]

那么根据 SCQ 可以得到,如果想得到强对偶性,应该有 [公式]

例子 2:(原问题非凸) Trust Region Methods

[公式]

其中 [公式],因此原问题不是凸的。他的对偶函数就是

[公式]

注意如果不满足 [公式] 或 [公式],则 [公式]。那么就可以得到对偶问题为

[公式]

也可以等价转换为 SDP

[公式]

Remarks:这里用到了舒尔补(Schur complement)的知识。考虑矩阵
[公式] 其中 [公式]。那么有以下及条性质:
  • [公式]
  • 若 [公式],则 [公式]
  • [公式]

关于第 3 条中的第二个要求 [公式],对 [公式] 进行奇异值分解,有 [公式],那么我们对任意 [公式],有 [公式],而 [公式] 实际上就是向 [公式] 的投影矩阵,因此就要求 [公式]

3. SCQ 几何解释

前面给出的是 SCQ 的代数描述,那么如何证明呢?另外如何从几何角度直观理解呢?

首先我们可以考虑最简单的优化问题

[公式]

定义集合 [公式],那么对偶函数为

[公式]

如果我们画出下面这张图,阴影部分就是可行区域 [公式],而 [公式] 则正好定义了一个支撑超平面,[公式] 就等于 [公式] 轴的交点。通过取不同的 [公式] 我们就可以得到不同的支撑超平面,也可以得到不同的 [公式],最终会有某一个 [公式] 对应的是 [公式]。还需要注意这里的支撑超平面永远不可能是竖直的。

(λ,1)^T 正好定义了一个支撑超平面
每个 λ 对应一个支撑超平面

那么 [公式] 体现在哪个点呢?由于对于原优化问题,我们有 [公式],因此体现在这个图里面就是 [公式],也就是上面左图当中的红色区域,而 [公式]

理解了这张图,我们现在开始证明两件事:

  1. 证明弱对偶性,也即 [公式]
  2. 证明强对偶性条件 SCQ。

注:在此之前,我们不妨加入等式约束,也即 [公式]

弱对偶性的证明:我们有 [公式]

[公式]

强对偶性条件 SCQ 的证明:由 [公式] 可以得到

[公式]

这实际上定义了 [公式] 的一个超平面。特别的有 [公式],因此也有

[公式]

这个不等式可以自然地导出弱对偶性,当“=”成立时则可以导出强对偶性。那么什么时候取等号呢?点 [公式] 为支撑点的时候!也就是说

如果在边界点 [公式] 处存在一个非竖直的支撑超平面,那么我们就可以找到 [公式] 使得上面的等号成立,也就是得到了强对偶性。

注意前面的分析中我们并没有提到 SCQ,那么 SCQ 是如何保证强对偶性的呢?注意 SCQ 要求存在 [公式] 使得 [公式],这也就意味着 [公式] 在 [公式] 半平面上有点,因此如果支撑超平面存在的话,就一定不是垂直的。

但这又引出另一个问题,那就是支撑超平面一定存在吗?答案是一定存在,这是由原问题的凸性质决定的。为了证明这一点,我们可以引入一个类似于 epigraph 的概念:

[公式]

由于原优化问题为凸的,可以应用定义证明集合 [公式] 也是凸的,同时 [公式],那么集合 [公式] 在 [公式] 点就一定存在一个支撑超平面。又由 SCQ 可知这个支撑超平面一定不是竖直的,因此就可以得到强对偶性了。

注:[公式] 也成立。

4. 广义不等式约束与SDP

前面讨论拉格朗日函数的时候都只考虑了标量函数,如果约束函数为广义不等式,也即

[公式]

那么他的拉格朗日函数就是

[公式]

对偶函数就是

[公式]

其同样满足 [公式]。对偶问题为

[公式]

强对偶性以及 Slater's Condition 是类似的。

对于 SDP 问题

[公式]

拉格朗日函数就是

[公式]

对偶函数为

[公式]

对偶问题就是

[公式]

强对偶性以及 Slater's Condition 是类似的。

5. 对偶问题的强对偶性与可行性

注意我们说强对偶性需要严格满足不等式约束(也即最优解需要满足 [公式] 而不能是 [公式]),但如果存在线性不等式约束,则可以取到等号(也即 [公式])。这就会出现下面的现象:

  1. 对于 LP 问题,由于约束是线性的,因此强对偶性只要求有可行解,而不要求 strictly feasible
  2. 对于其他问题,若存在非线性约束,比如 SOCP/SDP 问题,如果想要满足强对偶性,就需要满足 strictly feasible,这就会出现两种情况:1)问题本身的可行域不可能满足 strictly feasible,那么就达不到强对偶性,于是 [公式];2)问题可行域满足 strictly feasible,但是由于最优解达不到(比如 [公式]),那么此时原问题和对偶问题仍满足强队偶性,但是原问题最优解达不到,而对偶问题则可以达到。



Share Http URL:  http://www.wittx.cn/get_news_message.do?new_id=699














请输入评论