数学优化理论 · 第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。