第11课|拉格朗日乘子的影子价格、最优值灵敏度与活跃集切换

2026年10月30日 · 第2周第4天 · 讲授约18分钟(自测另计)

上一课用原始—对偶间隙验证“解是否足够好”。今天进一步问:如果把约束放松一点,最优值能改善多少? 为什么一个 KKT 乘子能衡量资源价值?为什么资源增加很多时这个预测可能失败?

一、问题设置:改变约束右端项

从单个参数问题开始: [ v(b)=\inf_x f(x),\qquad \text{s.t. }g(x)\le b. \tag{1} ] 其中 (b) 是约束允许的上界,(v(b)) 称为最优值函数(value function)。本课先取 (f,g) 凸且连续可微,允许在有最优解时使用 KKT;强对偶与有限乘子存在需单独检查 Slater 等条件。

  • 增大 (b) 意味着放宽约束:原来的可行点仍可行,所以 (v(b)) 不会上升。
  • 活跃:(g(x^)=b)。但活跃 不蕴含 (\lambda^>0)。
  • 采用 (g(x)-b\le0) 的符号约定时,最优乘子 (\lambda^\ge0),其负号 (-\lambda^) 是最优值关于 (b) 的边际变化率。

如果改成相反的约束方向,必须重新检查乘子及灵敏度的符号;不要死背“乘子等于导数”。

二、从对偶证明影子价格,而不是把它当经验公式

写拉格朗日函数: [ L_b(x,\lambda)=f(x)+\lambda(g(x)-b),\quad \lambda\ge0. ] 定义不含右端项常数的 [ q_0(\lambda)=\inf_x{f(x)+\lambda g(x)}. ] 于是: [ \boxed{q_b(\lambda)=q_0(\lambda)-\lambda b.} \tag{2} ] 假设在基准参数 (b_0) 处,原问题最优值有限、强对偶成立、对偶最优乘子 (\lambda_0^) 能达到对偶最优: [ q_{b_0}(\lambda_0^)=v(b_0). ] 对于任何扰动后的可行参数 (b),同一组 (\lambda_0^) 仍然对偶可行;弱对偶给出 [ \begin{aligned} v(b)&\ge q_b(\lambda_0^)
&=q_0(\lambda_0^)-\lambda_0^b
&=v(b_0)-\lambda_0^(b-b_0). \end{aligned} ] 所以有严格结论: [ \boxed{v(b)\ge v(b_0)-\lambda_0^(b-b_0).} \tag{3} ]

这条式子不是“差不多成立”的近似,而是(上述条件下)真正的全局仿射下界。只要 (v) 在 (b_0) 可微,凸函数的子梯度唯一,便得到: [ \boxed{v’(b_0)=-\lambda_0^.} \tag{4} ] 于是对足够小的 (\Delta b): [ v(b_0+\Delta b) =v(b_0)-\lambda_0^\Delta b+o(|\Delta b|). \tag{5} ] 这才是“影子价格”作为局部一阶近似的准确含义:放宽一单位约束,目标值的边际下降量是 (\lambda^*)(对于最小化)。

多条约束的情况

设 [ v(b)=\inf_x f(x),\quad g_i(x)\le b_i,\quad Ax=c,\quad b\in\mathbb R^m. ] 令 (q_b(\lambda,\nu)=q_0(\lambda,\nu)-\lambda^\top b)。若在 (b_0) 强对偶且最优乘子存在,则 [ \boxed{ v(b)\ge v(b_0)-(\lambda_0^)^\top(b-b_0). } \tag{6} ] 因此 (-\lambda_0^) 是 (v) 在 (b_0) 的一个子梯度。若 (v) 在该点可微,则 (\nabla v(b_0)=-\lambda_0^*)。存在多个最优乘子时不能不加检查就声称最优值可微。

为什么称为子梯度?凸函数的子梯度 (s) 满足 (v(b)\ge v(b_0)+s^\top(b-b_0)),恰好与式(6)相同。凸值函数本身也有直接证明:对任意两组参数 (b^{(1)},b^{(2)}) 的可行点 (x_1,x_2),利用凸性可知 (tx_1+(1-t)x_2) 对 (tb^{(1)}+(1-t)b^{(2)}) 可行,且目标值不大于加权和;对接近最优的可行点取极限,即得到 (v(tb^{(1)}+(1-t)b^{(2)})\le tv(b^{(1)})+(1-t)v(b^{(2)}))。这里要求参数对应的最优值适当有限,且共有的等式约束是仿射的。

