KNOWECON WIKI

ARTICLE

Karush-Kuhn-Tucker (KKT) conditions

Karush-Kuhn-Tucker (KKT) 条件 Karush-Kuhn-Tucker (KKT) 条件是非线性规划中一阶必要最优性条件的核心结果，在适当的正则性条件（约束规范）下，一个可行点若是局部极小点则必须满足这组条件。KKT 条件将经典拉格朗日乘数法——仅处理等式约束——推广到同时包含不等式约束的情形，构成了现代最优化理论与凸优化的基石。历史上

浏览 0 更新 2025-10-26

Karush-Kuhn-Tucker (KKT) 条件

Karush-Kuhn-Tucker (KKT) 条件是非线性规划中一阶必要最优性条件的核心结果，在适当的正则性条件（约束规范）下，一个可行点若是局部极小点则必须满足这组条件。KKT 条件将经典拉格朗日乘数法——仅处理等式约束——推广到同时包含不等式约束的情形，构成了现代最优化理论与凸优化的基石。历史上，这组条件由 William Karush 在 1939 年的硕士论文中首次提出，随后由 Harold W. Kuhn 和 Albert W. Tucker 在 1951 年的经典论文中独立重新发现并大幅拓展；在 Karush 的优先贡献被学界承认之前，条件长期被称为 Kuhn-Tucker 条件。

标准问题形式

考虑如下一般非线性规划问题 (NLP)：

min⁡xf(x)s.t.gi(x)≤0,i=1,…,mhj(x)=0,j=1,…,p\begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_i(\mathbf{x}) \le 0, \quad i = 1, \ldots, m \\ & h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p \end{aligned}

其中 x∈Rn\mathbf{x} \in \mathbb{R}^n 为决策向量，f:Rn→Rf : \mathbb{R}^n \to \mathbb{R} 为目标函数，gig_i 为不等式约束函数，hjh_j 为等式约束函数。所有函数均假设为连续可微 (C1C^1)。可行域记为 F={x∣gi(x)≤0,  hj(x)=0}\mathcal{F} = \{\mathbf{x} \mid g_i(\mathbf{x}) \le 0,\; h_j(\mathbf{x}) = 0\}。

拉格朗日函数与四个KKT条件

对于上述问题，引入对应于不等式约束的乘子向量 μ∈Rm\boldsymbol{\mu} \in \mathbb{R}^m 和等式约束的乘子向量 λ∈Rp\boldsymbol{\lambda} \in \mathbb{R}^p，定义拉格朗日函数：

L(x,μ,λ)=f(x)+∑i=1mμigi(x)+∑j=1pλjhj(x)\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^m \mu_i g_i(\mathbf{x}) + \sum_{j=1}^p \lambda_j h_j(\mathbf{x})

若 x∗\mathbf{x}^* 是局部极小点且合适的约束规范成立，则存在乘子 μ∗,λ∗\boldsymbol{\mu}^*, \boldsymbol{\lambda}^* 满足以下四个条件：

1. 稳定性条件 (Stationarity)

∇xL(x∗,μ∗,λ∗)=∇f(x∗)+∑i=1mμi∗∇gi(x∗)+∑j=1pλj∗∇hj(x∗)=0\nabla_{\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\mu}^*, \boldsymbol{\lambda}^*) = \nabla f(\mathbf{x}^*) + \sum_{i=1}^m \mu_i^* \nabla g_i(\mathbf{x}^*) + \sum_{j=1}^p \lambda_j^* \nabla h_j(\mathbf{x}^*) = \mathbf{0}

该条件要求目标函数在最优点的梯度可以表达为活跃约束梯度的线性组合，乘子即为组合系数。从几何上看，∇f\nabla f 必须落入约束梯度所张成的锥中。直观含义是：在最优处，任何可行方向上的方向导数均非负，目标函数已无法通过局部移动进一步改善。

2. 原始可行性 (Primal Feasibility)

gi(x∗)≤0,i=1,…,m;hj(x∗)=0,j=1,…,pg_i(\mathbf{x}^*) \le 0,\quad i = 1, \ldots, m; \qquad h_j(\mathbf{x}^*) = 0,\quad j = 1, \ldots, p

候选点必须满足所有原始约束。这是显然的要求，但作为 KKT 条件的一部分单独列出以确保完备性。

3. 对偶可行性 (Dual Feasibility)

μi∗≥0,i=1,…,m\mu_i^* \ge 0, \quad i = 1, \ldots, m

不等式约束的乘子必须非负。等式约束的乘子 λj∗\lambda_j^* 符号不受限制，因此不包含在此条件内。非负性要求反映了：放松一个 ≤\le 约束只能改善（或不恶化）目标值——若乘子为负，则意味着收紧约束反而能改善目标，这与极小化问题的逻辑矛盾。在最优化经济学中，这对应于影子价格的非负性。

