数学优化理论 · 第13课:对偶分解、原始解恢复与增广拉格朗日

2026年11月1日|第2周第6天|授课约18分钟(自测另计)

上一课证明,精确求解拉格朗日内层最小化后,约束残差构成对偶函数的超梯度。今天往前推进一步:当多个优化子问题通过共同资源约束连接时,能否让它们并行求解?为什么对偶值已经接近最优,返回的原始变量却仍不满足共享约束?增广拉格朗日能解决哪些问题,又牺牲了什么?

一、问题及假设:两个局部优化器,共享一个资源限制

考虑凸优化问题

[ \begin{aligned} (P)\quad\min_{0\le x,y\le2}&\quad f(x,y)=\tfrac12x^2+y^2,
\text{s.t.}&\quad x+y\ge2. \end{aligned} ]

可以把 (x,y) 看作两个 Worker 的资源投入:各自具有成本 (f_1(x)=x^2/2)、(f_2(y)=y^2),系统要求总投入至少为2。

假设两个局部盒约束和成本可以独立处理,但共享不等式把它们联结起来。目标严格凸,可行集非空、紧、凸。点 ((1.5,1.5)) 在盒内部且严格满足 (x+y>2),所以 Slater 成立;因此标准凸对偶理论适用。

把耦合约束写为 (g(x,y)=2-x-y\le0),引入 (\lambda\ge0)。

二、对偶分解:为什么固定乘子后能并行?

[ \begin{aligned} L(x,y,\lambda) &=\tfrac12x^2+y^2+\lambda(2-x-y)
&=\underbrace{(\tfrac12x^2-\lambda x)}{\text{子问题1}} +\underbrace{(y^2-\lambda y)}{\text{子问题2}} +2\lambda. \end{aligned} ]

由于局部变量的定义域是直积 ([0,2]\times[0,2]),因此

[ q(\lambda)=2\lambda+ \min_{0\le x\le2}(\tfrac12x^2-\lambda x) +\min_{0\le y\le2}(y^2-\lambda y). ]

这是真正的数学分解:固定价格 (\lambda),两个局部求解器能够独立、甚至并行计算。并行性来自目标/局部集合的可分性,而不是任何带约束问题引入乘子后都自动可分。

内层一阶条件分别给出 (x-\lambda=0) 和 (2y-\lambda=0),再考虑盒约束:

[ x(\lambda)=\min{\lambda,2},\qquad y(\lambda)=\min{\lambda/2,2}\qquad(\lambda\ge0). ]

在 (0\le\lambda\le2) 时两者均不触及上界,代回得到

[ \boxed{q(\lambda)=2\lambda-\tfrac34\lambda^2,\quad q’(\lambda)=2-\tfrac32\lambda.} ]

这里的导数恰好是共享约束残差 (2-x(\lambda)-y(\lambda))。超出该区间时,上面的二次表达式不能直接沿用;例如 (2\le\lambda\le4) 时 (q(\lambda)=2-\lambda^2/4),而 (\lambda\ge4) 时 (q(\lambda)=6-2\lambda)。

由于局部目标强凸,内层极小点唯一,对偶函数在此例中可微。一般仅有凸性时内层解可能不唯一,对偶函数也可能不可微,应改用上一课的超梯度结论。

三、KKT 与强对偶:先确认真正的答案

在最优点,盒约束未活跃,KKT 驻点给出

[ x^-\lambda^=0,\qquad 2y^-\lambda^=0. ]

如果共享约束不活跃,互补松弛会要求 (\lambda^=0),导致 (x=y=0),违反共享约束,因此共享约束活跃,即 (x^+y^*=2)。代入:

[ \lambda^+\tfrac12\lambda^=2 \quad\Rightarrow\quad \boxed{\lambda^=\tfrac43,\ x^=\tfrac43,\ y^*=\tfrac23}. ]

