数学优化理论 · 第 8 课

为什么最优点不一定有 KKT 乘子?LICQ、MFCQ 和 Slater 分别保证什么?

2026 年 10 月 27 日|第 2 周·第 1 天|阅读约 18 分钟(自测另计)

本课问题: 昨天我们知道:对凸问题,找到满足 KKT 的乘子可以证明全局最优。但如果一个点确实最优,为什么不一定能找到乘子?即使乘子存在,为什么又可能不唯一?这正是约束资格条件(Constraint Qualification, CQ)要解决的事。

学习目标:区分活跃约束与非零乘子;准确写出 LICQ、MFCQ、Slater 的适用条件;理解 LICQ ⇒ MFCQ 的构造性证明;手算一个乘子不唯一但算法仍收敛的实例;认识“缺少资格条件”与“必然没有 KKT”不是同一命题。

一、先用一个反直觉例子:最优解唯一,乘子却不唯一

考虑一维问题

[ \min_{x\in\mathbb R} f(x)=\frac12(x-2)^2, \qquad g_1(x)=x-1\le0,\quad g_2(x)=2x-2\le0. \tag{1} ]

这两条约束虽然写法不同,限定的都是 (x\le1),第二条是第一条的两倍。由于无约束最优点 (x=2) 不可行,唯一可行最优点是

[ x^=1,\qquad f(x^)=\frac12. ]

先不计算乘子,检查约束状态:(g_1(1)=g_2(1)=0),所以两条都活跃。

拉格朗日函数取 (g_i\le0) 的号数约定:

[ \mathcal L(x,\lambda)=\tfrac12(x-2)^2 +\lambda_1(x-1)+\lambda_2(2x-2), \qquad \lambda_1,\lambda_2\ge0. ]

KKT 驻点条件为

[ 0=f’(1)+\lambda_1 g_1’(1)+\lambda_2g_2’(1) =-1+\lambda_1+2\lambda_2. ]

因此所有乘子可以写成

[ \boxed{\lambda_1=1-2t,\quad\lambda_2=t,\quad 0\le t\le\tfrac12.}\tag{2} ]

例如 ((1,0))、((0,\tfrac12)) 和 ((\tfrac12,\tfrac14)) 都满足 KKT。这里并没有“算错一个答案”:最优点唯一,与表示边界法向的乘子唯一,是两件不同的事。 最优点由严格凸的目标与可行集决定;乘子是对同一法向量的非负组合系数,有冗余的法向便可能有多种表示。

再强调两件容易误会的事:

  • (g_2) 活跃而取 (\lambda_2=0) 完全合法。互补松弛只要求 (\lambda_i g_i(x^*)=0),不要求“活跃就严格正”。
  • 删掉 (g_2) 后,函数与可行集都没变,最优点仍是 1,但仅剩 (g_1) 的乘子被确定为 1。乘子与约束表达方式有关;最优点则由原始优化问题决定。

二、KKT 到底在要求什么?为什么需要 CQ?

一般考虑

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

假设相关函数在候选点附近连续可微。定义活跃集

[ I(x^)={i:g_i(x^)=0}. ]

对于不等式乘子 (\lambda_i\ge0)、等式乘子 (\nu_j\in\mathbb R),KKT 为

[ \begin{cases} g_i(x^)\le0,\quad h_j(x^)=0, &\text{原始可行性},
\lambda_i\ge0, &\text{对偶可行性},
\nabla f(x^)+\sum_i\lambda_i\nabla g_i(x^) +\sum_j\nu_j\nabla h_j(x^)=0, &\text{驻点条件},
\lambda_i g_i(x^
)=0,\ \forall i, &\text{互补松弛}. \end{cases}\tag{4} ]

互补松弛意味着非活跃约束对应的 (\lambda_i=0),于是驻点条件实际上只使用活跃约束的梯度。

为什么最优点附近总是出现这些法向?假设有一条从最优点出发的光滑可行曲线 (x(t)),其中 (x(0)=x^*)、(x’(0)=d)。因为沿它不能立刻降低目标,有

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

对任何活跃不等式,沿可行曲线还必须有

[ \nabla g_i(x^*)^\top d\le0, ]

而等式约束给出 (\nabla h_j(x^*)^\top d=0)。因此定义线性化可行方向集合

[ L(x^)=\left{d:\nabla g_i(x^)^\top d\le0\ (i\in I),
\nabla h_j(x^*)^\top d=0\ (j=1,\dots,p)\right}.\tag{5} ]