三、数值算例:完整求解影子价格与活跃集

考虑 [ \boxed{v(b)=\min_{x\le b}\frac12(x-3)^2.} \tag{7} ] 无约束极小点为 (x=3)。故分两种情形: [ x^(b)= \begin{cases} b,&b<3,
3,&b\ge3, \end{cases} \qquad v(b)= \begin{cases} \frac12(b-3)^2,&b<3,
0,&b\ge3. \end{cases} \tag{8} ] 拉格朗日函数 [ L_b(x,\lambda)=\frac12(x-3)^2+\lambda(x-b),\qquad\lambda\ge0. ] KKT 驻点 (x-3+\lambda=0),即 (x=3-\lambda),互补松弛为 (\lambda(x-b)=0)。可得 [ \boxed{\lambda^
(b)=\max{3-b,0}.} \tag{9} ] 此时 (v’(b)=b-3)((b<3)),以及 (v’(b)=0)((b>3)),在 (b=3) 左右导数也都是 0,所以这里一阶可微,但二阶导数在切换点不连续。处于 (b=3) 时,约束恰好活跃,但乘子仍为 0。

上界 (b) 最优点 (x^*) 约束状态 乘子 (\lambda^*) 最优值 (v(b))
1 1 活跃 2 2
1.5 1.5 活跃 1.5 1.125
3 3 活跃但零乘子 0 0
4 3 非活跃 0 0

在 (b_0=1) 时,(\lambda^=2)。若放宽 (\Delta b=0.5),一阶预测 [ v(1.5)\approx v(1)-2(0.5)=1. ] 实际 [ v(1.5)=\tfrac12(1.5-3)^2=1.125. ] 误差 (0.125) 是二阶项:只要 (b_0+\Delta b<3),准确公式是 [ \boxed{v(b_0+\Delta b)-v(b_0) =-\lambda^(b_0)\Delta b+\tfrac12(\Delta b)^2.} \tag{10} ] 影子价格给出局部斜率,并非有限扰动的精确总收益。

乘子还表示什么?

最优乘子常被解释为“资源的边际价值”,但要明确是对当前最优目标值的变化率。它不是随资源增加保持固定的兑换率;当 (b) 进入新的活跃集区域时,乘子可能变成零,甚至出现不可微折点。

四、最优值函数不一定可微:一个反例

考虑线性规划 [ \boxed{v(b)=\min_x x,\qquad -x\le0,\ -x\le b.} \tag{11} ] 两条约束意味着 (x\ge0) 且 (x\ge-b),所以 [ \boxed{v(b)=\max{0,-b}.} \tag{12} ] 在 (b_0=0) 时,两条约束都活跃、最优解 (x^*=0)。

拉格朗日函数 [ L_b(x,\lambda_1,\lambda_2) =x+\lambda_1(-x)+\lambda_2(-x-b). ] 在 (b=0) 的 KKT 驻点: [ 1-\lambda_1-\lambda_2=0,\quad \lambda_1,\lambda_2\ge0. ] 因此 [ \lambda_1=1-\lambda_2,\qquad 0\le\lambda_2\le1. ] 与被扰动的第二条约束相对应的乘子 (\lambda_2) 不唯一。相应子梯度 (-\lambda_2\in[-1,0])。而值函数左右导数为 [ v’-(0)=-1,\qquad v’+(0)=0. ] 所以 (v) 在 (b_0=0) 不可微。但 Slater 并未失败:(x=1) 同时严格满足两条约束。失败的是活跃梯度的线性无关性(两条梯度都是 (-1))。

这解释了三件事:①Slater 不保证乘子唯一;②活跃约束不一定有正乘子;③“影子价格等于一个唯一导数”需要检查可微性。

五、数值迭代与收敛条件:对偶上升如何追踪乘子?

对式(7),内层极小点满足 (x(\lambda)=3-\lambda),得到 [ q_b(\lambda)=(3-b)\lambda-\tfrac12\lambda^2,\qquad \lambda\ge0. ] 固定 (b=1): [ q_1(\lambda)=2\lambda-\tfrac12\lambda^2,\quad q_1’(\lambda)=2-\lambda. ] 投影对偶梯度上升为 [ \boxed{\lambda_{k+1}=\Pi_{\mathbb R_+}\bigl(\lambda_k+\eta(2-\lambda_k)\bigr).} \tag{13} ] 取 (\eta=\tfrac12,\ \lambda_0=0),得到:

(k) (\lambda_k) (q_1(\lambda_k)) 对偶间隙 (v(1)-q_1(\lambda_k))
0 0 0 2
1 1 1.5 0.5
2 1.5 1.875 0.125
3 1.75 1.96875 0.03125
最优 2 2 0

为何可以保证收敛?因为 (\lambda^*=2) 是更新的不动点,而非负半轴投影是非扩张的: [ \begin{aligned} |\lambda_{k+1}-2| &\le |(1-\eta)\lambda_k+2\eta-[(1-\eta)2+2\eta]|
&=|1-\eta|\,|\lambda_k-2|. \end{aligned} ] 当且仅当 (0<\eta<2) 时,此上界因子严格小于 1,于是 [ \boxed{|\lambda_k-2|\le|1-\eta|^k|\lambda_0-2|.} \tag{14} ] 本例可进一步写出 [ v(1)-q_1(\lambda_k)=\tfrac12(\lambda_k-2)^2, ] 故 (\eta=\tfrac12) 时,间隙每步至多变为上一轮的 (1/4)。

边界提醒:收敛结论依赖本例对偶函数的光滑强凹二次结构和合法步长。一般的非光滑对偶函数不满足这里的梯度收缩推导;不能因为“有对偶问题”就保证梯度上升线性收敛。

六、失败反例与误用边界

反例 A:活跃不代表影子价格严格正。 在式(7)的 (b=3),约束 (x\le b) 活跃,但 (\lambda^*=0)。继续放宽上界的局部收益是零。

反例 B:大扰动不能用局部斜率精确估值。 从 (b=1) 放宽到 (b=4),若硬套线性公式,得到 (v(4)\approx 2-2(3)=-4),而真实最优值为 (v(4)=0)。注意 (-4) 仍是式(3)的合法下界,但不是精确预测。变化跨过了活跃集切换点 (b=3)。

反例 C:局部最优可能没有有限 KKT 乘子。 (\min_x x) 且 (x^2\le0) 的唯一可行点为 0,但驻点方程 (1+\lambda(2x)=0) 在 (x=0) 不成立。这里资格条件失败,不能直接用缺失的乘子谈影子价格。

七、数学关系图

flowchart TD
  A["参数化约束 g(x) ≤ b"] --> B["拉格朗日对偶 q_b = q_0 − λᵀb"]
  B --> C["基准点强对偶 + 最优乘子存在"]
  C --> D["全局仿射下界 v(b) ≥ v(b₀) − λ*ᵀ(b−b₀)"]
  D --> E["−λ* 是凸值函数的子梯度"]
  E --> F["若可微:∇v(b₀)=−λ*"]
  E --> G["可能不可微:多重乘子与折点"]
  F --> H["小扰动一阶预测"]
  H --> I["大扰动/活跃集切换:预测未必准确"]
  B --> J["适当光滑与步长 → 可证明对偶迭代收敛"]

八、知识点对照

你想知道的事 正确工具 经常混淆的点
现在是否最优? 凸 KKT / 原始—对偶间隙证书 单靠活跃不能推乘子正
放宽一点资源能改善多少? (-\lambda^*) 局部灵敏度 导数不能当作大扰动精确收益
最优值函数有折点怎么办? 子梯度、方向导数 不能无条件声称导数唯一
算法会收敛吗? 光滑/强凹、步长、投影非扩张证明 强对偶不保证任意迭代收敛

本课一眼记住:(\boxed{\lambda^\ge0,\quad -\lambda^\in\partial v(b_0),\quad v’(b_0)=-\lambda^*\ \text{(可微时)}})。其中子梯度结论需要基准点的强对偶及有限最优乘子存在;不能忘记条件。

九、四级自测(总计 100 分)

首次发送不附标准答案;请勿提前查看独立测验 JSON,防止泄题。 前三题可客观判分,第四题开放推导。

Lv1|影子价格的符号与必要条件|15 分|预计 2 分钟