原始可行:(x^+y^=2),且二者均在盒内。对偶可行:(\lambda^\ge0)。驻点:(x^-\lambda^=2y^-\lambda^=0)。互补松弛:(\lambda^(2-x^-y^)=0)。故满足 KKT 且由凸性推出全局最优。最优值

[ \boxed{p^=\tfrac12\cdot\tfrac{16}{9}+\tfrac49 =\tfrac43=q(\tfrac43)=d^.} ]

这也是一个活跃约束且乘子为正的例子;但一般情况下活跃约束的乘子仍然可能为零,不可倒推严格互补。

四、对偶梯度迭代:下界不断变好,原始点却不一定可行

使用投影对偶梯度上升

[ \lambda_{k+1}= [\lambda_k+\alpha(2-x_k-y_k)]_+, \quad x_k=x(\lambda_k),\quad y_k=y(\lambda_k). ]

取 (\alpha=1/3,\lambda_0=0)。由于迭代始终位于 ([0,4/3]\subset[0,2]),可以代入 (x_k=\lambda_k,y_k=\lambda_k/2):

[ \lambda_{k+1}=\lambda_k+\tfrac13(2-\tfrac32\lambda_k) =\tfrac12\lambda_k+\tfrac23. ]

因此 (\lambda^*=4/3) 是不动点,且

[ \boxed{|\lambda_{k+1}-\lambda^| =\tfrac12|\lambda_k-\lambda^|,\qquad \lambda_k=\tfrac43(1-2^{-k}).} ]

迭代保持在 ([0,4/3]) 且以收缩因子 (1/2) 线性收敛。这是本例光滑强凹二次对偶函数和合法步长的结论,不是一般对偶次梯度法的通用线性收敛定理。

(k) (\lambda_k) 内层 (x_k,y_k) 违反量 (r_k=2-x_k-y_k) 对偶下界 (q(\lambda_k))
0 0 ((0,0)) 2 0
1 (2/3) ((2/3,1/3)) 1 1
2 1 ((1,1/2)) (1/2) (5/4)
3 (7/6) ((7/6,7/12)) (1/4) (21/16)
极限 (4/3) ((4/3,2/3)) 0 (4/3)

请注意:前四轮内层点都满足 (x_k+y_k<2),因此这些点均不是原问题可行点,它们的目标值不能用作原始最优值的上界。对偶下界 (q(\lambda_k)) 可靠,但尚不足以构成完整上下界证书。

五、原始解恢复:把下界与可行上界配成证书

本例可以将内层点欧氏投影到联合可行集。对于上表各轮,令

[ r_k=2-x_k-y_k>0,\quad (\widehat x_k,\widehat y_k) =(x_k+r_k/2,\ y_k+r_k/2). ]

这样 (\widehat x_k+\widehat y_k=2),两个分量也在 ([0,2]) 内。因此它给出合法原始可行点;投影只是在本例具备简单闭式,一般问题的恢复可能是另一项困难的优化任务。

(k) 恢复后 ((\widehat x,\widehat y)) 原始可行上界 (U=f(\widehat x,\widehat y)) 对偶下界 (q(\lambda_k)) 可认证间隙 (U-q)
0 ((1,1)) (3/2) 0 (3/2)
1 ((7/6,5/6)) (11/8) 1 (3/8)
2 ((5/4,3/4)) (43/32) (5/4) (3/32)
3 ((31/24,17/24)) (171/128) (21/16) (3/128)

例如第2轮:((x_2,y_2)=(1,1/2)),残差 (r_2=1/2),各增加 (1/4),得到 ((5/4,3/4))。它的目标值是 (43/32),而 (q(1)=5/4),因此

[ \boxed{\tfrac54\le p^\le\tfrac{43}{32},\qquad 0\le U-p^\le\tfrac3{32}.} ]

这才是严格的最优性误差证书,因为同时满足原始可行和对偶可行。注意简单平均多轮不可行点不必可行;“对偶值收敛”也并不自动使某个有限轮内层点可行。

六、增广拉格朗日:用二次罚项换取什么?

