一般 NLP 中的 KKT 条件、锥与约束资格条件

一般 NLP 中的 KKT 条件、锥与约束资格条件

问题形式与基本目标

考虑一般非线性规划问题

\[\begin{aligned} \min_{x\in\mathbb{R}^n}\quad & f(x)\\ \mathrm{s.t.}\quad & g_i(x)\le 0,\quad i=1,\dots,m,\\ & h_j(x)=0,\quad j=1,\dots,p, \end{aligned}\tag{1} \]

其中 \(f,g_i,h_j\) 在所讨论点附近可微。记可行集为

\[\Omega:=\{x\in\mathbb{R}^n:\ g_i(x)\le 0,\ i=1,\dots,m,\ h_j(x)=0,\ j=1,\dots,p\}.\tag{2} \]

对于给定可行点 \(x^*\in\Omega\)，记活动不等式指标集为

\[I(x^*):=\{i\in\{1,\dots,m\}: g_i(x^*)=0\}.\tag{3} \]

本文的目标是解释：

1. 局部极小点为什么应当满足 KKT 条件；
2. KKT 条件中的乘子从何而来；
3. 切锥、线性化锥、极锥与法锥在这一理论中扮演什么角色；
4. 为什么需要各种约束资格条件（constraint qualifications, CQ）。

---

切锥、线性化锥与极锥

定义 1 (Bouligand 切锥)
设 \(\Omega\subset\mathbb{R}^n\)，\(x\in \Omega\)。定义 \(\Omega\) 在 \(x\) 处的 Bouligand（或 contingent）切锥为

\[T_\Omega(x) := \left\{ d\in\mathbb{R}^n: \exists\, x^k\in \Omega,\ x^k\to x,\ \exists\, t_k\downarrow 0,\ \frac{x^k-x}{t_k}\to d \right\}.\tag{4} \]

定义 1 中的切锥描述的是可行集在点 \(x\) 处的真实一阶可行方向。

定义 2 (线性化锥)
对问题 (1)，其在可行点 \(x^*\) 处的线性化锥定义为

\[L_\Omega(x^*) := \Big\{ d\in\mathbb R^n: \nabla g_i(x^*)^\top d\le 0,\ i\in I(x^*),\ \nabla h_j(x^*)^\top d=0,\ j=1,\dots,p \Big\}.\tag{5} \]

定义 2 中的线性化锥表示把约束在 \(x^*\) 处作一阶线性化后得到的“近似可行方向锥”。

命题 1
对任意可行点 \(x^*\in\Omega\)，都有

\[T_\Omega(x^*)\subseteq L_\Omega(x^*).\tag{6} \]

证明
任取 \(d\in T_\Omega(x^*)\)。由定义 1，存在 \(x^k\in\Omega\) 与 \(t_k\downarrow 0\) 使

\[\frac{x^k-x^*}{t_k}\to d. \]

由于 \(x^k\) 可行，对任意 \(i\in I(x^*)\)，

\[g_i(x^k)\le 0,\qquad g_i(x^*)=0. \]

由 \(g_i\) 的可微性，

\[g_i(x^k)=g_i(x^*)+\nabla g_i(x^*)^\top(x^k-x^*)+o(\|x^k-x^*\|). \]

除以 \(t_k>0\) 并令 \(k\to\infty\)，得到

\[\nabla g_i(x^*)^\top d\le 0. \]

同理，由 \(h_j(x^k)=h_j(x^*)=0\) 及 \(h_j\) 的可微性可得

\[\nabla h_j(x^*)^\top d=0. \]

因此 \(d\in L_\Omega(x^*)\)，即 (6) 成立。∎

定义 3 (极锥)
对任意锥 \(K\subseteq\mathbb{R}^n\)，其极锥定义为

\[K^\circ:=\{v\in\mathbb{R}^n:\ \langle v,d\rangle\le 0,\ \forall d\in K\}.\tag{7} \]

定义 3 表明：锥 \(K\) 描述“可以走的方向”，而其极锥 \(K^\circ\) 描述“阻止这些方向的法向”。

---

Fréchet 正则法锥、Mordukhovich 法锥与 Clarke 法锥

定义 4 (Fréchet 正则法锥)
设 \(\Omega\subseteq\mathbb{R}^n\)，\(x\in\Omega\)。定义 Fréchet（regular）法锥为

