机器学习——拉格朗日对偶

        拉格朗日对偶与凸优化、拉格朗日乘子、KKT条件有着密切的联系，KKT条件可以通过朗格朗日对偶推到得到。

        步入正题

原问题

对于一个不等式优化问题：

首先定义一个拉格朗日函数：

其中βi>=0

则根据原问题的约束条件h(x)=0，g(x)<=0可得：

将L(x,α,β)看作是α与β的函数，将x看作常量，求拉格朗日函数的最大值可得：

则求f(x)的最小值满足下式：

这也被称为拉格朗日函数的极小极大问题。

对偶问题

对于上面的拉格朗日函数：

        首先将α，β看做是常量，x看做变量，求在x上的极小值，如下：

        则上式是一个关于α，β的函数，函数的最小值只与α，β有关。

        然后在极大化θ(α,β)函数；

        上面就是原问题的对偶问题，也被称作拉格朗日函数的极大极小问题。

原问题与对偶问题的关系

分别看一下原问题与对偶问题的形式：

原问题是先将x看作常量，先优化α，β，再优化x

设p∗ 为原问题的最优解，对应最优解的最优变量取值为x∗ ：

设d∗为对偶问题的最优解，对应最优解的最优变量取值为α∗、β∗：

原问题与对偶问题的最优解并不相等，其满足下式：

可以直观的理解为，最大里的最小的要比最小里的最大的要大，证明如下：

这相当于给原问题求的一个下界。这个性质也称为弱对偶，对于所有的优化问题都成立，即使原问题是非凸的。与之对应的称为强对偶性，强对偶需要满足如下：

任何一个原问题（包括非凸问题）它的对偶问题一定是一个凸问题，利用这个特性可将非凸问题转化为凸问题。并且在强对偶成立的条件下通过求解对偶问题的优化解来求原问题的解。