数学优化理论 · 第12课

对偶函数的超梯度与对偶次梯度法:为什么约束残差能更新乘子?

2026年10月31日|第2周第5天|讲授约18分钟(自测另计)

上一课我们证明,最优乘子可以反映放宽约束的边际价值。今天反过来问:如果不知道最优乘子,怎样用算法把它找出来? 更微妙的是,拉格朗日对偶函数一定凹,却未必可微。我们必须区分“导数”“超梯度”和“在何种假设下收敛”。

一、问题、定义与假设

考虑不等式约束问题:

[ p^*=\min_{x\in X} f(x)\quad\text{s.t.}\quad g_i(x)\le0,\ i=1,\dots,m. ]

这里 (X) 是易处理的基础集合,例如盒约束;(g(x)=(g_1(x),\dots,g_m(x))^\top)。采用符号约定 (g_i\le0,\ \lambda_i\ge0)。

拉格朗日函数和对偶函数分别为

[ L(x,\lambda)=f(x)+\lambda^\top g(x),\qquad q(\lambda)=\inf_{x\in X}L(x,\lambda),\quad \lambda\ge0. ]

对偶目标是 (d^=\sup_{\lambda\ge0}q(\lambda))。弱对偶保证 (q(\lambda)\le p^),即使原问题非凸也成立。对固定的 (x),(L(x,\lambda)) 对 (\lambda) 是仿射的;仿射函数族的逐点下确界是凹函数,所以 (q) 凹,但不保证处处可微。

以下“残差是超梯度”的推导要求内层极小值实际达到,且选到一个全局极小点。为讨论收敛界,可假设 (X) 非空紧致、(f,g_i) 在 (X) 上连续,从而内层极小点存在且 (|g(x)|) 有上界;还要另行假设存在有限的最优对偶乘子 (\lambda^*)。凸性和 Slater 可用于保证适当条件下的强对偶,但它们不是超梯度代数推导本身的必要条件。

二、为什么约束残差是对偶函数的超梯度?

对凹函数 (q),向量 (s) 称为 (\lambda) 处的超梯度,若对任意合法 (\mu\ge0),

[ \boxed{q(\mu)\le q(\lambda)+s^\top(\mu-\lambda).}\tag{1} ]

注意不等号是“(\le)”:凹函数的超梯度给出上方支撑平面。文献常把最大化凹对偶函数的方法称为“对偶次梯度法”(dual subgradient method),但此处按凹函数符号,更准确的是超梯度上升。

固定 (\lambda_k),求出

[ x_k\in\arg\min_{x\in X}L(x,\lambda_k). ]

对任意 (\mu\ge0),依次有

[ \begin{aligned} q(\mu) &=\inf_{x\in X}L(x,\mu)
&\le L(x_k,\mu)
&=L(x_k,\lambda_k)+g(x_k)^\top(\mu-\lambda_k)
&=q(\lambda_k)+g(x_k)^\top(\mu-\lambda_k). \end{aligned} ]

与式(1)比较,得到

[ \boxed{s_k=g(x_k)\in\partial^+q(\lambda_k).}\tag{2} ]

这一步完全不需要对 (x_k) 关于 (\lambda) 求导,也不要求 (q) 光滑。若内层有多个全局极小点,不同极小点可能给出不同的合法超梯度;不能武断地说 (q’(\lambda)=g(x_k)) 总成立。

对偶投影超梯度上升为

[ \boxed{\lambda_{k+1}=\Pi_{\mathbb R_+^m}\bigl(\lambda_k+\alpha_k g(x_k)\bigr).}\tag{3} ]

它有直接的物理意义:若 (g_i(x_k)>0),当前内层解违反第 (i) 条约束,对应乘子增大;若 (g_i(x_k)<0),该约束有余量,乘子趋向减小;投影保证 (\lambda_i\ge0)。请注意:(x_k) 是内层极小点,不一定是原问题可行点。约束残差更新乘子,不等于已经找到原始可行解。

三、非光滑的完整例子:折点为什么出现?

考虑一维问题