\[\widehat N_\Omega(x) := \left\{ v\in\mathbb{R}^n: \limsup_{\substack{y\to x\\ y\in\Omega,\ y\neq x}} \frac{\langle v,\, y-x\rangle}{\|y-x\|}\le 0 \right\}.\tag{8} \]

命题 2
对任意集合 \(\Omega\subseteq\mathbb{R}^n\) 及任意 \(x\in\Omega\)，有

\[\widehat N_\Omega(x)=T_\Omega(x)^\circ.\tag{9} \]

证明
先证 “\(\subseteq\)”。任取 \(v\in \widehat N_\Omega(x)\) 与 \(d\in T_\Omega(x)\)。由定义 1，存在 \(y^k\in\Omega\) 与 \(t_k\downarrow 0\) 使

\[\frac{y^k-x}{t_k}\to d. \]

若 \(d\neq 0\)，则

\[\left\langle v,\frac{y^k-x}{t_k}\right\rangle = \frac{\langle v,y^k-x\rangle}{\|y^k-x\|}\cdot \frac{\|y^k-x\|}{t_k}. \]

由 (8)，第一因子的上极限不超过 \(0\)；第二因子收敛到 \(\|d\|\)。因此

\[\langle v,d\rangle\le 0. \]

若 \(d=0\)，则结论显然成立。故 \(v\in T_\Omega(x)^\circ\)。

再证 “\(\supseteq\)”。设 \(v\in T_\Omega(x)^\circ\)，若 \(v\notin \widehat N_\Omega(x)\)，则由 (8) 的否定形式，存在 \(\varepsilon>0\) 与 \(y^k\in\Omega,\ y^k\to x\) 使

\[\frac{\langle v,y^k-x\rangle}{\|y^k-x\|}\ge \varepsilon. \]

令

\[t_k:=\|y^k-x\|,\qquad d^k:=\frac{y^k-x}{t_k}. \]

则 \(\|d^k\|=1\)。取子列仍记为 \(d^k\)，使 \(d^k\to d\)。由定义 1，有 \(d\in T_\Omega(x)\)。于是

\[\langle v,d\rangle = \lim_{k\to\infty}\left\langle v,\frac{y^k-x}{t_k}\right\rangle \ge \varepsilon>0, \]

这与 \(v\in T_\Omega(x)^\circ\) 矛盾。故 \(v\in \widehat N_\Omega(x)\)。∎

定义 5 (Mordukhovich 法锥)
定义 Mordukhovich（limiting/basic）法锥为

\[N_\Omega^M(x) := \left\{ v\in\mathbb{R}^n: \exists\, x^k\in\Omega,\ x^k\to x,\ \exists\, v^k\to v,\ v^k\in \widehat N_\Omega(x^k) \right\}.\tag{10} \]

定义 6 (Clarke 法锥)
定义 Clarke 法锥为

\[N_\Omega^C(x):=\overline{\operatorname{co}}\,N_\Omega^M(x).\tag{11} \]

命题 3
总有

\[\widehat N_\Omega(x)\subseteq N_\Omega^M(x)\subseteq N_\Omega^C(x).\tag{12} \]

证明
由定义 (10)，取常值序列 \(x^k\equiv x\) 与 \(v^k\equiv v\)，可得

\[\widehat N_\Omega(x)\subseteq N_\Omega^M(x). \]

再由定义 (11)，\(N_\Omega^C(x)\) 是 \(N_\Omega^M(x)\) 的闭凸包，故

\[N_\Omega^M(x)\subseteq N_\Omega^C(x). \]

∎

---

局部极小点的最原始一阶必要条件

命题 4
若 \(x^*\) 是问题 (1) 的局部极小点，则

\[-\nabla f(x^*)\in T_\Omega(x^*)^\circ=\widehat N_\Omega(x^*).\tag{13} \]

证明
任取 \(d\in T_\Omega(x^*)\)。由定义 1，存在 \(x^k\in\Omega\) 与 \(t_k\downarrow 0\) 使

\[\frac{x^k-x^*}{t_k}\to d. \]

由于 \(x^*\) 是局部极小点，对充分大的 \(k\) 有

\[f(x^k)\ge f(x^*). \]

由 \(f\) 的可微性，

\[f(x^k)=f(x^*)+\nabla f(x^*)^\top(x^k-x^*)+o(\|x^k-x^*\|). \]

移项并除以 \(t_k\)，令 \(k\to\infty\)，得

