| layout |
title |
date |
categories |
tags |
comments |
mathjax |
copyrights |
post |
对偶问题解释 |
2021-04-01 00:00:00 +0800 |
数学 |
optimization |
true |
true |
原创 |
理解什么是对偶函数、对偶问题、强弱对偶、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$$ 时，我们才会对它“满意”。
对这个“裕量”更直观地理解是：一个线性函数只能充分逼近示性函数。线性函数只能看作示性函数的下估计，也就是永远小于或者等于示性函数，这就是为什么对偶问题是原问题的下界。
强对偶是什么？弱对偶又是什么？
考虑最简单的最优化问题
$$
\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}
$$
上面的这一坨玩意儿扔进二维坐标系是这样的
在上图中，由于 $$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)$$ 最小化表现为与图形的下边界相切。
在二维坐标系里是这样的
但我们发现，得到的截距与 $$p^*$$，仍有一段距离，我们希望缩短这个距离，使得求解对偶问题得到的结果与原问题的解尽量接近。因此，我们变动 $$\lambda$$，去寻找最大的那个 $$g(\lambda)$$。从图中来看，也就是和两个角都相切的情况。
这时，$$g(\lambda^)$$ 和 $$p^$$ 的距离就是对偶间隙。
如此一来，我们画个图就能理解为什么凸问题的对偶间隙一定为 0 了。
由上可知，凸集一定能得到强对偶，这便是 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 条件来处理这个问题。
我们换种角度来思考。我们把寻找最优解的过程看作从一个点出发，不断向外扩张的椭球（二位情况下为椭圆）。
显然，在只有 1 个约束的条件下，相切时能够取到最优值。此时，切点处的偏导数应当成倍数关系。也就是
$$
\nabla f_0(x^)=\lambda_1\nabla f_1(x^)
$$
这当中，$$\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^)
$$
与一个不等式的情况相同，$$f_0(x^)$$ 位于 $$f_i(x^)$$ 这组成的超角锥内，所以里也需要 $$\lambda_i\geq0$$。
这便是 KKT 条件的第一和第三个条件。