[ \min_{0\le x\le2}x,\qquad 1-x\le0. ]

原问题等价于在 ([1,2]) 上最小化 (x),故 (x^=1,\ p^=1)。取 (x=1.5) 可严格满足不等式;本题为凸问题,具有 Slater 点。

拉格朗日函数

[ L(x,\lambda)=x+\lambda(1-x)=\lambda+(1-\lambda)x. ]

内层是在 (0\le x\le2) 上最小化一个关于 (x) 的线性函数:

[ x(\lambda)= \begin{cases} 0,&0\le\lambda<1,
\text{任意 }x\in[0,2],&\lambda=1,
2,&\lambda>1. \end{cases} ]

所以

[ \boxed{ q(\lambda)= \begin{cases} \lambda,&0\le\lambda\le1,
2-\lambda,&\lambda\ge1. \end{cases} =1-|\lambda-1|,\quad\lambda\ge0.}\tag{4} ]

这个对偶函数是凹的“倒 V”形,在 (\lambda=1) 不可微;其最大值是 (d^=1=p^),最优乘子 (\lambda^*=1)。

在 (\lambda<1) 时,内层极小点 (x=0),残差 (g(x)=1),所以算法向右走;在 (\lambda>1) 时,内层极小点 (x=2),残差 (g(x)=-1),算法向左走。折点处 (x=0,1,2) 都是内层极小点,分别给出 (+1,0,-1) 等合法超梯度;(\partial^+q(1)) 在本例包含区间 ([-1,1])。

KKT 检查:在原始最优点 (x^=1) 处,约束活跃 (1-x^=0),乘子 (\lambda^=1\ge0);驻点为 (1-\lambda^=0);互补松弛为 (\lambda^(1-x^)=0)。活跃状态来自约束取等号,而非乘子符号的猜测。

四、手算五步:对偶值不一定单调上升

取 (\lambda_0=0),步长 (\alpha_k=0.6/(k+1))。根据式(3),逐步得到:

(k) 当前 (\lambda_k) 内层极小点 (x_k) 残差 (1-x_k) 步长 (\alpha_k) 更新后 (\lambda_{k+1}) 当前对偶值 (q(\lambda_k))
0 0.00 0 +1 0.60 0.60 0.00
1 0.60 0 +1 0.30 0.90 0.60
2 0.90 0 +1 0.20 1.10 0.90
3 1.10 2 −1 0.15 0.95 0.90
4 0.95 0 +1 0.12 1.07 0.95

由于 (q(1.07)=0.93<q(0.95)=0.95),对偶上升法并不保证每一步目标都上升。本例内层解也会在不可行的 (x=0) 和可行但非最优的 (x=2) 之间切换;必须分别处理原始可行性和对偶最优值。

五、收敛保证:从投影非扩张性严格推导

令 (s_k=g(x_k))。假设全部内层问题精确求解,最优对偶乘子 (\lambda^) 存在,并且 (|s_k|\le G)。令初始距离 (R=|\lambda_0-\lambda^|)。

由超梯度不等式:

[ d^-q(\lambda_k)=q(\lambda^)-q(\lambda_k) \le s_k^\top(\lambda^*-\lambda_k).\tag{5} ]

又因为投影到闭凸集是非扩张的,并且 (\Pi_{\mathbb R_+^m}(\lambda^)=\lambda^),

[ \begin{aligned} |\lambda_{k+1}-\lambda^|^2 &\le|\lambda_k+\alpha_ks_k-\lambda^|^2
&=|\lambda_k-\lambda^|^2+ 2\alpha_ks_k^\top(\lambda_k-\lambda^)+\alpha_k^2|s_k|^2
&\le|\lambda_k-\lambda^|^2- 2\alpha_k(d^-q(\lambda_k))+\alpha_k^2G^2. \end{aligned} ]

移项,(k=0,\ldots,K-1) 累加,中间的距离平方项望远镜相消,得到

[ 2\sum_{k=0}^{K-1}\alpha_k(d^*-q(\lambda_k)) \le R^2+G^2\sum_{k=0}^{K-1}\alpha_k^2.\tag{6} ]

