理解什么是对偶函数、对偶问题、强弱对偶、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\}\]上面的这一坨玩意儿扔进二维坐标系是这样的
在上图中，由于 \(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 条件
上面，我们知道了凸集是强对偶的充分不必要条件，那么为什么不必要呢？
如图，这不是一个凸集，却也是强对偶。这时，我们需要使用 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 条件的第一和第三个条件。
Comments