第33课|PDHG与Chambolle–Pock:从Fenchel共轭到鞍点算法
2026年11月21日|第5周第5天|讲授约18分钟,自测另计
上一课介绍了ADMM的乘子更新与原始/对偶残差。今天换一种方式处理耦合:不引入罚参数或交替解两个增广拉格朗日子问题,而在原始变量和对偶变量上分别执行一次Prox。 这就是Primal–Dual Hybrid Gradient(PDHG),经典形式也称Chambolle–Pock算法。
一、优化问题、假设与目标
考虑有限维欧氏空间中的复合凸问题:
[ \boxed{\min_{x\in\mathbb R^n} P(x)=f(x)+g(Kx)} \tag{1} ]
其中 (K:\mathbb R^n\to\mathbb R^m) 是线性映射;(f,g) 都是真、下半连续、凸函数;它们的相应Prox可精确计算;存在一个原始—对偶鞍点。除特别指出外,取固定步长 (\tau,\sigma>0) 和外推系数 (\theta=1)。
典型应用:(g(Kx)=\lambda|Kx|1) 可表示总变差(TV)稀疏正则,或 (g(Kx)=\delta_C(Kx)) 表示线性变换后的硬约束。如果 (K) 不是恒等映射,直接求 (\operatorname{prox}{g\circ K}) 常常困难,但 (\operatorname{prox}f)、(\operatorname{prox}{g^*})、(K)、(K^T) 可以很便宜。
二、Fenchel共轭:原问题怎样变成鞍点?
对任意真、下半连续、凸 (g),共轭定义为:
[ g^*(y)=\sup_t{\langle t,y\rangle-g(t)}. ]
由Fenchel–Moreau定理 (g=g^{**}):
[ \boxed{g(Kx)=\sup_y{\langle Kx,y\rangle-g^*(y)}.} \tag{2} ]
所以定义原始—对偶拉格朗日(鞍点)函数:
[ \boxed{\mathcal L(x,y)=f(x)+\langle Kx,y\rangle-g^*(y).} \tag{3} ]
原问题等价于 (\min_x\sup_y\mathcal L(x,y)) 的最优值表达。要交换min与max、证明无间隙或存在鞍点,还需要适当资格条件;本课直接假设鞍点存在,不把“凸”本身误当成强对偶保证。
鞍点 ((x^,y^)) 满足:
[ \mathcal L(x^,y)\le\mathcal L(x^,y^)\le\mathcal L(x,y^)\quad\forall x,y. ]
由于对 (x) 凸、对 (y) 凹,相应KKT(次梯度)条件为:
[
\boxed{\begin{cases}
0\in\partial f(x^)+K^Ty^,
0\in\partial g^(y^)-Kx^*.
\end{cases}}
\tag{4}
]
第二行等价于 (y^\in\partial g(Kx^))。它可以看成原始变量与对偶变量相互平衡的两个驻点条件。
| 例如 (g(t)=\lambda | t | ) 时: |
[ g^*(y)=\delta_{[-\lambda,\lambda]}(y). ]
| 证明:若 ( | y | \le\lambda),上确界 (\sup_t(yt-\lambda | t | )=0);否则沿对应符号令 ( | t | \to\infty),上确界为 (+\infty)。 |
因此 (\operatorname{prox}_{\sigma g^*}) 就是投影到区间 ([-\lambda,\lambda]),与 (\sigma) 无关。这是共轭函数把非光滑项变成简单对偶约束的具体例子。
三、PDHG三步更新:从两次近端最优性推导
选 (\tau,\sigma>0),设 (x^{-1}=x^0) 并令 (\bar x^0=x^0)。经典dual-first版本为:
[
\boxed{
\begin{aligned}
y^{k+1}
&=\operatorname{prox}{\sigma g^*}
(y^k+\sigma K\bar x^k),
x^{k+1}
&=\operatorname{prox}{\tau f}
(x^k-\tau K^Ty^{k+1}),
\bar x^{k+1}
&=x^{k+1}+\theta(x^{k+1}-x^k).
\end{aligned}}
\tag{5}
]
这节课固定 (\theta=1),即 (\bar x^k=2x^k-x^{k-1})。
对偶步对应最优性:
[ \boxed{ \frac{y^k-y^{k+1}}{\sigma}+K\bar x^k\in\partial g^*(y^{k+1}). } \tag{6} ]
原始步对应最优性:
[ \boxed{ \frac{x^k-x^{k+1}}{\tau}-K^Ty^{k+1}\in\partial f(x^{k+1}). } \tag{7} ]
不需要显式求 (\nabla g(Kx)),也不需要形成 (K^TK) 的逆矩阵。重要区别:ADMM通过增广拉格朗日和乘子校正处理等式耦合,PDHG通过 (K,K^T) 上的原始—对偶Prox直接处理鞍点耦合。二者有算子分裂联系,但迭代式不能直接互换。
四、经典步长条件为什么是 (\tau\sigma|K|^2<1)?
定义算子谱范数:
[ |K|=\sup_{v\ne0}\frac{|Kv|}{|v|}. ]
经典充分条件为:
[ \boxed{\tau\sigma|K|^2<1,\qquad\theta=1.} \tag{8} ]
从任意测试点 ((x,y)) 出发,把式(6)、(7)分别代入凸次梯度不等式,使用三点平方恒等式:
[ 2\langle a-b,b-c\rangle =|a-c|^2-|b-c|^2-|a-b|^2. ]
得到关键单步界(定义 (\Delta x^{k+1}=x^{k+1}-x^k)、(\Delta y^{k+1}=y^{k+1}-y^k)):
[
\begin{aligned}
&\mathcal L(x^{k+1},y)-\mathcal L(x,y^{k+1})
&\le \frac{|x-x^k|^2-|x-x^{k+1}|^2-|\Delta x^{k+1}|^2}{2\tau}
&\quad+\frac{|y-y^k|^2-|y-y^{k+1}|^2-|\Delta y^{k+1}|^2}{2\sigma}
&\quad+\langle K(\bar x^k-x^{k+1}),y^{k+1}-y\rangle.
\end{aligned}
\tag{9}
]
最麻烦的是最后的交叉项。由于 (\theta=1),有:
[ \bar x^k-x^{k+1}=\Delta x^k-\Delta x^{k+1}. ]
定义:
[ C_k=\langle K\Delta x^k,y^k-y\rangle,\qquad\Delta x^0=0. ]
那么:
[
\boxed{
\begin{aligned}
&\langle K(\bar x^k-x^{k+1}),y^{k+1}-y\rangle
&=C_k-C_{k+1}+\langle K\Delta x^k,\Delta y^{k+1}\rangle.
\end{aligned}}
\tag{10}
]
用Cauchy–Schwarz与Young不等式:
[
\begin{aligned}
\langle K\Delta x^k,\Delta y^{k+1}\rangle
&\le |K||\Delta x^k||\Delta y^{k+1}|
&\le\frac{|\Delta x^k|^2}{2\tau}
+\frac{\tau|K|^2}{2}|\Delta y^{k+1}|^2.
\end{aligned}
\tag{11}
]
于是对式(9)从 (k=0) 到 (N-1) 求和,距离平方、(C_k)及原始位移平方都望远镜抵消。剩余对偶位移项的系数是:
[ -\frac12\left(\frac1\sigma-\tau|K|^2\right). ]
当 (\tau\sigma|K|^2<1) 时,该系数为负。末端剩余二次型:
[ \frac{|\Delta x^N|^2}{2\tau} +\frac{|y^N-y|^2}{2\sigma} +\langle K\Delta x^N,y^N-y\rangle ]
由Young不等式与相同步长条件可证非负。因此:
[ \boxed{ \sum_{k=0}^{N-1} [\mathcal L(x^{k+1},y)-\mathcal L(x,y^{k+1})] \le \frac{|x-x^0|^2}{2\tau} +\frac{|y-y^0|^2}{2\sigma}. } \tag{12} ]
定义遍历平均:
[ X_N=\frac1N\sum_{k=1}^Nx^k,\quad Y_N=\frac1N\sum_{k=1}^Ny^k. ]
由 (\mathcal L) 在 (x) 上凸、在 (y) 上凹的Jensen不等式:
[ \boxed{ \mathcal L(X_N,y)-\mathcal L(x,Y_N) \le \frac{1}{N}\left( \frac{|x-x^0|^2}{2\tau} +\frac{|y-y^0|^2}{2\sigma} \right). } \tag{13} ]
这就是经典固定比较点的遍历鞍点间隙 (O(1/N))。若取任意鞍点 ((x^,y^)),左侧非负;更一般的全局gap上界还需要对比较点集合的有界性等条件。它并不声称最后一步原始目标误差总是 (O(1/N))。
在有限维、凸闭函数、鞍点存在、精确Prox及严格步长条件下,经典PDHG的原始/对偶迭代也收敛到某个鞍点。更宽松的步长结果确实存在,但需单独定理,不得将经典充分条件误当成所有版本的必要条件。
五、两次完整数值迭代:含L1复合项
考虑:
[ \boxed{\min_x \tfrac12(x-3)^2+|2x|.} ]
| 写成 (f(x)=\tfrac12(x-3)^2,\ g(t)= | t | ,\ K=2)。 |
[ g^(y)=\delta_{[-1,1]}(y),\qquad \operatorname{prox}_{\sigma g^}(v)=\Pi_{[-1,1]}(v). ]
对二次函数 (f):
[ \operatorname{prox}_{\tau f}(v)=\frac{v+3\tau}{1+\tau}. ]
取 (\tau=\sigma=0.4,\theta=1,x^0=y^0=0)。因为 (\tau\sigma|K|^2=0.64<1),满足经典条件。
第一轮:
[ y^1=\Pi_{[-1,1]}(0)=0,\quad x^1=\frac{1.2}{1.4}=\frac67\approx0.857143, \quad\bar x^1=2x^1=\frac{12}{7}. ]
第二轮:
[ y^2=\Pi_{[-1,1]}(0.4\cdot2\cdot12/7)=1, ]
[ x^2=\frac{x^1-0.4\cdot2y^2+1.2}{1.4} =\frac{44}{49}\approx0.897959. ]
对应迭代表:
| 轮次 | 对偶变量 (y^k) | 原始变量 (x^k) | 原目标 (P(x^k)) |
|---|---|---|---|
| 0 | 0 | 0 | 4.500000 |
| 1 | 0 | 0.857143 | 4.010204 |
| 2 | 1 | 0.897959 | 4.005206 |
| 最优 | 1 | 1 | 4.000000 |
最优点 (x^=1) 可由 (x-3+2=0)(正半轴)和对偶 (y^=1) 验证。两轮还没有达到最优,且这些示例目标值下降不代表一般PDHG每轮目标必单调。
六、失败反例:步长不满足充分条件时真的可能发散
取鞍点问题:
[ \min_x\max_y xy. ]
这仍是一个合法的凸—凹问题,鞍点为 ((0,0)):它对应 (f=0,g^*=0,K=1)(原始目标为 (\delta_{{0}}(x)))。
PDHG((\theta=1))简化为:
[ y^{k+1}=y^k+\sigma(2x^k-x^{k-1}), \quad x^{k+1}=x^k-\tau y^{k+1}. ]
选择 (\tau=\sigma=1.5),乘积 (2.25>1),初值 (x^0=1,y^0=0,x^{-1}=x^0):
[ y^1=1.5,\ x^1=-1.25; \qquad y^2=-3.75,\ x^2=4.375. ]
继续迭代的振幅会增大,出现发散。这说明不能去掉步长控制后仍承诺收敛。不过反例不代表所有超出保守界的特定问题都必发散。
七、KKT补强:对偶变量的符号取决于约束
若 (g(t)=\delta_{(-\infty,1]}(t)) 且 (K=1),则 (g^*(y)=y+\delta_{[0,\infty)}(y))。
这时鞍点表达:
[ \mathcal L(x,y)=f(x)+y(x-1),\quad y\ge0 ]
正好是约束 (x\le1) 的拉格朗日函数。
对于 (\min_{x\le1}\frac12(x-3)^2),最优点是 (x^=1),乘子 (y^=2)。但对于 (\min_{x\le1}\frac12(x-1)^2),最优点同样在活跃边界 (x=1),乘子却是 (y^*=0)。
两题都满足:
[ y\ge0,\quad x-1\le0,\quad y(x-1)=0. ]
所以活跃约束不必有严格正的乘子。一般Fenchel对偶变量可正可负;只有这里的单侧不等式共轭结构额外产生 (y\ge0)。
八、知识关系图
flowchart TD
A["复合目标 f(x)+g(Kx)"] --> B["Fenchel g = g**"]
B --> C["鞍点 L(x,y)=f(x)+〈Kx,y〉−g*(y)"]
C --> D["KKT: 原始与对偶两个包含式"]
C --> E["PDHG: dual Prox → primal Prox → 外推"]
E --> F["单步三点不等式"]
F --> G["Young + τσ‖K‖²<1"]
G --> H["遍历鞍点间隙 O(1/N)"]
B --> I["L1 共轭=区间指标"]
I --> J["对偶Prox=投影"]
D --> K["不等式约束:法锥、乘子、互补松弛"]
九、本课结论、条件与适用边界
| 结论 | 必要的主要前提 | 不能过度推断 |
|---|---|---|
| Fenchel鞍点表示 | (g) 真下半连续凸;鞍点性质另需存在性 | 不能把凸性直接等同于强对偶 |
| PDHG两次Prox | (f,g) 的相应Prox可解,(K,K^T)可算 | 不能说在每步原始可行或单调 |
| 遍历gap (O(1/N)) | 凸闭、鞍点存在、固定步长、(\theta=1)、(\tau\sigma|K|^2<1) | 不自动给最后一步目标误差率 |
| 步长稳定性 | 谱范数和原始/对偶步长协调 | 超出界不代表每个问题必发散 |
参考阅读: A. Chambolle & T. Pock, A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging, JMIV 40, 120–145 (2011). https://doi.org/10.1007/s10851-010-0251-1 ;作者预印本 https://optimization-online.org/2010/06/2646/ 。
十、四级自测(100分)
首次课堂不公布任何标准答案、正确选项或开放题评分要点。独立测验JSON内有答案,请在提交作答前勿打开。
Lv1|Fenchel 对偶与鞍点条件|15分|预计2分钟
设 f、g 为真、下半连续、凸函数,K 为线性映射,且 min_x f(x)+g(Kx) 存在原始—对偶鞍点。关于 L(x,y)=f(x)+〈Kx,y〉−g*(y),下列哪项在所述假设下必然正确?
A. g*(y) 总等于 −g(y),因此不需要计算凸共轭。
B. 鞍点 (x,y) 满足 −Kᵀy∈∂f(x) 与 Kx∈∂g(y*);反过来,这两条包含式也给出鞍点。
C. 只要 Kx=0,就能断言 (x,0) 是任意该问题的鞍点。
D. 所有对偶变量都必须非负,且满足不等式互补松弛。
提示:分别对 L 在 x 方向取极小、在 y 方向取极大;一般 Fenchel 对偶变量与非负不等式乘子并不相同。
Lv2|两轮 Chambolle–Pock 数值迭代|20分|预计4分钟
| 考虑 min_x 0.5(x−2)^2+ | x | ,写成 f(x)=0.5(x−2)^2、g(t)= | t | 、K=1。取 τ=σ=0.5、θ=1,初值 x^0=y^0=0、x^(−1)=x^0,使用 y^(k+1)=prox_{σg*}(y^k+σK(2x^k−x^(k−1)))、x^(k+1)=prox_{τf}(x^k−τKᵀy^(k+1))。求第二轮后的 x^2,保留三位小数。 |
请只填写数值,保留三位小数(绝对误差容限0.001)。
提示:g(y)=δ_−1,1,先把 y 更新写成区间投影,再用一元二次函数的 Prox;第一轮外推点就是 x^0。*
Lv3|步长条件失效的反例|25分|预计5分钟
用 θ=1 的 PDHG 求解 min_x max_y xy(等价于 f=0、g*=0、K=1,有鞍点 (0,0))。设 τ=σ=2,x^0=1、y^0=0、x^(−1)=x^0。更新 y^(k+1)=y^k+σ(2x^k−x^(k−1))、x^(k+1)=x^k−τy^(k+1)。下面哪项正确?
A. 因为有鞍点,任意 τσ>0 都保证收敛。
B. 前两次原始变量为 x¹=−3、x²=−3,所以已收敛。
C. 前两次原始变量为 x¹=−3、x²=21,迭代可发散;这里 τσ‖K‖²=4 不满足经典充分条件。
D. 本例 f 和 g* 非凸,故不能用作凸情形的反例。
提示:第一轮 y¹=2、x¹=−3;第二轮务必使用 2x¹−x⁰,而不是 x¹。
Lv4|Fenchel 对偶、原始—对偶间隙与 KKT|40分|预计15分钟
设 f、g 真、下半连续、凸,K 为有限维线性映射,且存在鞍点。A(10分):由 Fenchel 共轭推导 min_x max_y L(x,y)=f(x)+〈Kx,y〉−g(y),并写出鞍点 KKT 包含式。B(12分):对 θ=1 的 Chambolle–Pock 算法,从两次 Prox 最优性严格推导任意 x∈dom f、y∈dom g 的单步不等式:L(x^(k+1),y)−L(x,y^(k+1)) ≤ [‖x−x^k‖²−‖x−x^(k+1)‖²−‖Δx^(k+1)‖²]/(2τ)+[‖y−y^k‖²−‖y−y^(k+1)‖²−‖Δy^(k+1)‖²]/(2σ)+〈K(xbar^k−x^(k+1)),y^(k+1)−y〉。C(12分):令 Δx^k=x^k−x^(k−1)、xbar^k=2x^k−x^(k−1),用交叉项分解、Young 不等式及 τσ‖K‖²<1,证明遍历平均点 X_N、Y_N 满足 L(X_N,y)−L(x,Y_N) ≤ [‖x−x^0‖²/(2τ)+‖y−y^0‖²/(2σ)]/N;说明这是固定比较点的鞍点间隙界,不自动等于最后一步原始目标误差。D(6分):对 min_{x≤1} 0.5(x−3)^2 和 min_{x≤1} 0.5(x−1)^2 分别列出最优点、活跃约束、非负 KKT 乘子和互补松弛,解释活跃约束乘子为何可以为零。
请按 A—D 分部分完成推导,不要只写结论。
提示:A 用 g(t)=sup_y〈t,y〉−g(y);B 对每个 Prox 写次梯度不等式并使用三点平方恒等式;C 令 C_k=〈KΔx^k,y^k−y〉,把交叉项写成 C_k−C_(k+1)+〈KΔx^k,Δy^(k+1)〉后望远镜求和;D 约束写成 x−1≤0。*
十一、下一讲
第34课|2026年11月22日(第五周第六天):PDHG的停止准则、原始—对偶gap与ADMM比较。 将讨论如何从计算得到的gap、可行性和驻点残差判断停止,何时能给出最优性证书,及两类分裂方法的主要代价。第35课为第五周复盘。
评分规则: Lv1 15分、Lv2 20分、Lv3 25分、Lv4 40分;80分及以上正常继续,60–79分补充Fenchel/PDHG例题,低于60分复习Prox和KKT。不改变日期课号。