\[\nabla f(x^*)^\top d\ge 0. \]

这等价于

\[-\nabla f(x^*)^\top d\le 0,\qquad \forall d\in T_\Omega(x^*), \]

即

\[-\nabla f(x^*)\in T_\Omega(x^*)^\circ. \]

再由命题 2，得到 (13)。∎

命题 4 表明：局部极小点处，目标函数不能沿任何真实切方向下降，因此其负梯度必须属于可行集的法锥。

---

线性化锥极锥的显式表达

令

\[K:=\{d:\ \nabla g_i(x^*)^\top d\le 0,\ i\in I(x^*)\},\tag{14} \]

\[S:=\{d:\ \nabla h_j(x^*)^\top d=0,\ j=1,\dots,p\}.\tag{15} \]

则由定义 2，

\[L_\Omega(x^*)=K\cap S.\tag{16} \]

命题 5
对任意闭凸锥 \(C_1,C_2\subseteq\mathbb R^n\)，有

\[(C_1\cap C_2)^\circ=\overline{\,C_1^\circ+C_2^\circ\,}.\tag{17} \]

证明
先证

\[\overline{C_1^\circ+C_2^\circ}\subseteq (C_1\cap C_2)^\circ. \]

任取 \(u=u_1+u_2\)，其中 \(u_1\in C_1^\circ,\ u_2\in C_2^\circ\)。对任意 \(x\in C_1\cap C_2\)，有

\[\langle u_1,x\rangle\le 0,\qquad \langle u_2,x\rangle\le 0, \]

故

\[\langle u,x\rangle=\langle u_1,x\rangle+\langle u_2,x\rangle\le 0. \]

所以 \(u\in (C_1\cap C_2)^\circ\)，进而其闭包也包含于 \((C_1\cap C_2)^\circ\)。

再证反向包含。设

\[M:=\overline{C_1^\circ+C_2^\circ}. \]

由上一步，\(M\subseteq (C_1\cap C_2)^\circ\)。对两边取极锥，包含关系反向，得

\[((C_1\cap C_2)^\circ)^\circ\subseteq M^\circ. \]

由双极定理（闭凸锥满足 \(K=(K^\circ)^\circ\)），可得

\[C_1\cap C_2\subseteq M^\circ. \]

另一方面，因为闭包不影响极锥，所以

\[M^\circ=(C_1^\circ+C_2^\circ)^\circ. \]

若 \(x\in (C_1^\circ+C_2^\circ)^\circ\)，则对任意 \(u_1\in C_1^\circ,\ u_2\in C_2^\circ\)，

\[\langle x,u_1+u_2\rangle\le 0. \]

令 \(u_2=0\)，得 \(\langle x,u_1\rangle\le 0\) 对任意 \(u_1\in C_1^\circ\) 成立，因此

\[x\in (C_1^\circ)^\circ=C_1. \]

同理可得 \(x\in C_2\)。故

\[(C_1^\circ+C_2^\circ)^\circ\subseteq C_1\cap C_2. \]

于是

\[M^\circ\subseteq C_1\cap C_2. \]

结合前面的包含关系，得到 \(M^\circ=C_1\cap C_2\)。再取极锥并用双极定理，即得

\[(C_1\cap C_2)^\circ=M=\overline{C_1^\circ+C_2^\circ}. \]

∎

命题 6
线性化锥 \(L_\Omega(x^*)\) 的极锥可显式写成

\[L_\Omega(x^*)^\circ = \left\{ \sum_{i\in I(x^*)}\lambda_i\nabla g_i(x^*) +\sum_{j=1}^p \mu_j\nabla h_j(x^*) :\ \lambda_i\ge 0,\ \mu_j\in\mathbb R \right\}.\tag{18} \]

证明
由 (16) 与命题 5，

\[L_\Omega(x^*)^\circ=(K\cap S)^\circ=\overline{K^\circ+S^\circ}. \]

先计算 \(K^\circ\)。由 (14)，

\[K=\bigcap_{i\in I(x^*)}\{d:\ \nabla g_i(x^*)^\top d\le 0\}. \]

每个半空间锥的极锥为

\[\{d:\ \nabla g_i(x^*)^\top d\le 0\}^\circ = \{\lambda_i\nabla g_i(x^*):\ \lambda_i\ge 0\}. \]

因此