普通拉格朗日的优点是分解简单;在非严格凸目标或内层解不唯一时,对偶函数可能出现尖点、乘子迭代振荡。增广拉格朗日通过罚项加强对约束残差的控制,但有代价。

先看等式版本 (h(x,y)=x+y-2=0)(它与原问题可行域不同,但在本例具有同一个最优点)。令 (\nu\in\mathbb R)、(\rho>0):

[ \boxed{L_\rho(x,y,\nu) =f(x,y)+\nu(x+y-2)+\tfrac{\rho}{2}(x+y-2)^2.} ]

原始对偶交替方法可以先(近似或精确)最小化 (L_\rho),再更新 (\nu_{k+1}=\nu_k+\rho h(x_{k+1},y_{k+1}))。二次项展开含 (2xy),在目标中形成交叉项 (\rho xy),于是固定 (\nu) 的内层不再是两个完全独立的局部优化问题。较好的数值稳定性并不自动意味着更低计算耗时。

如果保留原始不等式 (g=2-x-y\le0),一种标准的增广拉格朗日形式是

[ L_\rho^{\rm ineq}(x,y,\lambda)= f(x,y)+\frac{[\lambda+\rho g(x,y)]_+^2-\lambda^2}{2\rho}, \quad \lambda\ge0, ]

并使用 (\lambda^+=[\lambda+\rho g(x^+,y^+)]+)。这里 ([t]+=\max(t,0))。它不是简单将普通拉格朗日加上 (\tfrac\rho2[g]_+^2) 就可不加区别地套用全部标准 ALM 结论。一般凸性、鞍点存在、内层求解精度及参数策略等假设影响收敛保证;非凸或近似求解情形还需额外分析。

七、失败反例:对偶最优也可能给出不可行内层点

把目标改成线性的:

[ \min_{0\le x,y\le2} x+y,\quad \text{s.t. }x+y\ge2. ]

此时 (p^*=2),拉格朗日函数为

[ L=(1-\lambda)(x+y)+2\lambda,\quad \lambda\ge0. ]

对偶函数

[ q(\lambda)= \begin{cases} 2\lambda,&0\le\lambda\le1,
4-2\lambda,&\lambda\ge1. \end{cases} ]

在最优乘子 (\lambda^*=1) 处,(L\equiv2):整个盒 ([0,2]^2) 的点都是内层极小点。选择 ((0,0)) 仍违反原问题约束!因此“乘子最优、内层求解正确”并不足以保证任取内层极小点都原始可行。若从 (\lambda_0=0) 采用固定步长 (\alpha=1) 和折点两侧的端点内层解,乘子甚至会在 (0\leftrightarrow2) 间振荡。

八、关系图与本讲结论

flowchart TD
 A["原始共享约束:x+y≥2"] --> B["引入价格乘子 λ≥0"]
 B --> C["固定 λ:两个局部子问题可并行"]
 C --> D["返回局部解 x(λ), y(λ)"]
 D --> E["残差 r=2−x−y"]
 E --> F["投影更新 λ←[λ+αr]₊"]
 D --> G["原始恢复:投影到联合可行集"]
 F --> C
 F --> H["对偶下界 q(λ)"]
 G --> I["可行目标上界 U"]
 H --> J["间隙 U−q(λ) 认证"]
 I --> J
 B --> K["增广罚项可能带来交叉耦合 ρxy"]

本课的逻辑是:先用价格乘子解除共享约束的计算耦合,得到各局部解和对偶下界;再检查或恢复原始可行点,建立可靠的上下界间隙;最后在收敛稳定性与分解代价之间权衡是否采用增广拉格朗日。

方法/对象 能保证什么(在相应假设下) 容易误解的地方
对偶分解 固定乘子后局部问题独立求解 内层原始点未必可行
约束残差更新 精确内层下构造合法超梯度 不保证每轮对偶值单调
可行恢复与对偶证书 (q(\lambda)\le p^*\le f(\widehat x,\widehat y)) 仅凭小残差不能跳过可行性检查
增广拉格朗日 可改善一些问题的残差控制与收敛表现 二次罚项可能破坏可分性,不能保证普遍提速