真正可行方向所构成的切锥 (T_C(x^*)) 总包含在这个线性化集合内:

[ T_C(x^)\subseteq L(x^). ]

关键问题: 若约束在边界处退化,(L(x^*)) 会过大,把根本不存在的方向也当作“线性化可行”。此时最优性仍可能成立,却无法用活跃梯度拼出一个 KKT 乘子。CQ 正是为了排除足以妨碍这类法向表示的退化。

三、LICQ:活跃梯度必须线性无关

线性无关约束资格条件(LICQ)定义为:在 (x^*) 处,下面向量组线性无关:

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

没有等式时,把 (k= I ) 个活跃梯度作为行组成矩阵

[ G=\begin{bmatrix} \nabla g_{i_1}(x^)^\top\ \vdots
\nabla g_{i_k}(x^
)^\top \end{bmatrix}\in\mathbb R^{k\times n}. ]

LICQ 等价于 (G) 满行秩 (k)。因而活跃约束数不能超过变量维数。几何上,它禁止用互相重复的法向“重复描述”同一个局部边界。

例 (1) 在 (x^*=1) 处的活跃梯度为 (1,2)。这两个向量处在一维空间,显然线性相关,LICQ 失败。

LICQ 为什么保证 KKT 乘子唯一? 假设某个点已经有两组 KKT 乘子 ((\lambda,\nu))、((\hat\lambda,\hat\nu))。两次驻点条件相减:

[ \sum_{i\in I}(\lambda_i-\hat\lambda_i)\nabla g_i(x^) +\sum_j(\nu_j-\hat\nu_j)\nabla h_j(x^)=0. ]

非活跃乘子两组都为零。若 LICQ 成立,所有活跃梯度和等式梯度线性无关,那么每个系数只能为零,故两组乘子相同。

因此准确结论是:在通常的可微局部最优框架中,LICQ 保证KKT 乘子存在且唯一;上面这段减法证明其中的“若存在则唯一”,存在性还依赖局部最优性与下一节的资格条件定理。它不是说最优点必定唯一;严格凸才是保证唯一最优点的常见来源。

四、MFCQ:不必线性无关,只要存在共同的严格内移方向

Mangasarian–Fromovitz CQ(MFCQ)在 (x^*) 处要求:

  1. 等式约束梯度 (\nabla h_j(x^*)) 线性无关;
  2. 存在方向 (d\in\mathbb R^n),使得

[ \nabla h_j(x^)^\top d=0,\quad\forall j, \qquad \nabla g_i(x^)^\top d<0,\quad\forall i\in I(x^*). \tag{7} ]

第一项保证能沿等式约束的切向移动,第二项表示:所有活跃不等式在同一个方向上严格变松。

例 (1) 中并无等式约束。选 (d=-1):

[ g_1’(1)d=-1<0,\qquad g_2’(1)d=-2<0. ]

所以虽然 LICQ 失败,MFCQ 仍成立。这说明 MFCQ 比 LICQ 弱:它允许多个活跃约束具有相关梯度,只要存在可同时朝内走的方向。

4.1 证明 LICQ ⇒ MFCQ(不是靠图感判断)

先只看不等式情形。若 LICQ 成立,(G) 满行秩,因此 (GG^\top) 可逆。构造

[ d=-G^\top(GG^\top)^{-1}\mathbf1_k. ]

直接相乘:

[ Gd=-GG^\top(GG^\top)^{-1}\mathbf1_k=-\mathbf1_k<0. \tag{8} ]

于是所有活跃约束的一阶变化都严格为负,MFCQ 得证。

有等式时,可把等式梯度行和活跃不等式梯度行一起放入矩阵;LICQ 保证该矩阵满行秩。指定等式行内积为 0、活跃不等式行内积为 −1,同样能解出所需方向 (d)。

这不是“经验上通常成立”,而是一个构造性线性代数证明。

4.2 MFCQ 为什么足以保证局部最优的 KKT?

这里用一个重要桥梁:Fritz John 条件。在适当的可微性及局部最优假设下,即使暂时没有 CQ,也存在不全为零的乘子 (\alpha\ge0,\lambda_i\ge0,\nu_j\in\mathbb R),使

