第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。不改变日期课号。