数学优化理论 · 第27课:算子分裂——Forward–Backward、Douglas–Rachford 与非扩张算子
2026-11-15|第4周第6天|18分钟(自测另计)
上一讲我们把近端梯度映射、FISTA 与局部二次上界联系起来。今天换一个视角:不直接分析函数值,而是把最优性条件改写为单调算子的零点,再用不动点迭代求解。这条路线可统一解释 Prox、投影、Forward–Backward(FB)与 Douglas–Rachford Splitting(DRS),也是下周学习 ADMM、PDHG 的准备。
一、问题、假设与两种分裂
考虑 (\min_x F(x)=g(x)+h(x)),其中 (g,h:\mathbb R^n\to(-\infty,+\infty]) 均为真、下半连续、凸函数。两种情况:
- FB: (g=f) 可微、凸且 (L)-Smooth,(h) 可非光滑;假设最优点存在。
- DRS: (g,h) 都允许非光滑;为确保 DRS 固定点存在,额外假设存在原对偶最优性分解:(x^,a^,b^) 使 (a^\in\partial g(x^))、(b^\in\partial h(x^))、(a^+b^*=0)。满足适当资格条件时,可以从原问题最优性得到这种分解。
以下收敛讨论均在有限维欧氏空间、精确 Prox 运算下进行。
关键最优性包含式:
[ \boxed{0\in\partial g(x^)+\partial h(x^)}. \tag{1} ]
若 (g=f) 光滑,改写为 (0\in\nabla f(x^)+\partial h(x^))。注意未经资格条件不能把任意 (\partial(g+h)) 简单替换成两项次微分之和。
二、从次梯度到 Resolvent
对算子 (A),定义 resolvent(预解算子):
[ J_{\gamma A}=(I+\gamma A)^{-1},\quad\gamma>0. ]
当 (A=\partial g) 时,近端最优性条件
[ 0\in\partial g(p)+\frac{p-v}{\gamma} ]
等价于 (v\in p+\gamma\partial g(p)),因此
[ \boxed{J_{\gamma\partial g}(v)=\operatorname{prox}_{\gamma g}(v).} \tag{2} ]
这就把“求解一个近端优化子问题”变成“计算一个单调算子的 resolvent”。
单调性: 对任意 (a\in A(x),b\in A(y)),若 (\langle a-b,x-y\rangle\ge0),称 (A) 单调。凸次微分 (\partial g) 具有单调性;真、下半连续、凸函数的次微分还是最大单调算子。
2.1 为什么 Prox 是坚固非扩张的?
记 (p=P(u),q=P(v)),其中 (P=\operatorname{prox}_{\gamma g})。由最优性:
[ \frac{u-p}{\gamma}\in\partial g(p),\quad \frac{v-q}{\gamma}\in\partial g(q). ]
应用次微分单调性:
[ \left\langle (u-p)-(v-q),p-q\right\rangle\ge0. ]
移项:
[ \boxed{|p-q|^2\le\langle p-q,u-v\rangle.} \tag{3} ]
称为 firm nonexpansiveness(坚固非扩张性)。再由 Cauchy–Schwarz,得到普通非扩张性 (|Pu-Pv|\le|u-v|)。
定义反射算子:
[ R_g=2\operatorname{prox}_{\gamma g}-I. ]
展开平方:
[
\begin{aligned}
|R_g(u)-R_g(v)|^2
&=|2(p-q)-(u-v)|^2
&=|u-v|^2+4|p-q|^2-4\langle p-q,u-v\rangle
&\le|u-v|^2.
\end{aligned}
]
所以
[ \boxed{R_g\text{ 非扩张(Lipschitz 常数至多 }1\text{)}.} \tag{4} ]
这不是严格收缩:例如 (g=0) 时 (P=I,R_g=I)。
三、Averaged 算子为什么容易收敛?
如果
[ \boxed{T=(1-\theta)I+\theta R,\qquad 0<\theta<1,} \tag{5} ]
其中 (R) 非扩张,则称 (T) 是 (\theta)-averaged 算子。特别地,firmly nonexpansive 等价于 (1/2)-averaged。
若 (x^\in\operatorname{Fix}(T)),则 (Rx^=x^*)。利用平方范数的凸组合恒等式以及 (R) 非扩张:
[
\begin{aligned}
|Tx-x^|^2
&\le(1-\theta)|x-x^|^2+\theta|Rx-x^|^2
&\quad-\theta(1-\theta)|x-Rx|^2
&\le|x-x^|^2-\frac{1-\theta}{\theta}|x-Tx|^2.
\end{aligned}
\tag{6}
]
由此得到 Fejér 单调性:到任一固定点的距离不增,同时残差平方可求和。对 (x_{k+1}=Tx_k),若固定点非空,则
[ \sum_{k=0}^\infty|x_k-Tx_k|^2<\infty,\quad |x_k-Tx_k|\to0. ]
有限维下,迭代有界,存在聚点;连续性保证聚点是固定点;结合 Fejér 单调性可证整个序列收敛到某个固定点。这里通常不能声称固定点唯一或有线性收敛速度。
四、Forward–Backward:一个梯度步 + 一个 Prox
对于
[ \min_x f(x)+h(x) ]
且 (f) 凸、(L)-Smooth,令
[ \boxed{T_{\rm FB}(x)=\operatorname{prox}_{\gamma h}(x-\gamma\nabla f(x)).} \tag{7} ]
因此
[ x_{k+1}=T_{\rm FB}(x_k). ]
为什么叫 Forward–Backward?Forward 指显式梯度步 (I-\gamma\nabla f);Backward 指隐式 resolvent (J_{\gamma\partial h})。最优性的固定点等价关系为:
[ x=T_{\rm FB}(x)\iff0\in\nabla f(x)+\partial h(x). ]
4.1 迭代收敛需要什么步长?
凸且 (L)-Smooth 的梯度具有 (1/L)-cocoercivity:
[ \boxed{ \langle\nabla f(x)-\nabla f(y),x-y\rangle \ge\frac1L|\nabla f(x)-\nabla f(y)|^2. } \tag{8} ]
这可由对 (f(\cdot)-\langle\nabla f(y),\cdot\rangle) 应用光滑下降引理、再对 (x,y) 对称交换推导,故不是“梯度 Lipschitz 即可”——这里还需要凸性。
记 (d=x-y,b=\nabla f(x)-\nabla f(y))。则
[
\begin{aligned}
|(I-\gamma\nabla f)x-(I-\gamma\nabla f)y|^2
&=|d|^2-2\gamma\langle d,b\rangle+\gamma^2|b|^2
&\le|d|^2-\gamma(2/L-\gamma)|b|^2.
\end{aligned}
]
因此 (0<\gamma\le2/L) 时梯度映射非扩张。进一步,令 (\alpha=\gamma L/2\in(0,1)),有
[ I-\gamma\nabla f=(1-\alpha)I+\alpha(I-2\nabla f/L), ]
而括号内非扩张,所以它是 averaged 算子。Prox 是 (1/2)-averaged;两个 averaged 算子的复合仍是 averaged。由第三节的固定点论证:
[ \boxed{0<\gamma<2/L\Longrightarrow x_k\to x^\infty\in\arg\min(f+h).} \tag{9} ]
这里是迭代点收敛保证;并非在所有这些步长下,都能直接套用前面 (O(1/K)) 的单调函数值证明。
当 (0<\gamma\le1/L) 时,上一周的近端三点不等式给出:
[ F(x_{k+1})-F(z)\le \frac{|x_k-z|^2-|x_{k+1}-z|^2}{2\gamma}. ]
取 (z=x^*),求和并利用函数值单调不增:
[ \boxed{F(x_K)-F^\le\frac{|x_0-x^|^2}{2\gamma K}.} \tag{10} ]
五、Douglas–Rachford:两个都不光滑怎么办?
对 (\min_x g(x)+h(x)),若两项都可求 Prox,却不便求梯度,可使用 Douglas–Rachford Splitting(DRS):
[
\boxed{
\begin{aligned}
u_k&=\operatorname{prox}{\gamma g}(z_k),
v_k&=\operatorname{prox}{\gamma h}(2u_k-z_k),
z_{k+1}&=z_k+v_k-u_k.
\end{aligned}}
\tag{11}
]
注意主变量是 (z_k),真正代表原问题解的通常是影子序列 (u_k),而不是 (z_k)。
5.1 为什么这不是两个 Prox 直接连用?
定义反射 (R_g=2\operatorname{prox}_{\gamma g}-I)、(R_h) 类似,则
[ \boxed{T_{\rm DR}=\frac12(I+R_hR_g).} \tag{12} ]
直接展开可验证 (z_{k+1}=T_{\rm DR}(z_k))。两次反射的复合非扩张,因此 (T_{\rm DR}) 是 (1/2)-averaged(事实上 firmly nonexpansive)。
5.2 固定点与原问题最优点
若 (z^=T_{\rm DR}(z^)),那么式 (11) 中 (v^=u^)。由两次 Prox 的最优性:
[ \frac{z^-u^}{\gamma}\in\partial g(u^),\qquad \frac{u^-z^}{\gamma}\in\partial h(u^). ]
两式相加:
[ \boxed{0\in\partial g(u^)+\partial h(u^).} ]
由凸性,(u^*) 是原问题最优点。
反过来,若存在第 1 节所要求的 (x^,a^,b^),取 (z^=x^+\gamma a^),即可构造 DRS 固定点。
由于 (T_{\rm DR}) averaged、固定点非空,第 3 节证明适用:
[ \boxed{z_k\to z^,\quad u_k=\operatorname{prox}_{\gamma g}(z_k)\to x^.} \tag{13} ]
这里不声称原目标函数在每次影子迭代后下降,也不直接给出没有额外假设的线性收敛率。
六、完整数值迭代:FB 与 DRS 求同一个问题
考虑
[ \boxed{\min_x\ F(x)=|x|+\tfrac12(x-3)^2.} ]
其最优点为 (x^=2),最优值为 (F^=2.5)。使用软阈值
[ S_\lambda(v)=\operatorname{sign}(v)\max(|v|-\lambda,0). ]
Forward–Backward:(\gamma=0.5,x_0=0)
| 将平滑项取为 (f(x)=\tfrac12(x-3)^2),非光滑项取为 (h(x)= | x | )。有 (L=1): |
[ x_{k+1}=S_{0.5}\big(x_k-0.5(x_k-3)\big). ]
第一步 (x_1=S_{0.5}(1.5)=1)。第二步 (x_2=S_{0.5}(2)=1.5)。
| 迭代 | FB 输出 (x_k) | (F(x_k)) |
|---|---|---|
| 0 | 0 | 4.5 |
| 1 | 1 | 3 |
| 2 | 1.5 | 2.625 |
| 最优 | 2 | 2.5 |
Douglas–Rachford:(\gamma=1,z_0=0)
| 设 (g(x)= | x | ),(h(x)=\frac12(x-3)^2)。则 |
[ \operatorname{prox}_g(w)=S_1(w),\quad \operatorname{prox}_h(w)=\frac{w+3}{2}. ]
代入式 (11):
| (k) | (z_k) | (u_k=S_1(z_k)) | (v_k=(2u_k-z_k+3)/2) | (z_{k+1}) |
|---|---|---|---|---|
| 0 | 0 | 0 | 1.5 | 1.5 |
| 1 | 1.5 | 0.5 | 1.25 | 2.25 |
| 2 | 2.25 | 1.25 | 1.625 | 2.625 |
DRS 的固定点是 (z^=3),对应影子 (u^=S_1(3)=2)。不要误把 z 的目标函数值当成真实解的进度。
七、失败反例与边界
反例一:两个 Prox 直接复合,通常不是和的 Prox。
沿用上例,(\gamma=1,v=0):
[ \operatorname{prox}_g(\operatorname{prox}_h(0)) =S_1(1.5)=0.5. ]
但将 (g+h) 作为整体:
[ \operatorname{prox}_{g+h}(0) =\arg\min_x {|x|+\tfrac12(x-3)^2+\tfrac12x^2}=1. ]
所以两个结果不相同。不能把算子分裂理解成“任意顺序拼接 Prox 就正确”。
反例二:DRS 无固定点时,不能宣称收敛。
取 (g=\delta_{{0}},h=\delta_{{1}})。两个集合都闭凸,但交集为空。于是:
[ u_k=0,\quad v_k=1,\quad z_{k+1}=z_k+1. ]
所以 (z_k=z_0+k) 发散。这里不存在共同可行点,更没有第 1 节所要求的最优性分解。
反例三:普通前向步不能直接用于任意单调 Lipschitz 算子。
令 (B=\begin{bmatrix}0&-1\1&0\end{bmatrix})。它单调(内积恒为 0)且 1-Lipschitz,但不具有正的 cocoercivity。迭代 (x_{k+1}=(I-\gamma B)x_k) 满足
[ |(I-\gamma B)x|^2=(1+\gamma^2)|x|^2, ]
任意 (\gamma>0) 都会放大非零向量。这说明 FB 的梯度 cocoercivity 假设至关重要;一般鞍点算子不能原样沿用凸 Smooth 梯度结论。
八、与 KKT 的联系:活跃约束仍可能是零乘子
若 (g=\delta_C),那么 (\partial g=N_C),resolvent 就是投影。对 (C={x:g_i(x)\le0}),在合适资格条件下:
[ 0\in\nabla f(x^)+N_C(x^) ]
可写成 KKT 的
[ \nabla f(x^)+\sum_i\lambda_i\nabla g_i(x^)=0,\quad \lambda_i\ge0,\quad \lambda_i g_i(x^*)=0. ]
例一:(\min_{x\le1}\tfrac12(x-3)^2)。最优 (x^=1),活跃约束乘子 (\lambda^=2)。
例二:(\min_{x\le0}\tfrac12x^2)。最优 (x^=0),约束仍活跃,但 (\lambda^=0)。
活跃不意味着乘子严格为正,而互补松弛并不是“活跃就必须正乘子”。
九、数学关系图
flowchart TD
A["0 ∈ ∂g + ∂h"] --> B["Resolvent = Prox"]
B --> C["Firmly nonexpansive"]
C --> D["Reflected Prox 非扩张"]
D --> E["DRS: (I + R_h R_g)/2"]
E --> F["固定点存在 ⇒ 影子解收敛"]
A --> G["若一项为凸 Smooth f"]
G --> H["∇f cocoercive"]
H --> I["Forward step + Prox"]
I --> J["0 < γ < 2/L: 迭代点收敛"]
I --> K["0 < γ ≤ 1/L: 函数值 O(1/K)"]
B --> L["指标函数 ⇒ 投影 / 法锥 / KKT"]
| 方法 | 需要计算 | 主要收敛假设 | 保证 |
|---|---|---|---|
| FB | (\nabla f)、(\operatorname{prox}_{\gamma h}) | 凸 (L)-Smooth (f),闭凸 (h),解存在,(0<\gamma<2/L) | 迭代点收敛;(\gamma\le1/L) 时函数值 (O(1/K)) |
| DRS | (\operatorname{prox}{\gamma g})、(\operatorname{prox}{\gamma h}) | 两项闭凸且存在次梯度最优性分解 | 主变量固定点收敛、影子点趋向最优解 |
| 任意拼接 Prox | 两次 Prox | 仅两项凸还不够 | 不能保证等于 (\operatorname{prox}_{\gamma(g+h)}) |
| 任意单调前向步 | (B(x)) | 仅单调与 Lipschitz 不够 | 可能发散 |
十、今日四级自测(总分 100)
首次课堂不附标准答案。含答案的独立 JSON 仅供提交后评分核验,作答前请勿查看。
Lv1|算子不动点与最优性|预计 2 分钟
设 (g,h) 为真、下半连续、凸函数,(\gamma>0)。关于近端算子、反射算子及最优性,下列哪项一定正确?
- A. (\operatorname{prox}{\gamma(g+h)}=\operatorname{prox}{\gamma g}\circ\operatorname{prox}_{\gamma h}) 对任意这样的 (g,h) 都成立。
- B. 若 (T=\operatorname{prox}_{\gamma g}),则 (T) 坚固非扩张,反射算子 (2T-I) 非扩张。
- C. 任意两个非扩张算子的直接复合必为收缩映射,且收缩常数严格小于 1。
- D. 只要 DRS 的两个 Prox 均可计算,就一定存在原问题最优解。
提示:利用 Prox 的次梯度单调性;区分非扩张(≤1)与严格收缩(<1)。
Lv2|Douglas–Rachford 两步计算|预计 4 分钟
| 考虑 (\min_x g(x)+h(x)),其中 (g(x)=2 | x | )、(h(x)=\tfrac12(x-6)^2)。采用 DRS,(\gamma=1,z_0=0),每轮按 (u_k=\operatorname{prox}{g}(z_k))、(v_k=\operatorname{prox}{h}(2u_k-z_k))、(z_{k+1}=z_k+v_k-u_k) 更新。求 (z_2),填写三位小数。 |
提示:先算软阈值 S₂,再利用 prox_h(w)=(w+6)/2;每一步同时更新 u、v、z。
Lv3|DRS 假设失效与反例|预计 5 分钟
给定 (g=\delta_{{0}})、(h=\delta_{{1}}),使用 (\gamma=1) 的 Douglas–Rachford 迭代 (u_k=\operatorname{prox}g(z_k))、(v_k=\operatorname{prox}_h(2u_k-z_k))、(z{k+1}=z_k+v_k-u_k),初值 (z_0=0)。以下哪一项正确?
- A. 因为两个指标函数都是真、下半连续、凸函数,所以 DRS 必须收敛到共同可行点。
- B. DRS 每一步都满足 z_{k+1}=z_k,因此 z_k 恒为 0。
- C. DRS 每一步满足 z_{k+1}=z_k+1,因此 z_k=k;由于原问题无共同可行点,固定点存在的收敛定理不适用。
- D. 只要两个投影都单值,原目标 g+h 就一定具有有限最优值。
提示:两个单点集合不相交;分别写出两个投影会返回什么。
Lv4|非扩张、两类分裂收敛与 KKT|预计 13 分钟
设所有变量属于有限维欧氏空间。完成四部分,明确写出所需假设。
A(10 分):设 (g) 真、下半连续、凸,(P=\operatorname{prox}_{\gamma g})。用次梯度单调性证明 (|Pu-Pv|^2\le\langle Pu-Pv,u-v\rangle),并证明 (R=2P-I) 非扩张。
B(12 分):设 (g,h) 均真、下半连续、凸,并存在 (x^,a^,b^),使 (a^\in\partial g(x^))、(b^\in\partial h(x^))、(a^+b^=0)。写出 DRS 的三步更新,证明其固定点 (z^) 的影子点 (u^=\operatorname{prox}_{\gamma g}(z^)) 满足 (0\in\partial g(u^)+\partial h(u^))。利用反射算子的非扩张性,解释有限维下 (z_k) 与影子序列收敛的理由。
C(12 分):设 (f) 凸且 (L)-Smooth,(h) 真、下半连续、凸,最优点存在。定义 (T_\gamma=\operatorname{prox}{\gamma h}\circ(I-\gamma\nabla f))。利用梯度 (1/L)-cocoercive 和 A,说明 (0<\gamma<2/L) 时 (T\gamma) 为 averaged 算子;对于 (0<\gamma\le1/L),从三点不等式推出最后一步函数值误差 (F(x_K)-F^\le|x_0-x^|^2/(2\gamma K))。
D(6 分):分别求 (\min_{x\le1}\tfrac12(x-3)^2) 与 (\min_{x\le0}\tfrac12x^2) 的最优点、活跃约束与非负 KKT 乘子,检查互补松弛,并解释为什么活跃约束的乘子可以为零。
提示:A 记 p=Pu、q=Pv 并相减;B 把 z-u 与 u-z 分别写成两项次梯度;C 利用 cocoercivity 控制 I-γ∇f 的 Lipschitz 常数,再用凸组合恒等式;D 统一写成 x-c≤0。
十一、下一讲与学习建议
第28课|2026-11-16:四周阶段测验 + 第四周复盘。 将覆盖凸集、分离、强凸/Smooth、KKT/对偶、GD/AGD、Prox/Moreau/投影及本课算子分裂,重点考查“假设 → 最优性条件 → 算法 → 收敛量”的完整论证链。该日按课号推进,不因自测成绩改号。
本课作答后逐题按 15/20/25/40 分评分;总分 ≥80 正常继续,60–79 追加算子不动点与影子序列例题,<60 先复习次梯度、法锥与 KKT,再做针对性训练。
延伸阅读: Ryu & Boyd, A Primer on Monotone Operator Methods(2016),https://stanford.edu/~boyd/papers/monotone_primer.html;Eckstein & Bertsekas, On the Douglas–Rachford Splitting Method and the Proximal Point Algorithm,https://www.mit.edu/~dimitrib/Eckstein_Bertsekas_D-R.pdf。