4. 互补松弛性 (Complementary Slackness)

μi∗ gi(x∗)=0,i=1,…,m\mu_i^* \, g_i(\mathbf{x}^*) = 0, \quad i = 1, \ldots, m

对每个不等式约束 ii，要么约束在解处活跃 (gi(x∗)=0g_i(\mathbf{x}^*) = 0)，要么对应的乘子为零 (μi∗=0\mu_i^* = 0)，或两者同时成立。非活跃约束 (gi(x∗)<0g_i(\mathbf{x}^*) < 0) 在最优点附近不产生约束力，因此对应的乘子权重为零。互补松弛性是不等式约束下最优条件的核心：它精确地刻画了「只有绑定约束才有边际影响力」这一经济直觉。

四条条件合称KKT 系统。

约束规范 (Constraint Qualifications)

KKT 条件仅在合适的约束规范 (CQ) 下才是必要的。若缺乏 CQ，一个极小点可能根本不满足 KKT 条件。常见的约束规范按强度递减排布如下：

  • 线性独立约束规范 (LICQ): 在 x∗\mathbf{x}^* 处，所有活跃约束（包括等式约束和绑定的不等式约束）的梯度线性独立。LICQ 是最强的标准 CQ，且保证乘子的唯一性。
  • Mangasarian-Fromovitz 约束规范 (MFCQ): 等式约束的梯度线性独立，且存在向量 d\mathbf{d} 使得对所有活跃不等式约束有 ∇gi(x∗)⊤d<0\nabla g_i(\mathbf{x}^*)^\top \mathbf{d} < 0，同时对等式约束有 ∇hj(x∗)⊤d=0\nabla h_j(\mathbf{x}^*)^\top \mathbf{d} = 0。MFCQ 弱于 LICQ 但足以保证乘子集合的有界性。
  • Slater 条件 (凸情形): 若问题是凸规划且存在严格可行点（所有 gi(x)<0g_i(\mathbf{x}) < 0），则 KKT 条件既必要又充分。Slater 条件是凸优化中最常用的约束规范，在对偶理论中起着关键作用。
  • Abadie 约束规范: 要求线性化可行锥等于真实的切锥，是最弱的几何性 CQ 之一。

这些约束规范的共同目标是排除边界上因约束函数不可微或梯度退化的病态行为，确保线性化近似能够捕捉真实的可行域局部几何。

充分性与凸性

对于凸规划——即 ff 和所有 gig_i 是凸函数且 hjh_j 是仿射函数——KKT 条件同时也是全局最优的充分条件：任何满足 KKT 的点即为全局极小点。证明直接依赖于拉格朗日函数的凸性和鞍点性质：当 f,gif, g_i 为凸且 μi∗≥0\mu_i^* \ge 0 时，L(⋅,μ∗,λ∗)\mathcal{L}(\cdot, \boldsymbol{\mu}^*, \boldsymbol{\lambda}^*) 是 x\mathbf{x} 的凸函数，稳定点即全局极小点。

对于非凸问题，KKT 条件仅为必要条件（在 CQ 下），而非充分条件：满足 KKT 的点可能是鞍点甚至局部极大点。此时需借助二阶条件 (Second-Order Conditions) 加以区分。标准的二阶充分条件 (SOSC) 要求拉格朗日函数的 Hessian 矩阵在由活跃约束定义的临界锥上正定。若 Hessian 在临界锥上既有正曲率方向又有负曲率方向，则该点确为鞍点——这在双曲抛物面等高维鞍点结构的分析中尤为常见。

经济学解释：影子价格

在经济学与运筹学中，KKT 乘子具有深刻的影子价格 (shadow price) 含义。乘子 μi∗\mu_i^* 表示将第 ii 个约束的右端项从 00 扰动到 ε\varepsilon 时，最优目标值的边际变化率：

μi∗≈−∂f∗∂bi\mu_i^* \approx -\frac{\partial f^*}{\partial b_i}

即 μi∗\mu_i^* 回答：「若允许轻微违反第 ii 个约束，最小成本将下降多少？」对偶可行性 μi∗≥0\mu_i^* \ge 0 正是放松约束不会使成本上升这一直觉的形式化。互补松弛性则对应另一层面：未被充分利用的资源（即 gi(x∗)<0g_i(\mathbf{x}^*) < 0 的松弛约束）其影子价格为零——多一单位非绑定资源的边际价值为零。

这一框架在经济分析中的应用极为广泛：在消费者理论的效用最大化问题中，预算约束的乘子等于收入的边际效用；在成本最小化问题中，产出目标的乘子即为边际成本；在一般均衡与福利经济学中，KKT 乘子支撑了两大福利定理——竞争性均衡价格恰好对应社会计划者资源约束的乘子。KKT 条件也因此成为连接帕累托最优与市场价格体系的数学桥梁。

与对偶理论的关系

