原始—对偶混合梯度

复合惩罚 $g(Kx)$ 可能让一次完整近端求解很难，却可以分别容易地计算 $f$ 和 $g^*$ 的近端。PDHG把线性耦合留在矩阵乘法里，交替更新原变量和对偶变量。看似多出来的外推 $2x_{k+1}-x_k$ 使两次便宜操作拼成一个稳定的隐式平衡。

形式陈述

先原变量，再外推给对偶

设 $f:\mathbb R^n\to\mathbb R\cup\{+\infty\}$ 、 $g:\mathbb R^m\to\mathbb R\cup\{+\infty\}$ proper、下半连续且凸， $K:\mathbb R^n\to\mathbb R^m$ 线性。考虑

P(x)=f(x)+g(Kx),\qquad \mathcal L(x,y)=f(x)+\langle Kx,y\rangle-g^*(y).

假定存在Fenchel原对偶鞍点 $(x^*,y^*)$ ，即

-K^{\mathsf T}y^*\in\partial f(x^*),\qquad Kx^*\in\partial g^*(y^*).

固定 $\tau,\sigma>0$ ，并令 $\kappa\ge\|K\|_2$ 为一个有效的诱导范数上界，要求 $\tau\sigma\kappa^2<1$ 。本页采用原变量先更新的顺序，从任意 $x_0,y_0$ 执行两次精确近端：

x_{k+1}=\operatorname{prox}_{\tau f}(x_k-\tau K^{\mathsf T}y_k),

y_{k+1}=\operatorname{prox}_{\sigma g^*}\bigl(y_k+\sigma K(2x_{k+1}-x_k)\bigr).\tag{1}

这是Chambolle–Pock的原先更新版本；采用对偶先更新时，下标与外推位置须成套改变。本页固定式(1)，不混合两份伪代码。

定义 $z=(x,y)$ 及对称块矩阵

M=\begin{pmatrix}\tau^{-1}I&-K^{\mathsf T}\\-K&\sigma^{-1}I\end{pmatrix}.

上述严格步长使 $M\succ0$ 。有限维中， $z_k$ 收敛到某个鞍点。对平均输出 $\bar x_N=N^{-1}\sum_{k=1}^Nx_k$ 、 $\bar y_N=N^{-1}\sum_{k=1}^Ny_k$ ，任意 $u\in\operatorname{dom}f,v\in\operatorname{dom}g^*$ 满足

\mathcal L(\bar x_N,v)-\mathcal L(u,\bar y_N) \le\frac{\|z_0-(u,v)\|_M^2}{2N}.\tag{2}

其中 $\|z\|_M^2=z^{\mathsf T}Mz$ 。对有界比较集合取上确界可得受限鞍点间隙率；对无界比较集合，右边的统一半径可能无穷，不能据此声称全局gap有同一个有限常数。

直觉

外推正好消去一份耦合

两次近端的最优性条件为

\frac{x_k-x_{k+1}}\tau-K^{\mathsf T}y_k\in\partial f(x_{k+1}),

\frac{y_k-y_{k+1}}\sigma+K(2x_{k+1}-x_k)\in\partial g^*(y_{k+1}).

将它们写在同一个新点上，便得到

M(z_k-z_{k+1})\in\mathcal T(z_{k+1}),\qquad \mathcal T(x,y)=\binom{\partial f(x)+K^{\mathsf T}y}{\partial g^*(y)-Kx}.\tag{3}

$\mathcal T$ 是既有原对偶页建立的极大单调关系。式(3)是改变度量后的整个隐式步，却通过式(1)分成两次prox求出，无需显式形成或求逆块矩阵 $M$ 。

正定性也能直接看见。令 $c=\sqrt{\tau\sigma}\kappa<1$ ，对 $z=(a,b)$ 用范数配对界及 $2rs\le r^2+s^2$ ，有

\|z\|_M^2\ge(1-c)\left(\frac{\|a\|^2}{\tau}+\frac{\|b\|^2}{\sigma}\right)>0\quad(z\ne0).

因此这个块度量真正控制两份变量，而不是一个可能带负方向的形式二次式。

同一能量同时给稳定和间隙

取鞍点 $z^*$ 。由式(3)和单调性， $\langle z_{k+1}-z^*,M(z_k-z_{k+1})\rangle\ge0$ 。平方展开给

\|z_{k+1}-z^*\|_M^2+\|z_{k+1}-z_k\|_M^2 \le\|z_k-z^*\|_M^2.\tag{4}

这保证有界性与位移趋零。式(1)由连续prox与线性映射组成；在有限维取收敛子列，极限由位移趋零成为更新固定点，再由式(3)成为鞍点。到该点的M距离非增而沿子列趋零，所以整列收敛。

为证明式(2)，对任意比较点 $(u,v)$ 分别使用两条次梯度下界。其和给

\begin{aligned} \mathcal L(x_{k+1},v)-\mathcal L(u,y_{k+1}) &\le\langle M(z_k-z_{k+1}),z_{k+1}-(u,v)\rangle\\ &=\tfrac12\bigl(\|z_k-(u,v)\|_M^2-\|z_{k+1}-(u,v)\|_M^2 -\|z_k-z_{k+1}\|_M^2\bigr). \end{aligned}

逐轮求和并使用 $\mathcal L$ 对原变量凸、对对偶变量凹，便得平均输出的式(2)。初值可以不在函数有效域内，因为每个求和项从完成一次prox后的新点开始。

例子与边界