\[K^\circ=\operatorname{cone}\{\nabla g_i(x^*):i\in I(x^*)\} = \left\{ \sum_{i\in I(x^*)}\lambda_i\nabla g_i(x^*):\ \lambda_i\ge 0 \right\}.\tag{19} \]

再计算 \(S^\circ\)。由 (15)，\(S\) 是线性子空间，因此

\[S^\circ=S^\perp = \operatorname{span}\{\nabla h_j(x^*):j=1,\dots,p\} = \left\{ \sum_{j=1}^p \mu_j\nabla h_j(x^*):\ \mu_j\in\mathbb R \right\}.\tag{20} \]

将 (19) 与 (20) 代入，并注意此时和为闭集，故闭包可省，即得 (18)。∎

命题 6 正是 KKT 乘子式出现的根源：活动不等式梯度生成非负锥，等式梯度生成线性空间，两者相加便是线性化锥的极锥。

---

KKT 条件的由来

KKT 条件的证明结构可概括为：

\[\text{局部极小} \Longrightarrow -\nabla f(x^*)\in T_\Omega(x^*)^\circ \Longrightarrow -\nabla f(x^*)\in L_\Omega(x^*)^\circ \Longrightarrow \text{存在乘子，满足 KKT}. \]

因此真正的关键，是找到足够的条件保证

\[T_\Omega(x^*)^\circ=L_\Omega(x^*)^\circ. \]

这正是各类约束资格条件的作用。

---

各类约束资格条件（CQ）

定义 7 (LICQ)
称问题 (1) 在可行点 \(x^*\) 处满足 LICQ（linear independence constraint qualification），如果向量组

\[\{\nabla g_i(x^*): i\in I(x^*)\}\cup \{\nabla h_j(x^*):j=1,\dots,p\} \]

线性无关。

定义 8 (MFCQ)
称问题 (1) 在可行点 \(x^*\) 处满足 MFCQ（Mangasarian–Fromovitz constraint qualification），如果

1. \(\nabla h_j(x^*)\)（\(j=1,\dots,p\)）线性无关；
2. 存在某个方向 \(d\in\mathbb R^n\) 使
   \[\nabla h_j(x^*)^\top d=0,\qquad j=1,\dots,p, \]
   且
   \[\nabla g_i(x^*)^\top d<0,\qquad i\in I(x^*). \]

定义 9 (CRCQ)
称问题 (1) 在可行点 \(x^*\) 处满足 CRCQ（constant rank constraint qualification），如果存在 \(x^*\) 的一个邻域 \(N(x^*)\)，使得对任意

\[I_1\subseteq I(x^*),\qquad I_2\subseteq \{1,\dots,p\}, \]

向量组

\[\{\nabla g_i(x): i\in I_1\}\cup \{\nabla h_j(x): j\in I_2\} \]

在整个邻域 \(N(x^*)\) 内都保持相同秩。

定义 10 (CPLD)
称问题 (1) 在可行点 \(x^*\) 处满足 CPLD（constant positive linear dependence），如果对任意

\[I_1\subseteq I(x^*),\qquad I_2\subseteq \{1,\dots,p\}, \]

一旦向量组

\[\{\nabla g_i(x^*):i\in I_1\}\cup \{\nabla h_j(x^*):j\in I_2\} \]

在点 \(x^*\) 处正线性相关，则它们在某个邻域内保持线性相关。

定义 11 (ACQ)
称问题 (1) 在可行点 \(x^*\) 处满足 ACQ（Abadie constraint qualification），如果

\[T_\Omega(x^*)=L_\Omega(x^*).\tag{21} \]

定义 12 (GCQ)
称问题 (1) 在可行点 \(x^*\) 处满足 GCQ（Guignard constraint qualification），如果

\[T_\Omega(x^*)^\circ=L_\Omega(x^*)^\circ.\tag{22} \]

注
各类 CQ 的本质作用都是保证：线性化信息足够忠实地反映可行集的局部几何。
其中 ACQ 要求锥本身相等，GCQ 只要求极锥相等；对推出 KKT 而言，GCQ 已经足够。

---

CQ 之间的常见关系

在标准可微 NLP 框架下，常见的蕴含关系可写成

\[\mathrm{LICQ}\Longrightarrow \mathrm{MFCQ},\qquad \mathrm{LICQ}\Longrightarrow \mathrm{CRCQ}, \]

\[\mathrm{MFCQ}\Longrightarrow \mathrm{CPLD},\qquad \mathrm{CRCQ}\Longrightarrow \mathrm{CPLD}, \]

