KNOWECON WIKI

ARTICLE

Karush-Kuhn-Tucker (KKT) 条件

Karush-Kuhn-Tucker (KKT) 条件 Karush-Kuhn-Tucker 条件（简称 KKT 条件）是非线性规划中带有等式和不等式约束的最优化问题的一阶必要条件，由 Karush（1939）、Kuhn 与 Tucker（1951）独立提出。KKT 条件将经典的拉格朗日乘子方法从等式约束推广到不等式约束情形，是现代最优化理论、凸优化和机器学

浏览 0 更新 2025-07-11

Karush-Kuhn-Tucker (KKT) 条件

Karush-Kuhn-Tucker 条件（简称 KKT 条件）是非线性规划中带有等式和不等式约束的最优化问题的一阶必要条件，由 Karush（1939）、Kuhn 与 Tucker（1951）独立提出。KKT 条件将经典的拉格朗日乘子方法从等式约束推广到不等式约束情形，是现代最优化理论、凸优化和机器学习算法分析的基石。

问题的标准形式

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

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}) \leq 0, \quad i = 1, \ldots, m \\ & h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p \end{aligned}

其中 f,gi,hj:Rn→Rf, g_i, h_j: \mathbb{R}^n \to \mathbb{R} 均为连续可微函数。定义该问题的拉格朗日函数为：

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

其中 λi≥0\lambda_i \geq 0 为不等式约束对应的KKT 乘子（对偶变量），μj∈R\mu_j \in \mathbb{R} 为等式约束对应的乘子。

KKT 条件的四个组成部分

设 x∗\mathbf{x}^* 为局部最优解，且在 x∗\mathbf{x}^* 处某个适当的约束品性成立，则存在乘子 λ∗,μ∗\boldsymbol{\lambda}^*, \boldsymbol{\mu}^* 使以下条件同时成立：

1. 驻点条件 (Stationarity)

∇f(x∗)+∑i=1mλi∗∇gi(x∗)+∑j=1pμj∗∇hj(x∗)=0\nabla f(\mathbf{x}^*) + \sum_{i=1}^{m} \lambda_i^* \nabla g_i(\mathbf{x}^*) + \sum_{j=1}^{p} \mu_j^* \nabla h_j(\mathbf{x}^*) = \mathbf{0}

拉格朗日函数在 x∗\mathbf{x}^* 处的梯度为零向量。这表示目标函数的负梯度落在所有紧约束梯度的锥中——最优解处不存在可使目标下降的可行方向。

2. 原始可行性 (Primal Feasibility)

gi(x∗)≤0,hj(x∗)=0,∀i,jg_i(\mathbf{x}^*) \leq 0, \quad h_j(\mathbf{x}^*) = 0, \quad \forall i, j

即 x∗\mathbf{x}^* 本身必须是可行解，满足所有约束。

3. 对偶可行性 (Dual Feasibility)

λi∗≥0,∀i=1,…,m\lambda_i^* \geq 0, \quad \forall i = 1, \ldots, m

不等式约束的乘子必须非负。其几何含义是：只有"阻碍"目标函数减小的约束（即紧约束）才能产生非零乘子；若约束是松弛的，乘子必为零。

4. 互补松弛条件 (Complementary Slackness)

λi∗ gi(x∗)=0,∀i=1,…,m\lambda_i^* \, g_i(\mathbf{x}^*) = 0, \quad \forall i = 1, \ldots, m

这是 KKT 条件中最具特色的部分：对于每一个不等式约束，乘子与约束函数值至少有一个为零。若 gi(x∗)<0g_i(\mathbf{x}^*) < 0（约束松弛），则 λi∗=0\lambda_i^* = 0；若 λi∗>0\lambda_i^* > 0，则必须 gi(x∗)=0g_i(\mathbf{x}^*) = 0（约束紧）。这与对偶理论中的互补松弛条件一脉相承。

约束品性

KKT 条件成立需要满足约束品性（Constraint Qualification），它排除了约束梯度在 x∗\mathbf{x}^* 处出现"病态"退化的情形。常见的约束品性包括：

  • 线性独立约束品性 (LICQ)：所有紧约束（含全部等式约束）的梯度在 x∗\mathbf{x}^* 处线性无关。
  • Mangasarian-Fromovitz 约束品性 (MFCQ)：紧不等式约束的梯度正线性无关，且等式约束的梯度线性无关。
  • Slater 条件：对于凸问题，若存在严格可行点使所有不等式约束严格成立，则 KKT 条件既必要又充分。

凸规划下的充分性

当原始问题是凸规划时（即 ff 为凸函数，gig_i 为凸函数，hjh_j 为仿射函数），KKT 条件不仅是局部最优解的必要条件，也是全局最优解的充分条件：任何满足 KKT 条件的可行点 x∗\mathbf{x}^* 必然是全局最优解。这一性质使 KKT 条件在支持向量机 (SVM)、凸优化、最优控制等领域成为寻找全局最优解的核心工具。

经济学解释

在经济优化问题中，KKT 乘子 λi∗\lambda_i^* 衡量第 ii 个约束的影子价格：约束每放松一个边际单位，目标函数最优值的改善量。互补松弛条件的经济含义是：若某资源未完全耗尽（约束松弛），其影子价格为零；若影子价格为正，该资源必被完全耗尽（约束紧）。这一结构支撑着资源配置、一般均衡和机制设计中的大量边际分析。

应用场景

  1. 支持向量机：SVM 的对偶推导完全依赖 KKT 条件，互补松弛条件直接导出支持向量的概念——只有位于分类边界上的样本点才对应非零乘子。
  2. 不等式约束优化：在投资组合优化、生产计划、网络流量分配等存在非负约束或上限约束的问题中，KKT 条件是刻画最优解的标准语言。
  3. 最优控制：Pontryagin 最大值原理可视作无穷维空间中的 KKT 条件。
  4. 博弈论：纳什均衡的一阶条件可表示为各玩家优化问题的 KKT 系统。
  5. 机器学习：带正则化项的损失函数最小化（如 Lasso、弹性网）的解析性质直接由 KKT 条件刻画。

KKT 条件将不等式约束优化的一阶刻画提升至系统化的数学高度，是连接优化理论、数值算法与应用领域的核心桥梁。