证明凸函数（透彻理解凸优化中的对偶与KKT条件）

本文通过非常简洁和形象的方式说明解释凸优化中的对偶理论和KKT条件，并回答以下问题：

1、 对偶问题是如何解决原始问题的？

2、 什么是弱对偶？什么强对偶？

3、 强对偶的条件是什么？

4、 KKT条件与对偶的关系是怎么样的？

5、 KKT条件的必要性和充分性。

拉格朗日对偶

给定一个非线性规划问题，称为原始问题，存在另一个与之非常相关的非线性规划问题，就是拉格朗日对偶问题。为什么引入拉格朗日对偶？当原始问题不方便解决，特别是有不等式约束时，往往不便用函数微分方式处理，也就是不方便使用一阶、二阶导数来求解问题，我们用拉格朗日对偶就能很容易的解决。

在凸函数和适当的约束条件下，原始和对偶问题具有相同的最优目标值。

我们step by step来逐步分析：

原始问题：

对偶问题：

为了更形象直观，我们作一个变换，把f(x)映

射到z轴，把g(x)映射到y轴，变换后的区域如下图所示：

按照原始问题，我们要找符合约束的目标值的最小值，也就是在y<=0时的z的最小值。这样转化之后原来的不等式约束，就变得非常简单了，很明显图示红点就是符合要求的最小值。

现在看对偶问题是怎么求解目标的，先看z+uy的最小值，在变换后的坐标体系中，z+uy约束下求最值是线性规划问题，也就是求直线α=z+uy在与G区域保持接触的前提下，在z轴的截距的最小值。所以，我们假定u是一个常数，因为θ(u)是关于u的函数，现在在G区域平行移动直线，移动方向是（-u,-1）,如图所示。

现在看到与G区域相切的直线能够使截距最小，但是，注意我们刚才在移动的过程中，把u当作常数，也就是说，对于一个固定的直线（u为常数），移动该直线使之滑过G区域，目标是在Z轴截距最小，就是要使该直线与G区域左下方边缘相切。而对偶问题：

是关于u的，要求θ(u)的最大值，也就是斜率是变量，刚才我们对直线α=z+uy是平移，现在要旋转，旋转的目标是求截距的最大值。

刚才一会求最小，一会儿求最大，有的人可能就晕乎了，我们现在总结如下：

1、 对于某直线平移，此时自变量是原问题的变量，使之与Z轴的截距是最小的，这个确保是在G区域左下边缘找切线。

2、 现在有一个直线簇，就是1中直线的集合(斜率变化)，此时变量是对偶问题的变量；

3、 在这个直线簇中，找到截距最大的。

最后，我们看到，对偶问题和原始问题一样，目标点也是

。

以上我们看到，对偶问题和原始问题的解一样，我们把这种对偶叫做强对偶。

注意到，由于集合G的非凸性，对偶问题的解和原始问题的解有一个差距，就是对偶间隙（duality gap）。

对偶间隙

现在通过数学推导证明对偶间隙：

设原始问题：

对偶问题：

针对原问题的拉格朗日函数为：

对偶问题与拉格朗日函数的关系是：

我们有重要结论：

证明如下：

叫做对偶间隙（duality gap）

由下确界性质，设p*

为原问题的最优解，那么

我们把对偶问题的最优解记为d*

叫最优对偶间隙，如果强对偶，则有d*=p*

Slater条件，如果原问题是严格可行，且是凸问题，那么有

限于篇幅本文不给出slater条件的证明，这个证明过程是比较复杂，而且很有逻辑的，后边专门发文讲解。

KKT条件

假定

分别是原始问题、对偶问题的解，并且对偶问题是强对偶，那么

解释一下这个证明过程，第二个等号，是因为我们的对偶问题的最优目标值就是拉格朗日函数最小值（下确界），小于等于号，是因为最优解时的目标值一定不小于关于x的下确界。

所以有

这就是KKT条件中非常著名的互补松弛条件；

接下来，根据互补松弛条件，我们有

也就是说，x*

是拉格朗日函数的最小值时的解。所以有：

这就是KKT条件中的稳定性条件。

这两个条件再加上原问题、对偶问题的可行性，我们就得到KKT条件：

KKT条件的充分性：

如果

满足KKT条件，那么它们就分别是原始问题和对偶问题的解。

总结：

（1） 总是充分的;

（2） 在强对偶条件下， 是必要的。