[ \alpha\nabla f(x^)+ \sum_{i\in I}\lambda_i\nabla g_i(x^)+ \sum_j\nu_j\nabla h_j(x^*)=0. \tag{9} ]

如果 (\alpha>0),除以 (\alpha) 就得到标准 KKT。麻烦是可能出现 (\alpha=0):目标梯度完全消失,约束法向自己相互抵消。这叫异常乘子情形。

假设 MFCQ 成立,反设 (\alpha=0)。将式 (9) 与 MFCQ 方向 (d) 点乘。等式部分为零;每项活跃不等式都满足 (\nabla g_i^\top d<0),且 (\lambda_i\ge0)。它们的和为零,只能所有活跃 (\lambda_i=0)。此时剩下

[ \sum_j\nu_j\nabla h_j(x^*)=0. ]

MFCQ 的等式梯度线性无关迫使所有 (\nu_j=0),与乘子“不全为零”矛盾。因此 (\alpha>0),KKT 乘子存在。

这里讲的是“局部最优 ⇒ KKT 必要性”,不是说满足 MFCQ 就能保证目标函数是凸的、最优点是全局的或乘子唯一。

五、Slater:在凸问题中寻找全局严格可行点

现在假设约束函数 (g_i) 都凸且可微、等式约束仿射 (Ax=b),目标 (f) 凸。在通常的全空间或合适相对内点的定义域条件下,Slater 条件要求存在 (\bar x) 满足

[ g_i(\bar x)<0\quad(\forall i),\qquad A\bar x=b. \tag{10} ]

它检查一个全局严格可行点;LICQ、MFCQ 则是在指定可行点(尤其最优点)的局部梯度几何上检查。

对式 (1),取 (\bar x=0):

[ g_1(0)=-1<0,\qquad g_2(0)=-2<0, ]

故 Slater 成立,尽管最优点处 LICQ 失败。

在凸可微不等式 + 仿射等式的标准条件下,Slater 还能推出最优点处的 MFCQ。 不只背结论,直接证明:对于任一可行 (x^) 和其中一条活跃凸约束 (g_i(x^)=0),凸性的一阶下界有

[ g_i(\bar x)\ge g_i(x^)+ \nabla g_i(x^)^\top(\bar x-x^*). ]

因此

[ \nabla g_i(x^)^\top(\bar x-x^) \le g_i(\bar x)-g_i(x^*)<0. \tag{11} ]

取 (d=\bar x-x^*),它还满足 (Ad=0)。在等式梯度满秩(或移除冗余等式)的表述下,便满足 MFCQ。

Slater 的另一个重要作用是:在满足适当定义域、最优值有限和原最优可达到等标准假设时,保证凸优化强对偶和最优对偶乘子可达到。注意以下三个结论分工不同:

条件 检查对象 常用保证 不能直接保证
LICQ 某点的活跃约束梯度(含等式) 局部最优点 KKT 乘子存在且唯一 原始最优点唯一、全局最优
MFCQ 某点可共同内移的线性化方向 局部最优点存在 KKT 乘子 乘子唯一、强凸
Slater(标准凸问题) 全局严格可行点 强对偶、最优乘子存在;凸可微框架下有 MFCQ 方向 LICQ、乘子唯一

尤其不能倒着读箭头。 例如 Slater 成立,并不意味着最优点处每条活跃梯度都线性无关。式 (1) 就是反例。另一方面,某个 CQ 失败也不意味着该实例一定没有 KKT 乘子;资格条件提供的是可重复使用的充分保证。

六、两次投影梯度迭代:优化算法与乘子资格是两条分析线

仍使用式 (1),其可行域等价于 (C=(-\infty,1])。目标 Hessian 恒为 (1),因此 (\mu=L=1)。取投影梯度迭代

[ x_{k+1}=\Pi_C(x_k-\eta f’(x_k)), \qquad \eta=\tfrac12, ]

并从 (x_0=-1) 开始。因为 (\Pi_C(z)=\min{z,1}),一步可写成

[ x_{k+1}=\min{1,\tfrac12x_k+1}. \tag{12} ]

每个数字都可以手算:

迭代 当前 (x_k) 梯度 (f’(x_k)=x_k-2) 未投影 (z_k=x_k-\tfrac12f’(x_k)) 投影后 (x_{k+1}) 当前 (f(x_k))
0 −1 −3 0.5 0.5 4.5
1 0.5 −1.5 1.25 1 1.125
2 1 −1 1.5 1 0.5

