西瓜书扩展_拉格朗日对偶

2020-03-18 本文已影响0人我_7

原始目标函数（有约束条件）

对于任意一个带约束的优化都可以写成这样的形式：

$\underset{x}{\ min} \ f(x)$

$s.t.\ g_{i}(x)\leq0,\quad i=1,2,...,m$ $(1)$

$h_{j}(x)=0,\quad j=1,2,...,n$

新构造的目标函数（没有约束条件）

因为我们要求解的是最小化问题，所以一个直观的想法是如果我能够构造一个函数，使得该函数在可行解区域内与原目标函数完全一致，而在可行解区域外的数值非常大，甚至是无穷大，那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化是等价的问题。

通过给每一个约束条件加上一个拉格朗日乘子，我们组成拉格朗日方程：

$L(x,α,β)=f(x)+\sum_{i=1}^{m}α_{i}g_{i}(x) + \sum_{j=1}^{n}β_{j}h_{j}(x)$

接下来我们构造一个基于广义拉格朗日函数的原始问题，记为：

$θ_{P}(x)=\underset{β_{j},α_{i}\geq0}{\ max}\ L(x,α,β)=f(x)+\underset{β_{j},α_{i}\geq0}{\ max} \Bigg [ \sum_{i=1}^{m}α_{i}g_{i}(x) + \sum_{j=1}^{n}β_{j}h_{j}(x) \Bigg ]$

可行解区域外：当其中任何一个约束条件不满足时，令 $α_{i}=+∞$ ，则有：

$θ_{P}(x)=+∞$

可行解区域内：由于 $g_{i}(x)\leq0$ 且系数 $α_{i}\geq0$ ，则有：

$\Bigg [ \sum_{i=1}^{m}α_{i}g_{i}(x) + \sum_{j=1}^{n}β_{j}h_{j}(x) \Bigg ] \leq0$ $(2)$

所以最大值只能在它们都取 $0$ 的时候得到

$\underset{β_{j},α_{i}\geq0}{\ max} \Bigg [ \sum_{i=1}^{m}α_{i}g_{i}(x) + \sum_{j=1}^{n}β_{j}h_{j}(x) \Bigg ] =0$

所以有：

$θ_{P}(x)=f(x)$

因此，最小化 $θ_{P}(x)$ 的解就等价于式子 $(1)$ 解。

对偶问题

$θ_{D}(α,β)$ 对偶函数， $θ_{P}(x)$ 原始函数

到这里，我们成功把带约束问题转化为了无约束问题。但是存在 $α,β$ 这两组参数，我们没办法通过对 $x$ 求导的方法得到最优解。

新构造原始问题的一种表达：

$\underset{x}{\ min}\ θ_{P}(x) =\underset{x}{\ min}\ \underset{β_{j},α_{i}\geq0}{\ max}\ L(x,α,β)=p^*$ $(3)$

这里用 $p^*$ 表示原始问题的最优值。现在我们来把最小和最大的位置交换一下：

$\underset{β_{j},α_{i}\geq0}{\ max}\ θ_{D}(α,β)=\underset{β_{j},α_{i}\geq0}{\ max}\ \underset{x}{\ min}\ L(x,α,β)=d^*$ $(4)$

当然，交换以后的问题不再等价于原始问题，这个新问题的最优值用 $d^*$ 来表示。

所以我们就把 $(4)$ 称作是 $(3)$ 的对偶问题。如果我们能够想办法证明 $(4)$ 和 $(3)$ 存在相同的解 $x^*,α^*,β^*$ ，那我们就可以在对偶问题中选择比较简单的一个来求解。

对偶问题同解的证明

需要注意的是，无论原始问题是什么形式，对偶问题总是一个凸优化的问题——它的极值是唯一的。

弱对偶（对于所有的优化问题都成立）：

对于最优解（可行解区域内） $\tilde{x }$ ， $L(x^*,α,β)$ 总是满足式子 $(2)$ ：

$f(x^*)=θ_{P}(x^*) = \underset{x}{\ min}\ θ_{P}(x)=p^*$

$θ_{D}(α^*,β^*)= \underset{β_{j},α_{i}\geq0}{\ max}\ θ_{D}(α,β)=d^*$

$θ_{D}(α,β)=\underset{x}{\ min}\ L(x,α,β)\leq L(\tilde{x },α,β)$

$=f(x^*)+\sum_{i=1}^{m}α_{i}g_{i}(x^*) + \sum_{j=1}^{n}β_{j}h_{j}(x^*)$

$\leq f(x^*)=p^*$

则有：

$d^*=\underset{β_{j},α_{i}\geq0}{\ max}\ θ_{D}(α,β)\leq p^*$

强对偶（并不是所有的优化问题都成立）：

假设 $x^∗$ 和 $(α^*,β^*)$ 分别是原始问题和对偶问题的最优解，相应的极值为 p∗ 和 d∗ ，首先 p∗=d∗ ，此时我们可以得到：

$θ_{P}(x^*)=f(x^*)=θ_{D}(α^*,β^*)$

则有：

强对偶成立的情况下，我们可以通过求解对偶问题来优化原始问题，这里我们就来提一下强对偶成立的条件。

这里我们就简要地介绍一下Slater条件和KKT条件。

Slater条件是指存在严格满足约束条件的点 $x$ ，这里的“严格”是指 $g_{i}(x)\leq0$ 中的“小于或等于号”要严格取到“小于号”，亦即，存在 $x$ 满足：

$g_{i}(x)<0,\quad i=1,2,...,m$

$h_{j}(x)=0,\quad j=1,2,...,n$

如果原始问题是凸问题并且满足Slater条件的话，那么强对偶成立。需要注意的是，这里只是指出了强对偶成立的一种情况，而并不是唯一情况。例如，对于某些非凸优化的问题，强对偶也成立。

凸优化 217~219

234~236

总之，对目标函数和约束函数可微的任意凸优化问题，任意满足KKT条件的点分别是原、对偶最优解，对偶间隙为零。

西瓜书扩展_拉格朗日对偶

猜你喜欢

热点阅读