\[\mathrm{CPLD}\Longrightarrow \mathrm{ACQ}\Longrightarrow \mathrm{GCQ}. \]

需要注意的是，MFCQ 与 CRCQ 一般互不包含。

---

KKT 定理

定理 1 (KKT 必要条件)
设 \(x^*\) 是问题 (1) 的局部极小点。若在 \(x^*\) 处满足 GCQ（见定义 12），则存在乘子

\[\lambda\in\mathbb R^m,\qquad \mu\in\mathbb R^p \]

使得

\[\nabla f(x^*) +\sum_{i=1}^m \lambda_i\nabla g_i(x^*) +\sum_{j=1}^p \mu_j\nabla h_j(x^*)=0,\tag{23} \]

\[g_i(x^*)\le 0,\qquad h_j(x^*)=0,\tag{24} \]

\[\lambda_i\ge 0,\tag{25} \]

\[\lambda_i g_i(x^*)=0,\qquad i=1,\dots,m.\tag{26} \]

特别地，若在 \(x^*\) 处满足 ACQ、CPLD、MFCQ 或 LICQ，则上述 KKT 条件同样成立。

证明
由命题 4，

\[-\nabla f(x^*)\in T_\Omega(x^*)^\circ. \]

由 GCQ 的定义 (22)，

\[T_\Omega(x^*)^\circ=L_\Omega(x^*)^\circ. \]

因此

\[-\nabla f(x^*)\in L_\Omega(x^*)^\circ. \]

再由命题 6，存在 \(\lambda_i\ge 0\)（\(i\in I(x^*)\)）与 \(\mu_j\in\mathbb R\)，使

\[-\nabla f(x^*) = \sum_{i\in I(x^*)}\lambda_i\nabla g_i(x^*) + \sum_{j=1}^p \mu_j\nabla h_j(x^*). \]

对 \(i\notin I(x^*)\) 定义 \(\lambda_i:=0\)，即可得到 (23)。由构造，\(\lambda_i\ge 0\)，且当 \(i\notin I(x^*)\) 时 \(g_i(x^*)<0\) 且 \(\lambda_i=0\)；当 \(i\in I(x^*)\) 时 \(g_i(x^*)=0\)。故

\[\lambda_i g_i(x^*)=0,\qquad i=1,\dots,m. \]

结合原始可行性 (24)，定理得证。

最后，由 CQ 之间的蕴含关系可知，ACQ、CPLD、MFCQ、LICQ 都蕴含 GCQ，因此结论同样成立。∎

---

KKT 条件的几何意义与作用

几何意义
由定理 1 可见，KKT 条件本质上是

\[-\nabla f(x^*)\in N_\Omega(x^*), \]

也就是：在局部极小点处，目标函数的下降趋势已经被活动约束的法向完全抵消。

理论作用
KKT 条件是一阶必要条件；在此基础上，可以进一步讨论二阶必要条件与二阶充分条件。

算法作用
SQP、内点法、增广拉格朗日法等经典 NLP 算法，本质上都在求解或逼近 KKT 系统 (23)–(26)。

灵敏度与对偶解释
KKT 乘子还具有对偶变量与边际价值的解释：某个活动约束的乘子越大，通常表明该约束对最优值的影响越显著。

---

总结

综上，一般 NLP 中 KKT 条件的由来可以概括为

\[\text{局部极小} \Longrightarrow -\nabla f(x^*)\in T_\Omega(x^*)^\circ \Longrightarrow -\nabla f(x^*)\in L_\Omega(x^*)^\circ \Longrightarrow \text{存在乘子，满足 KKT}. \]

其中：

• 切锥 \(T_\Omega(x^*)\) 描述真实可行方向（定义 1）；
• 线性化锥 \(L_\Omega(x^*)\) 描述一阶近似可行方向（定义 2）；
• Fréchet 正则法锥满足 \(\widehat N_\Omega(x^*)=T_\Omega(x^*)^\circ\)（命题 2）；
• 线性化锥的极锥具有显式梯度生成形式（命题 6）；
• 各类 CQ 的作用，是保证从真实几何到线性化几何的过渡合法（见定义 7–12 及定理 1）。

因此，KKT 条件并不是凭空写出的代数方程，而是局部最优性的几何性质、锥的对偶结构以及约束资格条件共同作用的结果。