第二步由于 (z_1=1.25) 超过可行上界,被投影回 1;第三步不再变化,说明 (x^*=1) 是投影不动点。最优点梯度 (-1) 非零,但投影梯度映射为零。

进一步看收敛证明:映射 (x\mapsto \tfrac12x+1) 是 (1/2)-Lipschitz,投影到闭凸集合是非扩张的,所以

[ |x_{k+1}-x^|\le\tfrac12|x_k-x^|. \tag{13} ]

这里给出的是距离几何收缩;收敛因子使用了目标的二阶曲率和合法步长,并非“因为 MFCQ,所以 PGD 线性收敛”。MFCQ 为局部最优性条件中的乘子存在提供保证,PGD 的收敛保证来自另一个前提链。对一般问题,若有 (0<\mu I\preceq\nabla^2 f\preceq LI)、闭凸 (C) 且合法步长,类似的投影收缩分析才能成立;不能把这一玩具算例无条件外推给非凸问题。

七、失败反例:CQ 失效究竟意味着什么?

反例 A:最优点存在,但不存在有限 KKT 乘子。

[ \min_x f(x)=x,\qquad \text{s.t. }g(x)=x^2\le0. ]

唯一可行点 (x^*=0),因而必然全局最优。但 (g’(0)=0),既没有严格可行点(Slater 失败),也不存在 (g’(0)d<0) 的方向(MFCQ 失败);LICQ 也失败。KKT 驻点要求

[ f’(0)+\lambda g’(0)=1+2\lambda\cdot0=0, ]

任何有限 (\lambda\ge0) 都无法满足。

几何上,实际可行集只有一个点,切锥是 ({0});但线性化条件 (g’(0)d=0) 对所有 (d\in\mathbb R) 都成立。线性化太松,无法捕获真实边界,这正是异常情形的来源。

反例 B:同样没有 CQ,但 KKT 却可以成立。

保持约束 (x^2\le0),将目标换成 (f(x)=x^2)。在 (x^*=0) 处,(f’(0)=0),直接取 (\lambda=0) 就满足 KKT。资格条件失败只是失去普遍保证,不是宣告本例必失败。

反例 C:活跃的乘子不必为正。 式 (2) 的多组合法解中存在零乘子。因此判断活跃集要看 (g_i(x^*)=0),而不是看 (\lambda_i>0)。

八、一张关系图记住各条件的作用

flowchart TD
  L["局部最优 + 可微约束"] --> F["Fritz John:可能有异常乘子 α=0"]
  Q["LICQ:活跃梯度线性无关"] --> M["MFCQ:共同严格内移方向"]
  S["凸约束 + 仿射等式 + Slater 严格可行"] -->|标准可微条件| M
  M --> K["排除异常 α=0 → KKT 乘子存在"]
  F --> K
  Q --> U["若存在乘子,则乘子唯一"]
  S --> D["适当凸优化假设 → 强对偶/对偶最优达到"]
  K --> C["若 f/g 凸、等式仿射:KKT 是全局最优证书"]
  H["强凸 + Smooth + 合法步长 + 凸投影"] --> R["投影梯度可证收敛"]

把这个图拆成四句可检查的话:LICQ 强于 MFCQ;MFCQ 解决 KKT 的必要性;Slater 主要用于凸问题的强对偶与乘子存在;凸性让满足 KKT 的点成为全局最优证书。 最优点/乘子唯一性还需要各自额外条件;算法是否收敛要另看曲率、步长和迭代规则。

九、今日总结

第一周把最优性刻画成“目标梯度 + 法锥 = 0”。第二周进一步追问:法锥能否由你给出的这些约束梯度表示?这种表示是否唯一? LICQ 关注梯度之间有没有线性依赖;MFCQ 关注是否有共同内移方向;Slater 在凸框架中寻找严格可行点,连接对偶理论。

本课最重要的一组区分是:

[ \underbrace{\text{存在 KKT 乘子}}{\text{资格条件相关}} \quad\ne\quad \underbrace{\text{乘子唯一}}{\text{LICQ 等条件相关}} \quad\ne\quad \underbrace{\text{原问题最优点唯一}}{\text{严格/强凸等相关}} \quad\ne\quad \underbrace{\text{迭代算法收敛}}{\text{曲率 + 步长等相关}}. ]

下面四题首次发送不公布标准答案;先独立作答,再按题型与评分要点批改。

