MathLabs
定理已证明

卡罗需–库恩–塔克条件

命题陈述

考虑问题 min⁡f(x)\min f(x)，约束为 gi(x)≤0 (i=1,…,m)g_i(x) \le 0\ (i=1,\dots,m) 与 hj(x)=0 (j=1,…,p)h_j(x)=0\ (j=1,\dots,p)，其中 f,gi,hjf, g_i, h_j 可微。若 x∗x^* 是满足某约束规范的局部极小点，则存在乘子 μi≥0\mu_i \ge 0、λj\lambda_j 使得：（平稳性）∇f(x∗)+∑iμi∇gi(x∗)+∑jλj∇hj(x∗)=0\nabla f(x^*) + \sum_i \mu_i \nabla g_i(x^*) + \sum_j \lambda_j \nabla h_j(x^*) = 0；（原始可行性）gi(x∗)≤0, hj(x∗)=0g_i(x^*)\le 0,\ h_j(x^*)=0；（对偶可行性）μi≥0\mu_i \ge 0；（互补松弛性）μigi(x∗)=0\mu_i g_i(x^*) = 0（对所有 ii）。对凸问题而言，这些条件也是全局最优的充分条件。

为什么成立?

在受约束的最优点处，任何微小的可行移动都无法改善目标函数。平稳性条件说明 ff 的梯度恰好被活跃约束梯度的非负组合抵消——该点被只能向内推的力（乘子）『钉』在可行域边界上。互补松弛性说明约束产生力（μi>0\mu_i>0）当且仅当它确实起作用（gi(x∗)=0g_i(x^*)=0）；松弛的约束不作贡献。

证明思路

在某个约束规范下（如活跃约束梯度线性无关，或凸问题的 Slater 条件），x∗x^* 处的可行方向集合与活跃约束的线性化锥重合。由于 x∗x^* 是局部极小点，∇f(x∗)\nabla f(x^*) 不能与任何可行方向有负内积，因此 −∇f(x∗)-\nabla f(x^*) 属于活跃约束梯度所生成的锥——这正是将法卡斯引理应用于线性化系统的结果，由此得到乘子 μi,λj\mu_i, \lambda_j。

用到此定理的主题

凸优化

相关定理

线性规划的强对偶定理凸函数的局部极小值即全局极小值

分步证明

该定理暂无分步证明。

参考文献

  1. Stephen Boyd, Lieven Vandenberghe (2004). Convex Optimization
  2. Mokhtar S. Bazaraa, Hanif D. Sherali, C. M. Shetty (2006). Nonlinear Programming: Theory and Algorithms