拉格朗日对偶

带约束的最小化问题不只可以从“可行点”看，也可以从“下界”看。对 $$\underset{x}{min}{f}_0(x)\text{使 }{f}_i(x)\le 0,h_j(x)=0,$$ 定义拉格朗日函数 $L(x,\lambda ,\nu )=f_0(x)+\sum _i{\lambda }_i{f}_i(x)+\sum _j{\nu }_j{h}_j(x)$，其中不等式乘子 ${\lambda }_i\ge 0$。对偶函数是 $g(\lambda ,\nu )=\underset{x}{inf}L(x,\lambda ,\nu )$。

下界从哪里来

若 $x$ 可行，则 $f_i(x)\le 0$、$h_j(x)=0$，故 $L(x,\lambda ,\nu )\le f_0(x)$。又有 $g(\lambda ,\nu )\le L(x,\lambda ,\nu )$，所以每个非负乘子给原最优值一个下界。把下界尽量抬高，就是对偶问题 $\underset{\lambda \ge 0,\nu }{max}g(\lambda ,\nu )$。这一弱对偶结论不要求原问题凸。

一个可算的下界

最小化 $x^2$，约束 $x\ge 1$，即 $1-x\le 0$。原最优点是 $x^{\ast }=1$，最优值为 1。拉格朗日函数 $L(x,\lambda )=x^2+\lambda (1-x)$，对 $x$ 配方： $$g(\lambda )=\underset{x}{inf}L(x,\lambda )=\lambda -\frac{{\lambda }^2}{4},\lambda \ge 0.$$ 此抛物线在 $\lambda =2$ 达到最大值 1，恰与原最优值相等。对一般问题，原最优值与对偶最优值之间可能有对偶间隙；凸性及约束资格条件（如 Slater 条件）可保证强对偶，不能仅凭写出乘子就认定二者相等。

参考资料

• Boyd 与 Vandenberghe，Convex Optimization，第 5 章。
• MIT 6.079，凸优化讲义。
• 继续阅读：KKT条件、拉格朗日乘数法、凸函数。