第4章：拉格朗日对偶与 KKT

从约束得到下界

对标准约束问题定义

L(x,\lambda,\nu)=f_0(x)+\sum_i\lambda_i f_i(x)+\nu^T(Ax-b),\qquad\lambda\ge0.

对可行 x，不等式项非正、等式项为零，因此 $L(x,\lambda,\nu)\le f_0(x)$ 。令 $g(\lambda,\nu)=\inf_xL(x,\lambda,\nu)$ ，便得到最优值的下界。

最大化这个下界是对偶问题。弱对偶 $d^*\le p^*$ 不需要原问题凸；强对偶则需要额外条件，不能由写出拉格朗日函数自动得到。

对适当的凸问题，若在公共定义域的相对内部存在满足等式、严格满足不等式的点，Slater 条件可保证强对偶等结论；标准有限最优值情形还保证相应对偶最优解存在。

严格可行条件是常用充分条件，不是所有问题强对偶的必要条件。带仿射不等式时还有较弱版本，使用时应核对具体定理。

在可微情形，KKT 包含原可行、对偶可行、互补松弛和驻点条件：

\lambda_i f_i(x)=0,\qquad \nabla f_0(x)+\sum_i\lambda_i\nabla f_i(x)+A^T\nu=0.

凸问题中，满足 KKT 的点是全局最优；在合适约束资格下，最优点也存在相应乘子满足 KKT。非凸问题中，驻点通常不能保证全局最优。

最小化 $\tfrac12(x-2)^2$ ，约束 $x\le1$ 。拉格朗日函数为 $L=\tfrac12(x-2)^2+\lambda(x-1)$ ，对 x 最小化得 $x=2-\lambda$ ，所以

g(\lambda)=\lambda-\frac12\lambda^2,\quad\lambda\ge0.

对偶最优为 $\lambda=1$ ，值为 $1/2$ ，原最优为 x=1，也为 $1/2$ 。KKT 驻点为 $x-2+\lambda=0$ ，约束活跃且互补松弛成立。

若把约束上界 b 稍微放宽，最优值局部变化率为 $-\lambda^*$ ，说明乘子可以表示放松资源约束的边际价值，但敏感性结论还需可微等条件。