卡鲁什-库恩-塔克条件

卡鲁什-库恩-塔克条件 (Karush-Kuhn-Tucker Conditions)

卡鲁什-库恩-塔克条件（Karush-Kuhn-Tucker Conditions），常简称KKT条件，是非线性规划领域中用于判断一个解是否为最优解的一组一阶必要条件，是拉格朗日乘数法处理不等式约束的推广。在凸优化中（目标函数和不等式约束为凸函数、等式约束为仿射），KKT条件也是充分条件，满足KKT的可行点即全局最优解。条件最初由William Karush在1939年提出但未发表，直至1951年Harold W. Kuhn和Albert W. Tucker重新独立发现发表而得名。

约束优化问题的KKT框架

考虑标准非线性规划问题，目标为最小化 $f(x)$，约束于不等式约束 $g_i(x) \le 0$（$i = 1, \ldots, m$）和等式约束 $h_j(x) = 0$（$j = 1, \ldots, l$），所有函数连续可微。构建拉格朗日函数 $L(x, \mu, \lambda) = f(x) + \sum \mu_i g_i(x) + \sum \lambda_j h_j(x)$，其中 $\mu_i$ 和 $\lambda_j$ 为与不等式和等式约束对应的KKT乘数即对偶变量。

在局部最优解 $x^*$ 处满足某个约束规格（如LICQ，即有效约束梯度线性无关）的条件下，存在乘数 $\mu^*$ 和 $\lambda^*$ 使四点条件成立。

定常性：$\nabla f(x^*) + \sum \mu_i^* \nabla g_i(x^*) + \sum \lambda_j^* \nabla h_j(x^*) = 0$，在最优点目标函数梯度可表示为有效约束梯度的线性组合，是广义一阶最优性条件。

原始可行性：$g_i(x^*) \le 0$ 和 $h_j(x^*) = 0$。

对偶可行性：不等式约束的乘子满足 $\mu_i^* \ge 0$。因放宽约束即扩大可行域只能使最优值改好，乘子非负解释了影子价格概念：$\mu_i^*$ 衡量约束被稍微放宽时目标函数最优值的边际改善。

互补松弛性：乘积条件 $\mu_i^* g_i(x^*) = 0$（对所有i）。若约束松弛即不紧，$g_i(x^*) < 0$，则 $\mu_i^* = 0$，多余约束影子价格为零。若约束紧，$g_i(x^*) = 0$，则 $\mu_i^* > 0$ 可能成立，约束限制直接影响最优值。等式约束的乘子 $\lambda_j^*$ 符号不受限制。

经济学应用与意义

在微观经济学中，KKT条件是理解角点解和库恩-塔克条件下最优消费束的核心工具。离散选择问题中非负消费约束下，KKT条件指出达到角点解时对应非负约束的拉格朗日乘子为严格正。在金融工程的投资组合优化中，禁止卖空约束通过KKT条件处理。在机器学习的支持向量机（SVM）训练中，KKT条件是推导对偶问题和识别支持向量的理论基础，仅有对应约束紧（互补松弛条件中乘子大于0）的样本才影响决策边界，实现了稀疏性。KKT条件将最优解的必要信息浓缩于四点条件，是约束优化的统一理论框架，也是凸分析不可分割的组成部分。