由于每个对偶差距非负,前 (K) 次的最佳对偶值满足

[ \boxed{ d^*-\max_{0\le k<K}q(\lambda_k) \le\frac{R^2+G^2\sum_{k<K}\alpha_k^2} {2\sum_{k<K}\alpha_k}.}\tag{7} ]

这是有明确假设的收敛结论,不是对任意启发式更新的保证。

步长方案与保证的差别:

步长 由式(7)能保证什么 不可擅自推断
固定 (\alpha>0) 最佳值差距 (\le R^2/(2K\alpha)+\alpha G^2/2) 不能保证固定步长下精确收敛或逐步单调
已知运行轮数 (K),取 (\alpha=R/(G\sqrt K))((R,G>0)) 最佳对偶值差距 (\le RG/\sqrt K) 不等于每个迭代点都有同样误差界
(\alpha_k=a/(k+1)),(a>0) 因 (\sum\alpha_k=\infty,\ \sum\alpha_k^2<\infty),式(7)右侧趋零 不代表每一步对偶值单调,也不自动给有限步原始可行性证书

上面的 (O(K^{-1/2})) 是一般有界超梯度情形下的最佳对偶目标值误差保证,不是一般的乘子距离线性收敛率。若对偶函数还具有光滑性、强凹性等条件,可以使用不同的更快收敛分析,但不能把这些额外条件省略。

六、失败反例与近似内层计算

失败一:固定步长导致振荡。 仍用式(4),取常数步长 (\alpha=0.6),从 (\lambda_0=0) 开始:

[ 0\longrightarrow0.6\longrightarrow1.2 \longrightarrow0.6\longrightarrow1.2\longrightarrow\cdots. ]

在 1 左右反复越过折点,乘子不收敛。这并不与固定步长的误差上界冲突。

失败二:内层没有求到全局极小。 若 (x_k) 只是局部极小或任意候选点,则一般没有 (L(x_k,\lambda_k)=q(\lambda_k)),式(2)最后一个等号不能成立;约束残差不再自动是精确超梯度。

如果能够严格保证内层误差

[ L(x_k,\lambda_k)\le q(\lambda_k)+\varepsilon_k, \qquad \varepsilon_k\ge0, ]

那么仍有

[ q(\mu)\le q(\lambda_k)+g(x_k)^\top(\mu-\lambda_k)+\varepsilon_k. ]

即得到带 (\varepsilon_k) 误差的超梯度,并可把式(7)的分子改为

[ R^2+G^2\sum_{k<K}\alpha_k^2+ 2\sum_{k<K}\alpha_k\varepsilon_k. ]

因此,内层精度不能毫无代价地忽略;内层误差若长期不能减小,算法可能只收敛到某个误差邻域。

失败三:只看乘子更新或对偶值不能宣称原始最优。 内层解可能不可行;强对偶、对偶值收敛与恢复原始可行最优解不是同一件事。应另行验证原始可行性、互补松弛以及原始—对偶间隙。

七、方法关系图

flowchart TD
 A["给定乘子 λk"] --> B["全局求解内层 argmin L(x,λk)"]
 B --> C["约束残差 sk=g(xk)"]
 C --> D["凹对偶函数的超梯度"]
 D --> E["投影上升 λk+1=Π+(λk+αk sk)"]
 E --> A
 C --> F["精确求解 + 有界残差 + 对偶最优达到"]
 F --> G["望远镜求和得到最佳对偶值误差界"]
 B --> H["内层近似解?"]
 H --> I["需控制 εk 误差,不能声称精确超梯度"]

八、重点回顾与下一讲

今天可以用一条逻辑链记忆:

[ \boxed{\text{内层全局最小点}\Rightarrow \text{约束残差是超梯度}\Rightarrow \text{投影乘子上升}\Rightarrow \text{有条件的最佳对偶值收敛界}.} ]

最值得记住的区别是:(q) 凹但未必可微;约束违反量是正确的上升方向信息,但并不保证每一步单调;固定步长可能振荡;理论通常首先保证最佳对偶值,而非原始解每步可行或线性收敛。

