形式陈述

考虑原问题

$$ \begin{aligned} \min_x\quad & f_0(x)\\ \text{s.t.}\quad & f_i(x)\le0\ (i=1,\ldots,m),\\ & h_j(x)=0\ (j=1,\ldots,p). \end{aligned} $$$$\begin{array}{rl}\underset{x}{min}& f_0(x)\\ \text{s.t.}& f_i(x)\le 0(i=1,\dots ,m),\\ & h_j(x)=0(j=1,\dots ,p).\end{array}$$

其 Lagrange 函数为

$$ L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^m\lambda_i f_i(x)+\sum_{j=1}^p\nu_jh_j(x), \qquad \lambda\ge0, $$$$L(x,\lambda ,\nu )=f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{j=1}^p{\nu }_j{h}_j(x),\lambda \ge 0,$$

对偶函数

$$ g(\lambda,\nu)=\inf_xL(x,\lambda,\nu) $$$$g(\lambda ,\nu )=\underset{x}{inf}L(x,\lambda ,\nu )$$

对任意对偶可行 $(\lambda,\nu)$$(\lambda ,\nu )$ 都给出原最优值 $p^*$$p^{\ast }$ 的下界。因此对偶问题 $\max_{\lambda\ge0,\nu}g(\lambda,\nu)$$\underset{\lambda \ge 0,\nu }{max}g(\lambda ,\nu )$ 的最优值 $d^*$$d^{\ast }$ 总满足弱对偶 $d^*\le p^*$$d^{\ast }\le p^{\ast }$。对凸原问题，若满足 Slater 条件等约束资格，通常有强对偶 $d^*=p^*$$d^{\ast }=p^{\ast }$，并可由 KKT 条件刻画最优解。

直觉

非负乘子给违反不等式约束的点加罚。对所有 $x$$x$ 取最小后得到一个无论原问题多难都不会超过原最优值的证书；再选择最好的乘子，就是寻找最紧下界。

例子与边界

线性规划在适当可行/有界条件下具有强对偶。凸问题也可能因约束资格失败出现对偶间隙或对偶最优不取到；强对偶不是“只要凸就自动成立”。非凸问题仍有弱对偶，但对偶间隙可能很大。乘子必须满足 $\lambda_i\ge0$${\lambda }_i\ge 0$，否则对原可行点无法保证 $L(x,\lambda,\nu)\le f_0(x)$$L(x,\lambda ,\nu )\le f_0(x)$。对偶函数总是关于 $(\lambda,\nu)$$(\lambda ,\nu )$ 的凹函数，即使原问题非凸。Lagrange 对偶与仅用于光滑等式约束的经典乘子法相关，但量词和目的不同。

推论与应用

对偶变量可解释为资源的影子价格；对偶证书用于最优性验证、松弛组合问题、分解大型优化和推导支持向量机等模型。

参考资料

• Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004，Ch. 5, Lagrange duality, Slater condition and KKT conditions。
• R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press, 1970，§§28–31, conjugacy, duality and saddle points。