考虑参数化凸优化问题 v(b)=min f(x),约束 g(x)≤b;采用 L_b(x,λ)=f(x)+λ(g(x)−b),λ≥0。若在 b=b₀ 处强对偶成立、存在最优乘子 λ*,且 v 在 b₀ 可微,下列哪项一定正确?

A. v′(b₀)=+λ*,因为放宽约束会提高最小化目标值。

B. v′(b₀)=−λ,且 λ≥0;这是局部边际变化率,不保证任意有限扰动都能线性精确预测。

C. 只要约束在 b₀ 活跃,就必有 λ*>0。

D. 只要 f 是凸的,对任意 b 都必然存在有限的最优乘子。

提示:固定一组在 b₀ 最优的乘子,把它用于扰动后的问题,构造最优值函数的仿射下界。

Lv2|投影对偶上升的一步迭代|20 分|预计 3 分钟

考虑 minₓ ½(x−4)²,约束 x≤1;其对偶函数为 q(λ)=3λ−½λ²(λ≥0)。从 λ₀=0 出发,用投影对偶梯度上升 λ₁=max{0,λ₀+ηq′(λ₀)},取 η=¼。求 λ₁,填写数值,保留三位小数。

请只填写一个数值。

提示:先求 q′(λ),随后执行一次上升更新和非负投影。

Lv3|局部敏感度与大扰动反例|25 分|预计 5 分钟

对 v(b)=min_{x≤b} ½(x−3)²,已知在 b₀=1 时 v(1)=2、最优乘子 λ*(1)=2。现在把上界从 b₀=1 放宽到 b′=4。下列哪项判断正确?

A. 影子价格给出精确有限变化:v(4)=v(1)−2×3=−4。

B. 真实最优值 v(4)=0;支持不等式 v(4)≥v(1)−2(4−1)=−4 仍成立,但局部线性预测不准确。

C. 因为 λ*(1)>0,约束在 b′=4 仍必活跃,且乘子仍等于 2。

D. v(b) 随 b 放宽必然上升,因此 v(4)>v(1)。

提示:先检查 b′=4 时无约束最优点是否可行,再区分全局下界与局部一阶近似。

Lv4|二维对偶、灵敏度证明与线性收敛|40 分|预计 12 分钟

考虑参数化问题 [ v(b)=\min_{x,y\in\mathbb R}\ \frac12(x-2)^2+\frac12(y-1)^2,\qquad x+y\le b. ] 令约束乘子为 (\lambda\ge0)。

A(12 分):对 (b=1),推导对偶函数 (q_b(\lambda)),求 (x^,y^,\lambda^*,v(1)),并完整检验原始可行、对偶可行、驻点和互补松弛。

B(12 分):对一般问题 (v(b)=\inf{f(x):g_i(x)\le b_i,\ Ax=c}),假设 (b_0) 处强对偶且最优乘子 ((\lambda^,\nu^)) 存在,严格证明任意可行参数 (b) 均满足 [ v(b)\ge v(b_0)-(\lambda^)^\top(b-b_0). ] 解释为何在 (v) 可微时得到 (\nabla v(b_0)=-\lambda^),以及活跃约束为何可能对应零乘子。

C(8 分):本题将 (b=1) 放宽到 (b=1.4),计算真实的 (v(1.4)),给出在 (b=1) 处的一阶预测以及两者之差,并解释为何一阶预测不应当视为精确有限变化。

D(8 分):固定 (b=1),对 (q_b) 采用投影梯度上升,步长 (\eta=\frac14),从 (\lambda_0=0) 出发算出 (\lambda_1,\lambda_2),利用投影非扩张性证明本题乘子误差线性收缩,写出收缩因子及合法步长区间。

提示:先固定 λ 对 x、y 求全局极小;支持不等式来自固定 b₀ 的最优乘子后对扰动问题使用弱对偶;迭代收敛需利用 q 的二次型及投影非扩张性。

十、下一讲与评分安排

第12课|2026年10月31日:对偶问题的求解与对偶次梯度法。 重点理解对偶函数不可微时约束残差为什么给出超梯度,如何选择步长以及为什么固定大步长可能不能精确收敛。每周第7天(第14课)复盘;不因测评结果改变课号。

作答后将逐题按 15、20、25、40 分评分:80 分及以上按原计划继续,60–79 分追加薄弱知识点例子,低于 60 分优先复习 KKT、活跃约束与互补松弛。首次课堂不展示答案,评分要点保存在独立 JSON。