九、四级自测(100分;首次不附答案)

下面四题首次发送不泄露标准答案。前三题客观评分,Lv4 检查证明步骤。请独立作答。

Lv1|对偶分解的适用条件|15分|预计2分钟|单选

考虑对偶分解和原始解恢复,以下哪项一定正确?

A. 每轮精确最小化拉格朗日函数所得的原始变量,一定满足全部原始耦合约束。

B. 强对偶成立且已找到最优乘子时,任取该乘子下的内层极小点都必然是原始最优解。

C. 当目标、局部可行集可分,仅有共享约束耦合时,固定乘子可分解并行求解;但内层点是否原始可行必须单独检查。

D. 增广拉格朗日中的二次罚项绝不会破坏子问题的可分性。

提示:区分局部内层极小化和原问题共享约束。

Lv2|乘子的一步更新|20分|预计3分钟|数值

考虑 min ½x²+2y²,约束 x+y≥3、0≤x,y≤4,使用 L=½x²+2y²+λ(3−x−y),λ≥0。给定 λ₀=1、步长 α=0.2,先精确求内层极小点 (x₀,y₀),再执行 λ₁=max{0, λ₀+α(3−x₀−y₀)}。求 λ₁,保留三位小数。

提示:先计算该点的共享约束违反量,再更新。

Lv3|对偶最优与原始可行的反例|25分|预计5分钟|单选

考虑 min 2x+3y,约束 x+y≥1、0≤x,y≤1,并用 λ≥0 松弛约束 1−x−y≤0。关于 λ=2 时的对偶函数及对应内层极小点,下列哪项正确?

A. λ=2 是对偶最优乘子之一,但内层极小点 (0,0) 仍可能违反原始共享约束。

B. λ=2 时对偶函数值为零,因此尚未达到对偶最优。

C. λ=2 时内层极小点必然唯一且等于原始最优点 (1,0)。

D. 由于原始盒约束的存在,严格可行点不存在,所以强对偶必然失败。

提示:检查对偶最优乘子处的内层目标是否仍能区分各原始点。

Lv4|分解、收敛、可行恢复与增广罚项|40分|预计12分钟|开放题

综合题:设 P: min_{0≤x,y≤3} x²+½y²,约束 x+y≥3,令 L(x,y,λ)=x²+½y²+λ(3−x−y)、λ≥0。(A,12分) 求 0≤λ≤3 的内层解与对偶函数,求原始和对偶最优解,完整核验 KKT 四组条件。(B,10分) 从 λ₀=0、α=1/3 出发,计算 λ₁、λ₂、λ₃,并在迭代区间证明乘子误差的线性收缩因子。(C,10分) 用 λ₂ 时的内层点 (x₂,y₂),令 r=3−x₂−y₂,并采用 (x̂,ŷ)=(x₂+r/2,y₂+r/2) 恢复原始可行性;求 U=f(x̂,ŷ)、下界 q(λ₂) 和可认证间隙 U−q(λ₂),解释仅有小对偶误差为什么不足以证明任意内层点可行。(D,8分) 把约束改为等式 h=x+y−3,写出增广拉格朗日并指出哪一个展开项破坏 x/y 的可分性;解释它为何不保证普遍提速。

提示:内层一阶条件、固定点收缩、原始可行上界和交叉耦合分别是四段证明的切入点。

十、下节预告

第14课(2026年11月2日):第二周复盘。 将把 Slater/LICQ/MFCQ、KKT、弱/强对偶、影子价格、超梯度、对偶分解和原始恢复串成一条完整推理链,重点复盘活跃约束、零乘子、互补松弛及对偶最优但原始不可行的区别。

本课自测分值为 15+20+25+40=100。作答后逐题评分与反馈:80分及以上继续,60–79分补薄弱点,低于60分优先复习 KKT/对偶基础;成绩不更改日期课号。