两变量融合惩罚的完整轨道

取

f(x)=\tfrac12\|(x_1,x_2)-(2,0)\|^2,\qquad Kx=x_1-x_2,\qquad g(t)=|t|.

$g^*=\delta_{[-1,1]}$ ，原问题最优解为 $x^*=(1,1)$ ，对偶最优点为 $y^*=1$ 。可直接核对 $x^*-(2,0)+K^{\mathsf T}y^*=0$ 、 $Kx^*=0\in\partial\delta_{[-1,1]}(1)$ 。原对偶目标为

P(x)=\tfrac12[(x_1-2)^2+x_2^2]+|x_1-x_2|, \qquad D(y)=2y-y^2\quad(|y|\le1),

两者在上述点都等于一。

取 $\tau=\sigma=1/2$ ；由于 $\|K\|_2^2=2$ ，步长乘积为 $1/2<1$ 。式(1)变成

x_{k+1}=\frac{2x_k-K^{\mathsf T}y_k+(2,0)}3,

y_{k+1}=\operatorname{clip}_{[-1,1]}\!\left(y_k+\tfrac12K(2x_{k+1}-x_k)\right).

从 $x_0=(0,0),y_0=0$ 开始：

$k$	$x_k$	$y_k$	完整可行原对偶gap $P(x_k)-D(y_k)$
0	$(0,0)$	$0$	$2$
1	$(2/3,0)$	$2/3$	$2/3$
2	$(8/9,2/9)$	$1$	$25/81$
3	$(25/27,13/27)$	$1$	$100/729$

第二轮后对偶截断始终返回一。归纳得到，对 $k\ge2$ ，

x_k=\left(1-\frac19(2/3)^{k-2},\ 1-\frac79(2/3)^{k-2}\right),\qquad y_k=1,

P(x_k)-D(y_k)=\frac{25}{81}(4/9)^{k-2}.

每一步都有有限原目标与可行对偶下界，因此这个完整gap直接上界原目标误差；它比一般平均受限gap结论更强，来自算例可计算的对偶结构及显式轨道。

步长和外推各有实际作用

考虑纯双线性鞍点 $\mathcal L(x,y)=xy$ ，即 $f=0,g^*=0,K=1$ 。若取 $\tau=2,\sigma=1$ ，步长乘积为二，式(1)的矩阵为

\binom{x^+}{y^+}=\begin{pmatrix}1&-2\\1&-3\end{pmatrix}\binom{x}{y}.

特征值为 $-1\pm\sqrt2$ ，其中一个模大于一；从 $(1,0)$ 产生 $(1,1),(-1,-2),(3,5)$ 并发散。违反安全条件确实可能失败，但这里没有宣称每个大于等于一的乘积都必然失败。

若在安全步长 $\tau=1,\sigma=1/2$ 下删去外推，改成 $y^+=y+\sigma x^+$ ，更新矩阵是 $\left(\begin{smallmatrix}1&-1\\1/2&1/2\end{smallmatrix}\right)$ ，行列式一，两个非实特征值都在单位圆上；非零轨道不趋零。外推不是可随意删除的显示效果。

推论与应用

有限受限gap与完整优化证书分开报告

若选有界比较集合 $U\subseteq\operatorname{dom}f,V\subseteq\operatorname{dom}g^*$ ，令 $R_M^2=\sup_{u\in U,v\in V}\|z_0-(u,v)\|_M^2$ ，式(2)给

\sup_{u\in U,v\in V}\{\mathcal L(\bar x_N,v)-\mathcal L(u,\bar y_N)\}\le R_M^2/(2N).

这个受限上确界不一定非负，也不自动上界全局原目标差。若需要标准非负的局部鞍点gap，可选包含当前平均点的比较集合；若需要完整 $P-D$ 证书，则必须在全域计算并检查原、对偶可行性。纯双线性例在非零候选处的全域gap就是无穷大，不能用有限盒的结果替换它。

每轮计算一次 $K^{\mathsf T}y_k$ 、一次 $K(2x_{k+1}-x_k)$ 和两次prox，另有 $O(n+m)$ 向量运算及状态存储。对稠密 $m\times n$ 矩阵乘法为 $O(mn)$ ，稀疏存储 $s$ 个条目时为 $O(s+n+m)$ ；prox成本另计。无须形成 $K^{\mathsf T}K$ ，这正是与某些精确联合子问题相比的计算优势。

已知较松的 $\kappa$ 仍能给合法但保守步长；低估范数可能毁掉M正定性。近似prox、非线性 $K$ 、自适应步长或加速参数需要各自证明。鞍点存在与每步prox存在也不能混淆：前者提供可收敛的证书，后者只保证程序能继续运行。

参考资料

Antonin Chambolle and Thomas Pock, A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging, Journal of Mathematical Imaging and Vision40,120–145,2011，原始近端原对偶算法与平均间隙分析。
Ernest K. Ryu and Stephen Boyd, A Primer on Monotone Operator Methods,2016，§8中Chambolle–Pock小节（印刷页32），正定块度量与原变量先更新形式。本文将两个步长、式(2)的比较点合同和融合例完整展开，采用严格正定条件而不讨论临界扩展。

形式陈述 ​

先原变量，再外推给对偶 ​

外推正好消去一份耦合 ​

同一能量同时给稳定和间隙 ​

两变量融合惩罚的完整轨道 ​

步长和外推各有实际作用 ​

有限受限gap与完整优化证书分开报告 ​

反向链接