十、四级自测(满分 100 分)

首次授课不附标准答案、解析或开放题示范证明。 Lv1/Lv2/Lv3 为可客观评分题,Lv4 为按要点批改的开放题。四题考察不同能力,用户可按“1:选项,2:数值,3:选项,4:完整过程”回答。

Lv1|LICQ、MFCQ 与乘子唯一性|15 分|预计 2 分钟|单选

题目:考虑仅包含连续可微不等式约束的优化问题,x* 是一个局部最优点。下列说法哪项一定正确?

A. 只要约束在 x* 活跃,它对应的 KKT 乘子必严格大于零。

B. 若 x* 处 LICQ 成立,则 MFCQ 也成立;而且只要 KKT 乘子存在,它就是唯一的。

C. 只要 Slater 条件不成立,局部最优点就绝不可能存在 KKT 乘子。

D. 只要 MFCQ 成立,所有活跃约束的梯度就必线性无关。

可选中立提示:分别看“活跃”“存在乘子”“乘子唯一”是由哪一种条件保证的。

Lv2|冗余活跃约束的乘子计算|20 分|预计 3 分钟|数值

题目:求解 min f(x)=½(x−5)²,满足 g₁(x)=x−2≤0、g₂(x)=3x−6≤0。在最优点的 KKT 乘子中,已知 λ₁=0.6,求 λ₂ 的数值(保留三位小数,仅填数值)。

可选中立提示:先找最优边界点,再用 f′(x)+λ₁g₁′(x)+λ₂g₂′(x)=0。*

Lv3|资格条件失败并不等于 KKT 必然失败|25 分|预计 5 分钟|单选

题目:考虑两个一维凸优化问题:P:min f(x)=e^x,s.t. x²≤0;Q:min f(x)=x⁴+x²,s.t. x²≤0。二者唯一可行点均为 x*=0。以下哪个判断正确?

A. P 存在有限 KKT 乘子,但 Q 不存在。

B. P 和 Q 都满足 MFCQ,因此都存在有限 KKT 乘子。

C. P 不存在有限 KKT 乘子,但 Q 存在至少一组 KKT 乘子;二者均不满足 MFCQ。

D. 只要 Slater 失效,两问题都必然存在严格正的对偶间隙。

可选中立提示:两个问题的可行集一样,但目标梯度在 x=0 是否一样?活跃约束的梯度又是多少?

Lv4|二维活跃集、乘子退化和资格条件证明|40 分|预计 12 分钟|开放证明

题目:考虑二维凸优化问题 min f(x,y)=½[(x−2)²+(y−2)²],约束 g₁=x+y−2≤0,g₂=x−1≤0,g₃=y−1≤0,g₄=−x≤0,g₅=−y≤0。

A(8分)求唯一最优点,列出活跃与非活跃约束,并说明为何最优点唯一。

B(12分)完整写出 KKT 条件,找出全部满足 KKT 的非负不等式乘子;由此说明最优解唯一不代表乘子唯一,且活跃乘子可以为零。

C(10分)在最优点判断 LICQ、MFCQ 是否成立,并给出全局 Slater 严格可行点;每一步必须展示相关梯度或方向的检验。

D(10分)一般地,对于仅有连续可微不等式约束的 n 维问题,设活跃约束梯度线性无关。用线性代数证明 LICQ ⇒ MFCQ,并解释这能为局部最优点的 KKT 必要性提供什么保证。

可选中立提示:先画出盒约束与斜边的关系;判断 LICQ 看梯度线性独立,判断 MFCQ 看是否存在使全部活跃约束严格下降的共同方向。一般证明可把活跃梯度放入一个矩阵。

十一、下一讲与评分规则

下一讲:2026 年 10 月 28 日,第 9 课——从拉格朗日函数推导对偶函数与弱对偶;用一个有解析解的凸问题计算对偶下界、对偶间隙和最优乘子。 我们还会解释 Slater 给出的强对偶条件与一般非凸问题中可能出现的间隙。

用户提交四题答案后,按 Lv1 15 + Lv2 20 + Lv3 25 + Lv4 40 逐题批改,开放证明使用评分要点人工/ChatGPT 评价,不伪称机器自动判定。总分 ≥80 正常继续;60–79 补做针对性算例;<60 重温活跃约束、法锥、KKT 与 CQ,再练同等难度巩固题。学习建议不改变按北京日期确定的课号。