KKT 条件是连接原始问题与对偶问题的枢纽。定义拉格朗日对偶函数：

q(μ,λ)=inf⁡xL(x,μ,λ)q(\boldsymbol{\mu}, \boldsymbol{\lambda}) = \inf_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda})

对偶问题最大化 qq 并受限于 μ≥0\boldsymbol{\mu} \ge \mathbf{0}。在凸性和约束规范（如 Slater 条件）下，强对偶性成立：原始最优值等于对偶最优值，且 KKT 条件精准刻画原始-对偶最优对 (x∗,μ∗,λ∗)(\mathbf{x}^*, \boldsymbol{\mu}^*, \boldsymbol{\lambda}^*)。此时 x∗\mathbf{x}^* 在给定最优乘子下最小化拉格朗日函数，乘子在给定 x∗\mathbf{x}^* 下最大化对偶函数。KKT 系统由此编码了鞍点性质：

L(x∗,μ,λ)≤L(x∗,μ∗,λ∗)≤L(x,μ∗,λ∗)\mathcal{L}(\mathbf{x}^*, \boldsymbol{\mu}, \boldsymbol{\lambda}) \le \mathcal{L}(\mathbf{x}^*, \boldsymbol{\mu}^*, \boldsymbol{\lambda}^*) \le \mathcal{L}(\mathbf{x}, \boldsymbol{\mu}^*, \boldsymbol{\lambda}^*)

对任意可行 x\mathbf{x} 和 μ≥0\boldsymbol{\mu} \ge \mathbf{0} 成立。现代凸优化中的内点法 (interior-point methods) 本质上就是通过扰动互补松弛条件 μigi(x)=−τ\mu_i g_i(\mathbf{x}) = -\tau 并沿中心路径追踪来求解 KKT 系统的算法族。

计算示例

考虑如下二维非线性规划：

min⁡x1,x2(x1−2)2+(x2−1)2s.t.x1+x2≤2x12−x2≤0\begin{aligned} \min_{x_1, x_2} \quad & (x_1 - 2)^2 + (x_2 - 1)^2 \\ \text{s.t.} \quad & x_1 + x_2 \le 2 \\ & x_1^2 - x_2 \le 0 \end{aligned}

构建拉格朗日函数 L=(x1−2)2+(x2−1)2+μ1(x1+x2−2)+μ2(x12−x2)\mathcal{L} = (x_1-2)^2 + (x_2-1)^2 + \mu_1(x_1+x_2-2) + \mu_2(x_1^2 - x_2)。稳定性条件给出：

2(x1−2)+μ1+2μ2x1=0,2(x2−1)+μ1−μ2=02(x_1 - 2) + \mu_1 + 2\mu_2 x_1 = 0, \quad 2(x_2 - 1) + \mu_1 - \mu_2 = 0

结合 μ1≥0,μ2≥0\mu_1 \ge 0, \mu_2 \ge 0，x1+x2≤2x_1+x_2 \le 2，x12−x2≤0x_1^2-x_2 \le 0，以及互补松弛条件 μ1(x1+x2−2)=0\mu_1(x_1+x_2-2)=0、μ2(x12−x2)=0\mu_2(x_1^2-x_2)=0，通过枚举活跃约束组合求解。解为 (x1,x2)=(1,1)(x_1, x_2) = (1, 1)，对应 μ1=0,μ2=2\mu_1 = 0, \mu_2 = 2：第一个约束松弛（影子价格为零），第二个约束绑定且其影子价格为 2。目标函数为凸函数（正定二次型），约束函数中 x12−x2x_1^2-x_2 为凸，因此 KKT 条件也是充分的，(1,1)(1,1) 为全局极小点。

历史注记

William Karush 在芝加哥大学攻读硕士期间，于 1939 年在论文 Minima of Functions of Several Variables with Inequalities as Side Conditions 中首次推导了这组条件，但当时未引起广泛关注。1951 年，Harold W. Kuhn 与 Albert W. Tucker 在第二届伯克利研讨会论文 Nonlinear Programming 中独立重新发现并系统扩展了该理论。1976 年 Kuhn 发表历史注记确认了 Karush 的贡献，至 20 世纪 80 年代「KKT」三名并称成为优化文献的标准用法。Albert W. Tucker 亦是囚徒困境的命名者和博弈论早期发展的重要人物，KKT 条件与博弈论中纳什均衡的一阶刻画存在深刻的数学联系。

参见

  • 拉格朗日乘数法——仅含等式约束的特殊情形
  • 凸优化——KKT 条件充分性成立的优化问题类
  • Slater 条件——凸情形下的关键约束规范
  • Fritz John 条件——通过在目标函数梯度上引入额外乘子来规避约束规范要求，但实用性较弱
  • 内点法——求解扰动 KKT 系统的数值算法族
  • 对偶理论——强对偶性与 KKT 条件的等价关系
  • 影子价格——乘子的经济学含义