下一讲(2026年11月1日,第13课):对偶分解、原始解恢复与增广拉格朗日思想。我们将讨论多个子问题共享资源约束时如何分布式求解,以及为什么给拉格朗日函数增加二次罚项有助于抑制非光滑和振荡。11月2日第14课为第二周复盘。


九、今日四级自测(100分,答案不在讲义中)

请先独立作答;首次发课不公布选项答案、数值答案或开放题评分标准,也请不要提前打开独立测验 JSON。

Lv1|超梯度的必要前提|15分|预计2分钟

考虑 q(λ)=inf_{x∈X}[f(x)+λg(x)],λ≥0,且内层下确界可达到。哪项一定正确?

A. 原问题凸就保证 q 在每个 λ 处可微。

B. 任取内层的全局极小点 x_λ,残差 g(x_λ) 是凹函数 q 在 λ 处的超梯度。

C. 任取一个原始可行点 x,其残差 g(x) 都是 q 的超梯度。

D. 用合法超梯度与任何固定正步长,都能保证每一步 q 严格上升。

提示:先写出超梯度上支撑不等式,注意内层必须取到下确界。

Lv2|一次投影对偶更新|20分|预计3分钟

原问题为 min_{0≤x≤2} x,约束 1−x≤0。给定 λ₀=0.5、步长 α₀=0.4;先精确求 x₀∈argmin_{0≤x≤2}[x+λ₀(1−x)],然后做 λ₁=max{0,λ₀+α₀(1−x₀)}。求 λ₁(保留三位小数,只填数值)。

提示:固定 λ₀ 后,内层目标是关于 x 的一次函数;先找端点再更新。

Lv3|固定步长的多步反例|25分|预计5分钟

仍考虑 q(λ)=min{λ,2−λ}(λ≥0),用精确内层极小点的残差执行投影超梯度上升,常数步长 α=0.6,从 λ₀=0 开始。λ<1 时选 x=0,λ>1 时选 x=2。哪项描述正确?

A. λ₁=0.6,λ₂=1.2,λ₃=0.6;此算法发生振荡。

B. λ₁=0.6,λ₂=1.2,λ₃=1.8;对偶值单调上升。

C. λ₁=0.6,λ₂=1.2,λ₃=1.0;第三步命中最优乘子。

D. λ>1 时残差为 +1,因此此后乘子会一直增大。

提示:先判断 λ 在折点两侧时的残差符号,再连续更新三次。

Lv4|非光滑对偶、收敛界与近似内层|40分|预计12分钟

考虑 min_{0≤x≤2} x,s.t. 1−x≤0,L(x,λ)=x+λ(1−x),λ≥0。A(10分):分段推导 q(λ),求原始与对偶最优值、最优乘子,并解释 λ=1 为什么不可微以及该点有哪些合法超梯度。B(14分):从 q(μ)≤L(x_k,μ) 出发证明 s_k=g(x_k) 为超梯度;再利用投影非扩张性,在存在 λ*、   s_k   ≤G、R=   λ₀−λ*   的假设下,推导前 K 步最佳对偶值误差 ≤[R²+G²Σ_{k<K}α_k²]/[2Σ_{k<K}α_k]。C(8分):比较固定步长 α>0 与 α_k=a/(k+1) 的收敛结论,指出哪些量有保证、哪些没有。D(8分):若内层仅满足 L(x_k,λ_k)≤q(λ_k)+ε_k,推导带 ε_k 的超梯度不等式,指出收敛界需增加的误差项。
*提示:B部分先展开   λ_k+α_ks_k−λ*   ²,再由凹函数的超梯度不等式换成 q(λ)−q(λ_k);D部分记住不再有 L(x_k,λ_k)=q(λ_k)。

评分与课程安排:Lv1 15分、Lv2 20分、Lv3 25分、Lv4 40分。作答后逐题评分;总分≥80继续,60–79补例子,<60复习;测评不改变日期课号。课堂不附答案,答案及开放题细则仅存于独立 JSON。