拉格朗日对偶性

原始问题

​ 假设$f(x), c_i(x), h_j(x)$是定义在$R^n$上面的连续可微函数,考虑约束最优化问题

​ 称此约束最优化问题为原始最优化问题或原始问题。

​ 首先,引进广义拉格朗日函数

​ 这里,$\alpha_i,\beta_j$是拉格朗日乘子,$\alpha_i\ge0$.

​ 考虑函数(注意:此时$L(x,\alpha,\beta)$的变量是$\alpha_i\beta_j$):

​ 这里下标$P(Primal)$表示原始问题.对于此函数(关于$\alpha,\beta$的函数,$x$是常量),经过我们优化(不管什么方法),确定$\alpha,\beta$的值,就可以得到$L(x,\alpha,\beta)$的最大值,因为此时$\alpha,\beta$已经确定,显然最大值就是只和$x$有关的函数

​ 下面通过$x$是否绵竹约束条件两方面来分析这个函数:

​ 1.考虑某个$x$违反了原始的约束,即$c_i\gt0$或者$h_j\neq0$,那么:

​ 2.考虑$x$满足原始的约束,则:

​ 注意最大化确定$\alpha,\beta$的过程,$f(x)$就是个常量,常量的最大值显然是本身

​ 通过上面两条分析可以得出:

​ 那么在满足约束的条件下:

​ 即$\min_x\Theta_P(x)$与原始优化问题等价,所以常用$\min_x\Theta_P(x)$来代表原始问题,定义原始问题的最优值:

​ 原始问题讨论到这里,总结:重新定义一个无约束问题,这个无约束问题等价于原来的约束优化问题。

对偶问题

​ 定义关于$\alpha,\beta$的函数

​ 注意上面等式右边是关于$x$的函数最小化,$x$确定之后,最小值就只与$\alpha,\beta$有关,所以此时是一个关于$\alpha,\beta$的函数

​ 再考虑极大化$\Theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta)$,即:

​ 这就是原始问题的对偶问题,再将原始问题写出来:

​ 从形式上可以看出堆成,只不过原始问题先固定$L(x,\alpha,\beta)$中的$x$,优化参数$\alpha,\beta$,再优化$x$;而对偶问题是先固定$\alpha,\beta$,再优化$x$,然后再确定参数$\alpha,\beta$

​ 定义对偶问题的最优值:

原始问题与对偶问题之间的关系

​ 若原始问题和对偶问题都有最优值,则有$Min-Max$不等式:

​ 当$L(x,\alpha,\beta)$对$x$为凸函数,对$\alpha,\beta$为凹函数,以上等号成立。而$L(x,\alpha,\beta)$对$\alpha,\beta$为天然凹函数,因此只要$L(x,\alpha,\beta)$对$x$为凸函数,等号便成立

​ 证明:一个式子的最大值永远大于等于这个式子的最小值,哪怕是这个式子最小的最大值与最大的最小值相比(瘦死的骆驼比马大)。

0%