Ch3nyang's blog

home

home

person

about

hive

project

collections_bookmark

mindclip

rss_feed

rss

对偶问题解释

calendar_month 2021-03
archive 数学
tag optimization

理解什么是对偶函数、对偶问题、强弱对偶、Slater 条件和 KKT 条件。

对偶函数和对偶问题

标准形式最优化问题

\[\begin{array}{lll}{\mathop{\text{minimize}}\limits_{\boldsymbol{x}}}&f_0(x)\\\text{subject to}&f_i(x)\leq0&i=1,\cdots,m \\&h_i(x)=0&i=1,\cdots,p \end{array}\]

Lagrange 对偶函数

\[L(x,\lambda,v)=f_0(x)+\sum\limits_{i=1}^{m}{\lambda_i f_i(x)}+\sum\limits_{i=1}^{p}{v_i h_i(x)}\]

Lagrange 对偶问题

\[\begin{array}{lll}g(\lambda,v)&=&\inf\limits_{x\in D}{L(x,\lambda,v)}\\&=&\inf\limits_{x\in D}{\left(f_0(x)+\sum\limits_{i=1}^{m}{\lambda_i f_i(x)}+\sum\limits_{i=1}^{p}{v_i h_i(x)} \right)} \end{array}\]

“不满意度”

为什么对偶问题是原问题的下界?

我们重新考虑下面的函数

\[\min f_0(x)+\sum\limits_{i=1}^{m}{I_\_( f_i(x))}+\sum\limits_{i=1}^{p}{I_0(h_i(x))}\]

其中,示性函数

\[I_\_(u)=\left\{\begin{array}{ll}0&u\leq0\\\infty&u>0 \end{array} \right.\]

类似的,\(I_0\) 也是示性函数。

示性函数就像一堵墙。当 \(f_i(x)\leq0\) 时,这堵“墙”不存在;而在 \(f_i(x)>0\) 时,这堵“墙”有无穷高,你永远也过不去。这样,保证了原问题条件一定成立。

我们也可以把它理解为不满意度。当 \(f_i(x)\leq0\) 时,我们对它是十分满意的;而在 \(f_i(x)>0\) 时,我们对它一点也不满意。

很容易看出,利用示性函数的新问题与原问题是等价的。

这种行为非常地二极管,因此我们希望能够更加温和一点:给满意程度打个分。我们把示性函数替换为线性函数:用 \(\lambda\) 替换 \(I_\_(u)\),用 \(v\) 替换 \(I_0(u)\)。当 \(f_i(x)=0\) 时,我们的“不满意度”为零,随着 \(f_i(x)\) 越来越大,我们也越来越“不满意”。

在原问题中,只要 \(f_i(x)\leq0\),它就是可以接受的。然而,在我们现在的对偶问题中,只有约束存在裕量,也就是 \(f_i(x)<0\) 时,我们才会对它“满意”。

对这个“裕量”更直观地理解是:一个线性函数只能充分逼近示性函数。线性函数只能看作示性函数的下估计,也就是永远小于或者等于示性函数,这就是为什么对偶问题是原问题的下界。

Slater 条件

强对偶是什么?弱对偶又是什么?

考虑最简单的最优化问题

\[\begin{array}{ll}{\mathop{\text{minimize}}\limits_{\boldsymbol{x}}}&f_0(x)\\\text{subject to}&f_1(x)\leq0\end{array}\]

其最优值为

\[p^*=\inf\left\{f_0(x)\mid f_1(x)\leq0 \right\}\]

我们把它换成集合的写法

\[G=\left\{(f_1(x),f_0(x)) \right\}\\ p^*=\inf\left\{t\mid (u,t)\in G,u\leq0 \right\}\]

上面的这一坨玩意儿扔进二维坐标系是这样的

dual1

在上图中,由于 \(u\leq0\),所以我们只考虑第二和第三象限,然后找到阴影部分 \(t\) 的最小值,也就是 \(p^*\)。

我们把这个式子再变一变

\(g(\lambda)=\inf\left\{\lambda u+t\mid u,t\in G,\lambda\geq0 \right\}\) 也就是一根直线 \(t=-\lambda u+g(\lambda)\)。需要注意的是,这里 \(u\) 不再需要约束条件。

而对于这根直线,\(-\lambda\) 也就是斜率的变化会导致截距 \(g(\lambda)\) 的变化。对于固定的 \(\lambda\),\(g(\lambda)\) 最小化表现为与图形的下边界相切。

在二维坐标系里是这样的

dual2

但我们发现,得到的截距与 \(p^*\),仍有一段距离,我们希望缩短这个距离,使得求解对偶问题得到的结果与原问题的解尽量接近。因此,我们变动 \(\lambda\),去寻找最大的那个 \(g(\lambda)\)。从图中来看,也就是和两个角都相切的情况。

dual3

这时,\(g(\lambda^*)\) 和 \(p^*\) 的距离就是对偶间隙。

如此一来,我们画个图就能理解为什么凸问题的对偶间隙一定为 0 了。

dual4

由上可知,凸集一定能得到强对偶,这便是 Slater 条件。

对于更加一般的问题

\[\begin{array}{lll}{\mathop{\text{minimize}}\limits_{\boldsymbol{x}}}&f_0(x)\\\text{subject to}&f_i(x)\leq0&i=1,\cdots,m \\&h_i(x)=0&i=1,\cdots,p \end{array}\]

我们同样的做法,能够得到

\[\begin{array}{lll}p^*&=&\inf\left\{t\mid (u,v,t)\in G,u\leq0,v=0 \right\}\\ &\geq&\inf\left\{(\lambda,v,1)^T(u,v,t)\mid (u,v,t)\in G,u\leq0,v=0 \right\}\\ &\geq&\inf\left\{(\lambda,v,1)^T(u,v,t)\mid (u,v,t)\in G \right\}\\ &=&g(\lambda,v) \end{array}\]

KKT 条件

上面,我们知道了凸集是强对偶的充分不必要条件,那么为什么不必要呢?

dual5

如图,这不是一个凸集,却也是强对偶。这时,我们需要使用 KKT 条件来处理这个问题。

我们换种角度来思考。我们把寻找最优解的过程看作从一个点出发,不断向外扩张的椭球(二位情况下为椭圆)。

dual6

显然,在只有 1 个约束的条件下,相切时能够取到最优值。此时,切点处的偏导数应当成倍数关系。也就是

\[\nabla f_0(x^*)=\lambda_1\nabla f_1(x^*)\]

dual7

这当中,\(\nabla f_1(x^*)\) 是有方向的,指向 \(f_1(x)\leq0\) 的区域。而 \(\nabla f_0(x^*)\) 也需要指向这个区域,故 \(\lambda_1\geq0\)。

如果有多个不等式约束,则会有 \(f_0(x^*)\) 的偏导可以被 \(f_i(x^*)\) 的偏导线性表示。即

\[\nabla f_0(x^*)=\sum\lambda_i\nabla f_i(x^*)\]

dual8

与一个不等式的情况相同,\(f_0(x^*)\) 位于 \(f_i(x^*)\) 这组成的超角锥内,所以里也需要 \(\lambda_i\geq0\)。

这便是 KKT 条件的第一和第三个条件。

Comments

Share This Post