数学优化理论 · 第 14 课
第二周复盘:从约束资格条件到原始—对偶最优性证书
2026 年 11 月 2 日|第 2 周·第 7 天(复盘)|讲授约 18 分钟,自测另计
本课不引入新的大型算法,而用一个完整的二次规划,把第 8—13 课串联起来。今天重点补强:活跃约束不等于正乘子;KKT 的必要性与充分性不同;强对偶不等于有限乘子一定存在;对偶下界不等于原始可行解。
一、六节课的逻辑地图
| 课号 | 核心对象 | 要求记住的准确结论 |
|---|---|---|
| 8:LICQ、MFCQ、Slater | 资格条件 | 局部最优 + LICQ/MFCQ 可保证存在 KKT 乘子;LICQ 还保证乘子唯一;标准凸问题中 Slater 主要保证强对偶与乘子存在 |
| 9:对偶函数 | 下界 | (q(\lambda,\nu)=\inf_xL(x,\lambda,\nu));不论原问题凸否,都有弱对偶 (d^\le p^) |
| 10:鞍点与间隙 | 证书 | 适当凸性下 KKT 与全局拉格朗日鞍点等价;原始可行上界减去对偶下界可认证目标误差 |
| 11:影子价格 | 灵敏度 | 扰动右端项 (g_i(x)\le b_i) 时,基准最优乘子给出 (-\lambda^*\in\partial v(b)) |
| 12:超梯度 | 算法 | 若内层全局最小点存在,残差 (g(x_k)) 是对偶超梯度;固定步长不保证非光滑情形精确收敛 |
| 13:对偶分解 | 并行与恢复 | 固定乘子可能使子问题可分,但内层变量仍可能违反原始耦合约束 |
三条最重要的逻辑线:
flowchart TD
A["局部最优 + 资格条件"] --> B["KKT 必要性:乘子存在"]
C["凸性 + KKT"] --> D["全局最优充分性"]
E["标准凸性 + Slater"] --> F["强对偶 + 最优乘子存在"]
B --> G["活跃集、乘子和互补松弛"]
D --> H["原始—对偶最优性证书"]
F --> H
I["内层全局最小化"] --> J["约束残差是超梯度"]
J --> K["对偶迭代、下界改进"]
K --> L["结合原始可行上界判断间隙"]
二、统一例题:两个活跃约束,乘子却不唯一
研究
[
\begin{aligned}
\min_{x,y}\quad &f(x,y)=\tfrac12[(x-2)^2+(y-1)^2]
\text{s.t.}\quad&
g_1=x+y-2\le0,
&g_2=2x+2y-4\le0,
&g_3=-x\le0,\qquad g_4=-y\le0.
\end{aligned}
\tag{1}
]
假设核验。 Hessian 为单位矩阵,故目标函数 1-强凸且梯度 1-Lipschitz;所有约束仿射,因此是凸优化。取 ((0.5,0.5)),四条不等式严格成立,Slater 成立。最优解存在且唯一。
求最优点。 无约束最优点 ((2,1)) 的和为 3,违反 (x+y\le2)。在边界 (y=2-x) 上,
[ \phi(x)=\tfrac12[(x-2)^2+(1-x)^2], \qquad \phi’(x)=2x-3. ]
候选点
[ \boxed{(x^,y^)=(1.5,0.5)},\qquad \boxed{f^*=0.25}. ]
这只是候选;下面必须检查完整的 KKT。
活跃约束。 (g_1(x^)=g_2(x^)=0),两条都活跃;(g_3,g_4<0),两条非活跃。互补松弛要求非活跃约束的乘子为零,但不要求每条活跃约束的乘子为正。
目标梯度为
[ \nabla f(x^*)=(-0.5,-0.5). ]
活跃梯度为 (\nabla g_1=(1,1))、(\nabla g_2=(2,2))。驻点条件
[ \nabla f(x^*)+\lambda_1\nabla g_1+ \lambda_2\nabla g_2=0 ]
等价于
[ \boxed{\lambda_1+2\lambda_2=0.5}. ]
所有非负解为
[ \boxed{\lambda_2=s,\quad\lambda_1=0.5-2s,\quad 0\le s\le0.25}. ]
任一组都满足原始可行、对偶可行、驻点与互补松弛。由于问题凸,KKT 足以证明全局最优。这里原始最优点唯一,但乘子有无穷多组;例如 (\lambda_2=0) 时,第 2 条约束依然活跃。
LICQ 与 MFCQ: 活跃梯度 ((1,1)) 和 ((2,2)) 线性相关,LICQ 失败;方向 (d=(-1,-1)) 满足
[ \nabla g_1^Td=-2<0,\qquad \nabla g_2^Td=-4<0, ]
所以 MFCQ 成立。问题同时满足 Slater。可见:LICQ 比 MFCQ 更强;缺少 LICQ 并不意味着不存在 KKT 或强对偶,只是不能保证乘子唯一。
三、KKT 为什么足以构成全局最优性证书?
一般地,令 (g_i(z)\le0)、(Az=b),其中 (f)、(g_i) 凸可微,等式仿射。拉格朗日函数
[ L(z,\lambda,\nu)=f(z)+\sum_i\lambda_i g_i(z)+\nu^T(Az-b). ]
假设原始可行点 (z^) 与乘子满足 KKT。对任意原始可行 (z),由 (\lambda_i^\ge0) 与 (g_i(z)\le0):
[ f(z)\ge L(z,\lambda^,\nu^). ]
由于 (L(\cdot,\lambda^,\nu^)) 是凸函数,KKT 驻点保证它在 (z^*) 处全局最小:
[ L(z,\lambda^,\nu^)\ge L(z^,\lambda^,\nu^*). ]
最后由互补松弛及等式可行性:
[ L(z^,\lambda^,\nu^)=f(z^). ]
合并得到严格的最优性证明:
[ \boxed{f(z)\ge L(z,\lambda^,\nu^)\ge L(z^,\lambda^,\nu^)=f(z^)}. \tag{2} ]
注意假设角色: 这条“存在 KKT (\Rightarrow) 全局最优”的充分性证明不需要 Slater;但从最优点反过来断言一定存在乘子,通常需要资格条件。
四、弱对偶、对偶函数与数值证书
回到式 (1),取乘子 (\lambda_1=t\ge0),其余三个乘子均为 0。对原变量 ((x,y)\in\mathbb R^2) 取下确界:
[ q(t)=\inf_{x,y}\left{\tfrac12[(x-2)^2+(y-1)^2]+t(x+y-2)\right}. ]
求导得唯一内层极小点
[ x(t)=2-t,\qquad y(t)=1-t. ]
代回:
[ \boxed{q(t)=t-t^2}. \tag{3} ]
这是完整对偶函数在一条合法乘子切片上的值;因为其他乘子取零,(q(t)) 仍是原问题的合法下界。它在 (t=0.5) 达到 (0.25),与上面找到的原始最优值相同,因此强对偶得到数值验证。
弱对偶的严格来源。 对任意原始可行 (z) 与对偶可行 ((\lambda,\nu)),
[ q(\lambda,\nu)=\inf_u L(u,\lambda,\nu) \le L(z,\lambda,\nu)\le f(z). ]
因此 (q(\lambda,\nu)\le p^*)。若当前有可行原始点 (\hat z) 与合法对偶下界 (q),则
[ \boxed{0\le f(\hat z)-p^*\le f(\hat z)-q}. \tag{4} ]
这才是可以认证的目标误差上界。若 (\hat z) 不可行,右侧的差可能为负,不能当作有效间隙。
更细地,对原始可行 (z),
[ f(z)-q= \underbrace{-\sum_i\lambda_i g_i(z)}{\ge0:\ \text{互补性缺口}} + \underbrace{L(z,\lambda,\nu)-\inf_uL(u,\lambda,\nu)}{\ge0:\ \text{内层最小化缺口}}. \tag{5} ]
因此零间隙同时意味着互补性和内层全局最小化条件在该原始—对偶对上成立。
五、对偶迭代:三步数值计算与收敛条件
继续沿合法乘子切片只更新 (t),其余乘子固定为 0。由式 (3):
[ q’(t)=1-2t =(x(t)+y(t)-2). ]
使用投影对偶梯度上升:
[ t_{k+1}=[t_k+\eta(1-2t_k)]_+, \quad t_0=0,\quad \eta=\tfrac14. ]
即
[ \boxed{t_{k+1}=\tfrac12t_k+\tfrac14}. \tag{6} ]
| (k) | (t_k) | 内层点 ((x_k,y_k)) | 共享约束残差 (x_k+y_k-2) | 对偶下界 (q(t_k)) |
|---|---|---|---|---|
| 0 | 0 | ((2,1)) | 1 | 0 |
| 1 | 0.25 | ((1.75,0.75)) | 0.5 | 0.187500 |
| 2 | 0.375 | ((1.625,0.625)) | 0.25 | 0.234375 |
| 3 | 0.4375 | ((1.5625,0.5625)) | 0.125 | 0.24609375 |
| 最优 | 0.5 | ((1.5,0.5)) | 0 | 0.25 |
重要: 前四个内层点 (x_k+y_k>2),因此不符合原问题的原始可行性!它们可用于计算对偶下界,但不能直接作为原始可行上界。作为对照,选原始可行点 ((1,1)),有 (f(1,1)=0.5);于是第 2 步的认证间隙为 (0.5-0.234375=0.265625)。只有进一步改善原始可行上界,才能使证书间隙真正接近零。
本例的最优乘子切片是 (t^*=0.5)。由式 (6)
[ |t_{k+1}-t^|=\tfrac12|t_k-t^|, ]
故乘子误差几何下降;并且
[ p^*-q(t_k)=(t_k-0.5)^2, ]
| 对偶值误差每步变为上一步的 (1/4)。对一般 (\eta),投影非扩张性可得收缩上界 ( | 1-2\eta | ),所以在本二次模型中 (0<\eta<1) 具有严格收缩。这依赖于光滑强凹二次结构,不能推广为非光滑对偶超梯度法的线性收敛保证。 |
六、三个失败反例:把定理的边界记牢
反例 A:最优但没有有限 KKT 乘子。 (\min_x x),约束 (x^2\le0)。唯一可行点 (x^=0),显然最优;但驻点方程 (1+2\lambda x^=0) 成了 (1=0)。凸性本身不足以保证有限 KKT 乘子存在,Slater 在此失败。
反例 B:零对偶间隙,但对偶最优不达到。 (\min_x(x-1)^2),约束 (x^2\le0)。有 (p^*=1),而
[ q(\lambda)=\inf_x[(x-1)^2+\lambda x^2] =\frac{\lambda}{1+\lambda},\quad\lambda\ge0. ]
(\sup_{\lambda\ge0}q(\lambda)=1),但任何有限 (\lambda) 都取不到 1;因此强对偶(值相等)不意味着对偶最优乘子存在。
| 反例 C:凹对偶函数也可能固定步长振荡。 对 (q(\lambda)=1- | \lambda-1 | ) 进行超梯度上升,固定步长 0.6,从 (\lambda_0=0) 出发可产生 (0\to0.6\to1.2\to0.6\to1.2\to\cdots)。不能仅凭“函数凹”就声称任意步长收敛。 |
七、复盘判断表与下一讲
| 看到的证据 | 能够推出 | 不能直接推出 |
|---|---|---|
| 活跃 (g_i(x^*)=0) | 该约束取等号 | (\lambda_i^*>0) |
| 局部最优 + LICQ | 存在且唯一的 KKT 乘子 | 原始全局最优(不假设凸性时) |
| 凸问题 + 满足 KKT 的点 | 原始全局最优、零对偶间隙 | 任意数值算法均收敛 |
| 标准凸问题 + Slater | 适当有限最优值等条件下的强对偶及最优乘子存在 | LICQ 或乘子唯一 |
| (d^=p^) | 原始和对偶最优值相等 | 对偶最大值必在有限乘子处达到 |
| 对偶下界升高 | 可能改善最优值下界 | 每轮内层原始点必可行 |
| 原始可行 + 对偶可行 + 小间隙 | 可认证的目标函数误差上界 | 无额外条件下的变量距离上界 |
下一讲:第 15 课,2026 年 11 月 3 日。 进入第三周“GD/AGD 收敛理论”:从 Descent Lemma 推导梯度下降的步长界、凸与强凸情况下的函数值/距离收敛速度,并比较不同条件下 (O(1/k)) 与线性收敛。复盘测验不会改变日期或课号。
八、今日四级自测(100 分)
请先独立作答。首次课堂不提供答案;不要打开独立 JSON 提前泄题。 前三题客观判分,第四题检查推导的假设与不等式。
Lv1|KKT 充分性与资格条件|15 分|预计 2 分钟|单选
对标准凸可微最小化问题,所有不等式均写为 g_i(x)≤0。关于 KKT、Slater 和活跃约束,下列哪项一定正确?
A. 只要 g_i(x*)=0,对应 KKT 乘子就一定严格大于零。
B. Slater 条件失败时,任何最优点都不可能存在有限 KKT 乘子。
C. 若原始可行点与一组对偶可行乘子满足驻点和互补松弛,则它是全局最优点;这一充分性本身无需 Slater。
D. 拉格朗日对偶函数总是可微的,因此任意固定步长对偶梯度上升都收敛。
提示:区分 KKT 的充分性、约束资格条件对必要性的保证以及活跃约束与正乘子的区别。
Lv2|冗余活跃约束的乘子计算|20 分|预计 3 分钟|数值
考虑 f(x,y)=1/2[(x−2)²+(y−1)²],约束 x+y≤2、2x+2y≤4、x≥0、y≥0。记前两条不等式的乘子为 λ₁、λ₂。已知在最优解处 λ₂=0.100,且非负性约束的乘子为零。求 λ₁(保留三位小数)。
提示:最优点在 x+y=2 上;先用对称投影或 KKT 得到目标梯度,再列驻点等式。
Lv3|强对偶与乘子不达到的反例|25 分|预计 5 分钟|单选
考虑凸优化问题 min (x−1)²,s.t. x²≤0,λ≥0 为该约束的乘子。关于强对偶、乘子存在性和 KKT,下列哪项正确?
A. Slater 成立,因为原问题存在唯一可行点。
B. 原问题最优值与对偶上确界都等于 1,但没有有限 λ 能使对偶函数取到 1,也不存在有限 KKT 乘子。
C. 对任何有限 λ,对偶函数都等于负无穷,因此对偶问题没有有用下界。
D. 取 λ=1 就能满足最优点的 KKT 驻点条件。
提示:先由 x²≤0 确定唯一可行点,再对 L=(x−1)²+λx² 求全局内层极小,注意 sup 是否达到。
Lv4|KKT—对偶—收敛的综合证明|40 分|预计 12 分钟|开放题
考虑 [ \min_{x,y\in\mathbb R}\;\tfrac12[(x-4)^2+(y-2)^2] \quad\text{s.t.}\quad x+y\le4,\;2x+2y\le8,\;x\ge0,\;y\ge0. ] 记前两条约束的乘子为 (\lambda_1,\lambda_2\ge0),并令 (t=\lambda_1+2\lambda_2)。
A(12 分):求唯一原始最优点、最优值、全部活跃约束,以及所有最优 ((\lambda_1,\lambda_2));检验 KKT 四组条件,并指出 LICQ、MFCQ、Slater 是否成立。
B(10 分):对一般凸可微目标、凸不等式及仿射等式,使用拉格朗日函数与凸性严格证明“原始可行 + 对偶可行 + KKT 驻点 + 互补松弛”足以保证全局最优。注明 Slater 在这一充分性证明中是否必需。
C(10 分):在本题中令非负性约束乘子为零,求 (0\le t\le1) 时的对偶函数 (q(t)),并用原始可行点 ((3,1)) 与 (t=0.5) 构造数值的原始—对偶最优性间隙。
D(8 分):固定 (\lambda_2=0),仅对 (\lambda_1=t) 做投影对偶梯度上升:(t_{k+1}=[t_k+\eta q’(t_k)]_+),取 (\eta=1/4,t_0=0)。计算 (t_1,t_2),并证明对偶乘子误差的收缩因子。说明这个线性收敛结论为何不能直接推广到任意非光滑对偶函数。
提示:A 先从 x+y=4 消元或用 KKT;B 链接 f(z)≥L(z,λ)≥L(x,λ);C 固定 t 后消去原变量;D 先写出 t_{k+1} 的仿射形式。*
答题反馈
四题合计 100 分(15+20+25+40)。80 分及以上按计划继续;60–79 分补充薄弱点实例;低于 60 分优先复习活跃约束、KKT、互补松弛及弱对偶。无论得分如何,第 15 课的日期与编号都不改变。