The Chambolle-Pock Primal-Dual Hybrid Gradient Method

Intuition Beginner

Many problems pull in two directions at once. You want a picture that stays close to the noisy photo you measured, and you want it to be smooth, with sharp edges but no speckle. The two wishes fight: matching the photo exactly keeps the noise; over-smoothing erases the edges. A good answer is a truce between them.

A clean way to find that truce is to picture a tug-of-war. One player, the "primal" player, proposes a picture. The other player, the "dual" player, is a critic who probes where the picture is too rough and pushes back on exactly those spots. They take turns: the critic sharpens its complaints given the current picture, then the picture-maker adjusts to answer the latest complaints. Round by round, the picture and the complaints settle into balance.

The Chambolle-Pock method runs this tug-of-war with two friendly moves you already know. Each round the critic does one proximal step (its update is a simple, often closed-form, adjustment), and the picture-maker does one proximal step too. The only thing coupling them is a linear operator — for images, the operator that measures how much neighboring pixels differ. There is one extra trick: the picture-maker looks slightly ahead, using not just the latest picture but a small over-shoot of it, which steadies the back-and-forth and makes it converge.

What makes this method shine on images is that neither move needs solving a big system of equations. Each step is just a cheap formula plus multiplying by the difference operator. There is a single rule to keep it stable: the two step sizes, multiplied together and scaled by the operator's strength, must stay below one.

Visual Beginner

Picture one round as three moves: the critic (dual $y$) sharpens its complaints from the current picture, the picture-maker (primal $x$) answers, and then a small over-shoot of the new picture is passed forward to steady the next round.

   round n                      what each step does

   dual y-update  ------->   prox-ascent: sharpen the critic given
   (the critic)              the look-ahead picture (a clip / prox step)
        |
        v
   primal x-update  ----->   prox-descent: adjust the picture to
   (the picture-maker)       answer the new critic (a prox step)
        |
        v
   extrapolation  ------->   look slightly ahead:
   (over-shoot)             bar x = x_new + (x_new - x_old)
        |
        v
   repeat until x and y settle   (the truce holds)

   stability rule:  step_x  x  step_y  x  (operator strength)^2  <  1

the piece	its update does
critic $y$ (dual)	prox-ascent: a cheap step (often a clip) given the look-ahead picture
picture $x$ (primal)	prox-descent: a cheap step answering the latest critic
over-shoot $\bar{x}$	pass forward $x_{\text{new}}$ plus its change, to steady the rounds

Worked example Beginner

We run one round on a tiny two-pixel denoising problem. The noisy data is $b=(b_1,b_2)=(3,0)$. We want a picture $x=(x_1,x_2)$ that stays near $b$ but whose two pixels are not too different. The roughness is measured by the single difference $Kx=x_1-x_2$, so $K=(1,-1)$. The fit cost is $g(x)=\frac{1}{2}\Vert x-b{\Vert }^2$ and the roughness cost is the absolute value $\lambda |Kx|$ with $\lambda =1$. We use step sizes $\tau =\frac{1}{2}$, $\sigma =\frac{1}{2}$, and start at $x=(3,0)$, $\bar{x}=(3,0)$, critic $y=0$.

Step 1. The critic's update. The critic for an absolute value lives between $-\lambda$ and $\lambda$. Its update is: take $y+\sigma (K\bar{x})$, then clip into $[-1,1]$. Here $K\bar{x}=3-0=3$, so $y+\frac{1}{2}\cdot 3=1.5$, and clipping to $[-1,1]$ gives $y=1$.

Step 2. The picture's update. The picture answers by a fit-step. The fit prox for $g$ is $x\leftarrow (x-\tau K^{\top }y+\tau b)/(1+\tau )$. Here $K^{\top }y=(1,-1)\cdot 1=(1,-1)$, so $x-\tau K^{\top }y=(3,0)-\frac{1}{2}(1,-1)=(2.5,0.5)$. Add $\tau b=(1.5,0)$ and divide by $1+\tau =1.5$: $x=(4.0,0.5)/1.5=(2.667,0.333)$.

Step 3. The over-shoot. Pass forward $\bar{x}=x_{\text{new}}+(x_{\text{new}}-x_{\text{old}})=(2.667,0.333)+((2.667,0.333)-(3,0))=(2.333,0.667)$.

What this tells us. The gap between the two pixels started at $3-0=3$ and after one round the picture's gap is $2.667-0.333=2.333$ — the roughness is already shrinking, while each pixel stays near its data value. Every step was a clip or a one-line formula; no system of equations was solved.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $X={\mathbb{R}}^n$ and $Y={\mathbb{R}}^m$ are Euclidean spaces, $K:X\to Y$ is a bounded linear operator with adjoint $K^{\top }$ and operator norm $\Vert K\Vert =\max \{\Vert Kx\Vert :\Vert x\Vert \le 1\}$, and $g:X\to (-\infty ,+\infty ]$, $f:Y\to (-\infty ,+\infty ]$ are proper closed convex. The proximal operator ${\mathrm{prox}}_{th}(v)=\arg {\min }_w\{h(w)+\frac{1}{2t}\Vert w-v{\Vert }^2\}$ and its resolvent identity ${\mathrm{prox}}_{th}=(I+t\partial h{)}^{-1}$ are from 44.06.02; the Fenchel conjugate $f^{\ast }(y)={\sup }_z\{⟨z,y⟩-f(z)\}$ and Fenchel-Rockafellar duality are from 44.02.03.

Definition (the saddle-point model). Consider the composite primal problem

$$\underset{x\in X}{\min }f(Kx)+g(x).$$

Conjugating $f$ via $f(Kx)={\sup }_{y\in Y}\{⟨Kx,y⟩-f^{\ast }(y)\}$ of 44.02.03 turns it into the saddle-point (convex-concave) problem

$$\underset{x\in X}{\min }\underset{y\in Y}{\max }\Phi (x,y),\Phi (x,y)=⟨Kx,y⟩+g(x)-f^{\ast }(y),$$

convex in $x$ for fixed $y$ and concave in $y$ for fixed $x$. The variable $y$ is the dual variable dual to the constraint inside $f$.

Definition (the Chambolle-Pock / PDHG iteration). Fix step sizes $\tau ,\sigma >0$ and an extrapolation parameter $\theta \in [0,1]$. Starting from $(x^0,y^0)$ and ${\bar{x}}^0=x^0$, the primal-dual hybrid gradient (PDHG) / Chambolle-Pock iteration produces $(x^{n+1},y^{n+1},{\bar{x}}^{n+1})$ by

$$\begin{array}{rl}{y}^{n+1}& ={\mathrm{prox}}_{\sigma f^{\ast }}(y^n+\sigma K{\bar{x}}^n),\\ x^{n+1}& ={\mathrm{prox}}_{\tau g}(x^n-\tau K^{\top }{y}^{n+1}),\\ {\bar{x}}^{n+1}& =x^{n+1}+\theta (x^{n+1}-x^n).\end{array}$$

The first step is a proximal ascent in $y$ (an explicit step $+\sigma K{\bar{x}}^n$ followed by the prox of $f^{\ast }$); the second is a proximal descent in $x$ (an explicit step $-\tau K^{\top }{y}^{n+1}$ followed by the prox of $g$). The third is the over-relaxation / extrapolation step. The standard choice is $\theta =1$.

Definition (step-size condition). The convergence of the unaccelerated method ($\theta =1$) holds under

$$\tau \sigma \Vert K{\Vert }^2<1.$$

This is the only restriction relating the two step sizes; either may otherwise be chosen freely, balancing the conditioning of the primal and dual blocks.

Definition (partial primal-dual gap). For bounded sets $B_X\times B_Y\ni (x^{\star },y^{\star })$, the partial primal-dual gap is

$${\mathcal{G}}_{B_X\times B_Y}(x,y)=\underset{y^{\prime }\in B_Y}{\max }\Phi (x,y^{\prime })-\underset{x^{\prime }\in B_X}{\min }\Phi (x^{\prime },y),$$

nonnegative, vanishing iff $(x,y)$ is a saddle point inside $B_X\times B_Y$; it is the convergence criterion the rate theorem controls.

Counterexamples to common slips Intermediate+

• "Chambolle-Pock is ADMM." Both solve the saddle model of 44.02.03, but ADMM 44.06.04 minimizes an augmented Lagrangian blockwise, and its $x$-update $\arg {\min }_x\{f(x)+\frac{\rho }{2}\Vert Ax+Bz-c{\Vert }^2\}$ couples $f$ with the quadratic $\Vert A\cdot {\Vert }^2$ — when $A\ne I$ this is a generalized prox requiring a linear solve. Chambolle-Pock uses only ${\mathrm{prox}}_{\tau g}$, ${\mathrm{prox}}_{\sigma f^{\ast }}$, and matrix-vector products with $K,K^{\top }$: never a solve.

• "The extrapolation is optional cosmetics." Dropping it ($\theta =0$) gives the plain Arrow-Hurwicz primal-dual method, which is not guaranteed to converge for general convex $f,g$ under $\tau \sigma \Vert K{\Vert }^2<1$; it needs strong convexity or smaller steps. The $\theta =1$ over-relaxation is what delivers the $O(1/N)$ guarantee for the general convex case.

• "Smaller steps always converge, like a gradient method." The binding condition is the product $\tau \sigma \Vert K{\Vert }^2<1$, not each step individually. Shrinking only $\tau$ while $\sigma$ is large can still violate it; both must be controlled jointly through their product against $\Vert K{\Vert }^2$.

Key theorem with proof Intermediate+

The convergence of Chambolle-Pock is established not by descent on either variable alone but by a single estimate on the joint primal-dual iterate, telescoped and averaged: the ergodic gap decays as $O(1/N)$. The estimate uses only the firm nonexpansiveness of the two proximal maps and the bilinear coupling through $K$.

Theorem (ergodic $O(1/N)$ convergence of the primal-dual gap). Let $g,f^{\ast }$ be proper closed convex, $K$ linear, and let $(x^{\star },y^{\star })$ be a saddle point of $\Phi$. Run Chambolle-Pock with $\theta =1$ and $\tau \sigma \Vert K{\Vert }^2<1$. Then the ergodic averages $X_N=\frac{1}{N}{\sum }_{n=1}^N{x}^n$, $Y_N=\frac{1}{N}{\sum }_{n=1}^N{y}^n$ satisfy, for every bounded $B_X\times B_Y$ containing $(x^{\star },y^{\star })$,

$${\mathcal{G}}_{B_X\times B_Y}(X_N,Y_N)\le \frac{1}{N}\left(\frac{\Vert x^0-x{\Vert }^2}{2\tau }+\frac{\Vert y^0-y{\Vert }^2}{2\sigma }\right){|}_{\sup over(x,y)\in B_X\times B_Y}=O\left(\frac{1}{N}\right).$$

Proof. The prox-ascent step $y^{n+1}={\mathrm{prox}}_{\sigma f^{\ast }}(y^n+\sigma K{\bar{x}}^n)$ has, by the resolvent characterization of 44.06.02, the optimality $\frac{1}{\sigma }(y^n+\sigma K{\bar{x}}^n-y^{n+1})\in \partial f^{\ast }(y^{n+1})$, i.e. $K{\bar{x}}^n-\frac{1}{\sigma }(y^{n+1}-y^n)\in \partial f^{\ast }(y^{n+1})$. The subgradient inequality for the convex $f^{\ast }$ then gives, for every $y$,

$$f^{\ast }(y)\ge f^{\ast }(y^{n+1})+⟨K{\bar{x}}^n-\frac{1}{\sigma }(y^{n+1}-y^n),y-y^{n+1}⟩.$$

Symmetrically, $x^{n+1}={\mathrm{prox}}_{\tau g}(x^n-\tau K^{\top }{y}^{n+1})$ gives $-K^{\top }{y}^{n+1}-\frac{1}{\tau }(x^{n+1}-x^n)\in \partial g(x^{n+1})$, hence for every $x$,

$$g(x)\ge g(x^{n+1})+⟨-K^{\top }{y}^{n+1}-\frac{1}{\tau }(x^{n+1}-x^n),x-x^{n+1}⟩.$$

Add the two inequalities and regroup the bilinear terms into $\Phi$. Using the polarization identity $⟨a-b,c-b⟩=\frac{1}{2}(\Vert a-b{\Vert }^2+\Vert c-b{\Vert }^2-\Vert a-c{\Vert }^2)$ on the $\frac{1}{\tau }$- and $\frac{1}{\sigma }$-weighted inner products produces, after collecting,

$$\Phi (x^{n+1},y)-\Phi (x,y^{n+1})\le \frac{\Vert x-x^n{\Vert }^2}{2\tau }-\frac{\Vert x-x^{n+1}{\Vert }^2}{2\tau }+\frac{\Vert y-y^n{\Vert }^2}{2\sigma }-\frac{\Vert y-y^{n+1}{\Vert }^2}{2\sigma }-R_n,$$

where the residual coupling term $R_n$ collects the extrapolation contribution $⟨K({\bar{x}}^n-x^n),y-y^{n+1}⟩=⟨K(x^n-x^{n-1}),y-y^{n+1}⟩$ (using ${\bar{x}}^n=2x^n-x^{n-1}$) together with the squared-distance slack. The condition $\tau \sigma \Vert K{\Vert }^2<1$ is exactly what makes the accumulated $R_n$ terms, after a Cauchy-Schwarz / Young split $|⟨K\delta x,\delta y⟩|\le \frac{\Vert K\Vert }{2}(\frac{\sqrt{\tau \sigma }}{\sqrt{\tau \sigma }})(\cdots )$, telescope into a nonnegative quantity that can be dropped. Summing the displayed inequality over $n=0,\dots ,N-1$ telescopes the squared distances:

$$\sum _{n=1}^N[\Phi (x^n,y)-\Phi (x,y^n)]\le \frac{\Vert x-x^0{\Vert }^2}{2\tau }+\frac{\Vert y-y^0{\Vert }^2}{2\sigma }.$$

By convexity of $\Phi (\cdot ,y)$ and concavity of $\Phi (x,\cdot )$ (Jensen), $\Phi (X_N,y)-\Phi (x,Y_N)\le \frac{1}{N}{\sum }_n[\Phi (x^n,y)-\Phi (x,y^n)]$. Taking the supremum over $(x,y)\in B_X\times B_Y$ on both sides gives the stated $O(1/N)$ bound on the partial gap. $\square$

Bridge. The single telescoping estimate on the joint iterate is the foundational reason Chambolle-Pock converges, and the role of $\tau \sigma \Vert K{\Vert }^2<1$ — absorbing the bilinear coupling so the squared distances telescope cleanly — builds toward the accelerated $O(1/N^2)$ and linear rates of the Advanced results, where strong convexity supplies an extra negative term that sharpens the same estimate. This is exactly the saddle-point reading of 44.02.03 driven by the two proximal primitives of 44.06.02, and it is dual to the operator-splitting analysis of 44.06.04: where ADMM is Douglas-Rachford on the Fenchel dual, Chambolle-Pock is the proximal point algorithm on the primal-dual monotone operator in a preconditioned metric, so the method generalises forward-backward splitting to a coupled primal-dual pair without ever inverting $K$. Putting these together, the central insight is that the gap functional, not either variable's value, is the right convergence certificate, and the bridge is the resolvent ${\mathrm{prox}}_{\tau g}=(I+\tau \partial g{)}^{-1}$ of 44.06.02 — the same primitive that ADMM, forward-backward, and this method all share, here paired with ${\mathrm{prox}}_{\sigma f^{\ast }}$ across the operator $K$.

Exercises Intermediate+

Advanced results Master

The Chambolle-Pock iteration $y^{n+1}={\mathrm{prox}}_{\sigma f^{\ast }}(y^n+\sigma K{\bar{x}}^n)$, $x^{n+1}={\mathrm{prox}}_{\tau g}(x^n-\tau K^{\top }{y}^{n+1})$, ${\bar{x}}^{n+1}=x^{n+1}+\theta (x^{n+1}-x^n)$ admits a self-contained development: its placement as a preconditioned proximal point method, the base $O(1/N)$ rate, the two accelerated regimes, the no-linear-solve property that separates it from ADMM, and the Condat-Vu extension to a smooth term.

Theorem 1 (preconditioned proximal point reading). For $\theta =1$, Chambolle-Pock is the proximal point algorithm of Rockafellar applied to the maximal monotone primal-dual operator $T(x,y)=(\partial g(x)+K^{\top }y,\partial f^{\ast }(y)-Kx)$ in the metric of the symmetric positive-definite preconditioner M = \begin{psmallmatrix} I/\tau & -K^\top \\ -K & I/\sigma\end{psmallmatrix}, which is positive definite exactly when $\tau \sigma \Vert K{\Vert }^2<1$ ^{[He & Yuan 2012]}. The resulting $M$-resolvent is firmly nonexpansive in the $M$-norm, so the iterates form a Fejér-monotone sequence converging to a zero of $T$ — a saddle point of $\Phi$. This is the structural reason convergence holds for any fixed steps satisfying the product condition, paralleling the averaged-operator reading of ADMM in 44.06.04, but with the operator $K$ entering through the metric rather than through an augmented-Lagrangian quadratic.

Theorem 2 (base ergodic rate). For proper closed convex $g,f^{\ast }$ with a saddle point, $\theta =1$, and $\tau \sigma \Vert K{\Vert }^2<1$, the ergodic averages satisfy ${\mathcal{G}}_{B_X\times B_Y}(X_N,Y_N)\le \frac{1}{N}(\frac{\Vert x^0-x{\Vert }^2}{2\tau }+\frac{\Vert y^0-y{\Vert }^2}{2\sigma })$ over $(x,y)\in B_X\times B_Y$, the $O(1/N)$ partial-primal-dual-gap bound ^{[Chambolle & Pock 2011]}. The rate is on the ergodic average; the last iterate also converges (by Fejér monotonicity from Theorem 1) but without a uniform worst-case rate in the general nonsmooth case.

Theorem 3 (acceleration under partial strong convexity, $O(1/N^2)$). If $g$ is $\gamma$-strongly convex (equivalently $f$, hence $\nabla f^{\ast }$, is smooth on the dual side), the adaptive schedule

$${\theta }_n=\frac{1}{\sqrt{1+2\gamma {\tau }_n}},{\tau }_{n+1}={\theta }_n{\tau }_n,{\sigma }_{n+1}=\frac{{\sigma }_n}{{\theta }_n}$$

keeps ${\tau }_n{\sigma }_n\Vert K{\Vert }^2$ invariant and yields $\Vert x^N-x^{\star }{\Vert }^2=O(1/N^2)$, the optimal rate for this smoothness class ^{[Chambolle & Pock 2011]}. The mechanism is that strong convexity contributes a $\frac{\gamma }{2}\Vert \cdot {\Vert }^2$ term that lets $1/{\tau }_n$ grow linearly, so ${\tau }_n\sim 1/(\gamma n)$ and the primal distance, scaled by $1/{\tau }_N$, decays quadratically — the saddle-point analogue of Nesterov acceleration for the smooth class.

Theorem 4 (linear rate under bilateral strong convexity). If both $g$ and $f^{\ast }$ are strongly convex (with moduli ${\gamma }_g,{\gamma }_{f^{\ast }}$ — equivalently $g$ strongly convex and $f$ smooth, and $f$ strongly convex and $g$ smooth, so both primal and dual problems are smooth strongly convex), fixed accelerated steps $\tau ,\sigma$ give linear convergence $\Vert x^N-x^{\star }{\Vert }^2+\Vert y^N-y^{\star }{\Vert }^2=O({\omega }^N)$ for some $\omega \in (0,1)$ determined by ${\gamma }_g,{\gamma }_{f^{\ast }},\Vert K\Vert$ ^{[Chambolle & Pock 2011]}. The contraction factor improves as the problem's two-sided conditioning improves, and the optimal fixed steps balance the primal and dual moduli against $\Vert K\Vert$ — the primal-dual counterpart of the linear rate of gradient descent on smooth strongly convex objectives.

Theorem 5 (no linear solve; Condat-Vu extension). Each Chambolle-Pock step evaluates ${\mathrm{prox}}_{\tau g}$, ${\mathrm{prox}}_{\sigma f^{\ast }}$, and the actions of $K,K^{\top }$ — never the inverse of $K$, $K^{\top }K$, or any quadratically-coupled prox; this is the decisive contrast with ADMM 44.06.04, whose $x$-update $\arg {\min }_x\{g(x)+\frac{\rho }{2}\Vert Kx-z+u{\Vert }^2\}$ is a generalized prox in the $K^{\top }K$-metric requiring a linear solve (or a linearizing inner approximation) when $K^{\top }K$ is not diagonal, exactly the case for the difference operator $K=\nabla$ of imaging ^{[Chambolle & Pock 2011]}. The Condat-Vu generalization handles a third, smooth term: for ${\min }_{x}f(x_{\mathrm{sm}})+g(x)+h(Kx)$ with $\nabla f_{\mathrm{sm}}$ $\beta$-Lipschitz, the iteration adds a forward gradient step $x^{n+1}={\mathrm{prox}}_{\tau g}(x^n-\tau \nabla f_{\mathrm{sm}}(x^n)-\tau K^{\top }{y}^n)$, $y^{n+1}={\mathrm{prox}}_{\sigma h^{\ast }}(y^n+\sigma K(2x^{n+1}-x^n))$, convergent under $\tau (\frac{\beta }{2}+\sigma \Vert K{\Vert }^2)\le 1$ and recovering Chambolle-Pock when $f_{\mathrm{sm}}=0$ ^{[Condat 2013]}.

Synthesis. Chambolle-Pock is the proximal point algorithm on the primal-dual monotone operator $T$ in the preconditioned $M$-metric, and this single identification is the foundational reason the method coheres: the alternating prox-ascent and prox-descent are the two block rows of one $M$-resolvent, the extrapolation ${\bar{x}}^n=2x^n-x^{n-1}$ is the off-diagonal coupling $-K,-K^{\top }$ in $M$, and the step condition $\tau \sigma \Vert K{\Vert }^2<1$ is exactly the positive-definiteness of $M$ that makes the resolvent firmly nonexpansive. This is exactly the saddle-point form of 44.02.03 solved by the two proximal primitives of 44.06.02, and it is dual to the Douglas-Rachford reading of ADMM in 44.06.04: where ADMM splits the Fenchel dual through reflected resolvents and pays a linear solve when $K$ is a genuine coupling operator, Chambolle-Pock keeps $K$ in the metric and never inverts it, which is the central insight that makes it the method of choice for total-variation and imaging problems where $K$ is a difference operator with no usable factorization.

The base estimate generalises to the accelerated regimes by a uniform mechanism — strong convexity adds a damping term, $g$-strong-convexity alone buys $O(1/N^2)$ through the adaptive $({\tau }_n,{\sigma }_n,{\theta }_n)$ schedule, and bilateral strong convexity buys a linear rate — so one gap-descent argument, sharpened by curvature, covers $O(1/N)$, $O(1/N^2)$, and linear convergence at once. Putting these together, the Condat-Vu extension folds a smooth term in by a forward gradient step, placing Chambolle-Pock inside the same three-operator splitting family as forward-backward 44.06.02 and ADMM 44.06.04, all of which are resolvent iterations on $0\in \mathcal{A}+\mathcal{B}$ read through different reformulations of one saddle model.

Full proof set Master

Proposition 1 (prox optimality as a subgradient inclusion). The Chambolle-Pock dual and primal updates satisfy $K{\bar{x}}^n-\frac{1}{\sigma }(y^{n+1}-y^n)\in \partial f^{\ast }(y^{n+1})$ and $-K^{\top }{y}^{n+1}-\frac{1}{\tau }(x^{n+1}-x^n)\in \partial g(x^{n+1})$.

Proof. The update $y^{n+1}={\mathrm{prox}}_{\sigma f^{\ast }}(\tilde{y})$ with $\tilde{y}=y^n+\sigma K{\bar{x}}^n$ is, by definition, the minimizer of $f^{\ast }(y)+\frac{1}{2\sigma }\Vert y-\tilde{y}{\Vert }^2$. Fermat's rule 44.06.02 gives $0\in \partial f^{\ast }(y^{n+1})+\frac{1}{\sigma }(y^{n+1}-\tilde{y})$, i.e. $\frac{1}{\sigma }(\tilde{y}-y^{n+1})\in \partial f^{\ast }(y^{n+1})$. Substituting $\tilde{y}=y^n+\sigma K{\bar{x}}^n$ gives $K{\bar{x}}^n-\frac{1}{\sigma }(y^{n+1}-y^n)\in \partial f^{\ast }(y^{n+1})$. The primal update $x^{n+1}={\mathrm{prox}}_{\tau g}(x^n-\tau K^{\top }{y}^{n+1})$ is handled identically: $0\in \partial g(x^{n+1})+\frac{1}{\tau }(x^{n+1}-(x^n-\tau K^{\top }{y}^{n+1}))$, i.e. $-K^{\top }{y}^{n+1}-\frac{1}{\tau }(x^{n+1}-x^n)\in \partial g(x^{n+1})$. $\square$

Proposition 2 (one-step primal-dual estimate). For every $(x,y)$,

$$\Phi (x^{n+1},y)-\Phi (x,y^{n+1})\le \frac{\Vert x-x^n{\Vert }^2-\Vert x-x^{n+1}{\Vert }^2}{2\tau }+\frac{\Vert y-y^n{\Vert }^2-\Vert y-y^{n+1}{\Vert }^2}{2\sigma }-⟨K(x^{n+1}-{\bar{x}}^n),y^{n+1}-y⟩-\frac{\Vert x^{n+1}-x^n{\Vert }^2}{2\tau }-\frac{\Vert y^{n+1}-y^n{\Vert }^2}{2\sigma }.$$

Proof. The convex subgradient inequality for $f^{\ast }$ at $y^{n+1}$ with the inclusion of Proposition 1 gives $f^{\ast }(y)\ge f^{\ast }(y^{n+1})+⟨K{\bar{x}}^n-\frac{1}{\sigma }(y^{n+1}-y^n),y-y^{n+1}⟩$; for $g$ at $x^{n+1}$, $g(x)\ge g(x^{n+1})+⟨-K^{\top }{y}^{n+1}-\frac{1}{\tau }(x^{n+1}-x^n),x-x^{n+1}⟩$. Recall $\Phi (x^{n+1},y)-\Phi (x,y^{n+1})=[g(x^{n+1})-g(x)]+[f^{\ast }(y^{n+1})-f^{\ast }(y)]+⟨K{x}^{n+1},y⟩-⟨Kx,y^{n+1}⟩$. Insert the two inequalities (as upper bounds on $g(x^{n+1})-g(x)$ and $f^{\ast }(y^{n+1})-f^{\ast }(y)$), giving

$$\Phi (x^{n+1},y)-\Phi (x,y^{n+1})\le \frac{1}{\tau }⟨x^{n+1}-x^n,x-x^{n+1}⟩+\frac{1}{\sigma }⟨y^{n+1}-y^n,y-y^{n+1}⟩+⟨K(x^{n+1}-{\bar{x}}^n),y^{n+1}-y⟩\cdot (-1)+B,$$

where $B$ collects the bilinear terms $⟨K{x}^{n+1},y-y^{n+1}⟩-⟨K(x^{n+1}-x),y^{n+1}⟩+⟨K{\bar{x}}^n,y-y^{n+1}⟩$ that combine to $-⟨K(x^{n+1}-{\bar{x}}^n),y^{n+1}-y⟩$. Apply the polarization identity $⟨a-b,c-a⟩=\frac{1}{2}(\Vert c-b{\Vert }^2-\Vert c-a{\Vert }^2-\Vert a-b{\Vert }^2)$ to each inner product $\frac{1}{\tau }⟨x^{n+1}-x^n,x-x^{n+1}⟩=\frac{1}{2\tau }(\Vert x-x^n{\Vert }^2-\Vert x-x^{n+1}{\Vert }^2-\Vert x^{n+1}-x^n{\Vert }^2)$ and likewise for the $\sigma$-term. Collecting yields the stated inequality. $\square$

Proposition 3 (the extrapolation makes the coupling telescope). With $\theta =1$, ${\bar{x}}^n=2x^n-x^{n-1}$, so $x^{n+1}-{\bar{x}}^n=(x^{n+1}-x^n)-(x^n-x^{n-1})$, and the coupling term telescopes: summing $-⟨K(x^{n+1}-{\bar{x}}^n),y^{n+1}-y⟩$ over $n$ leaves only boundary terms plus a quantity controlled by $\tau \sigma \Vert K{\Vert }^2<1$.

Proof. With ${\bar{x}}^n=x^n+(x^n-x^{n-1})=2x^n-x^{n-1}$, write $\delta x^n=x^n-x^{n-1}$, so $x^{n+1}-{\bar{x}}^n=\delta x^{n+1}-\delta x^n$. Then $-⟨K(\delta x^{n+1}-\delta x^n),y^{n+1}-y⟩=-⟨K\delta x^{n+1},y^{n+1}-y⟩+⟨K\delta x^n,y^{n+1}-y⟩$. Abel summation regroups ${\sum }_n[⟨K\delta x^n,y^{n+1}-y⟩-⟨K\delta x^{n+1},y^{n+1}-y⟩]$ into ${\sum }_n⟨K\delta x^n,y^{n+1}-y^n⟩$ plus boundary terms $⟨K\delta x^1,y^1-y⟩-⟨K\delta x^{N+1},y^{N+1}-y⟩$. Each interior term is bounded by Young's inequality, $|⟨K\delta x^n,y^{n+1}-y^n⟩|\le \frac{\Vert K\Vert \alpha }{2}\Vert \delta x^n{\Vert }^2+\frac{\Vert K\Vert }{2\alpha }\Vert y^{n+1}-y^n{\Vert }^2$; choosing $\alpha =\sqrt{\tau /\sigma }$ makes these absorbable into the $-\frac{1}{2\tau }\Vert x^{n+1}-x^n{\Vert }^2-\frac{1}{2\sigma }\Vert y^{n+1}-y^n{\Vert }^2$ slack of Proposition 2 precisely when $\Vert K\Vert \sqrt{\tau \sigma }<1$, i.e. $\tau \sigma \Vert K{\Vert }^2<1$. The leftover is nonnegative and is dropped. $\square$

Proposition 4 (ergodic gap bound). Under $\theta =1$, $\tau \sigma \Vert K{\Vert }^2<1$, summing Propositions 2-3 over $n=0,\dots ,N-1$ and averaging gives $\Phi (X_N,y)-\Phi (x,Y_N)\le \frac{1}{N}(\frac{\Vert x-x^0{\Vert }^2}{2\tau }+\frac{\Vert y-y^0{\Vert }^2}{2\sigma })$ for all $(x,y)$.

Proof. Sum the inequality of Proposition 2 over $n=0,\dots ,N-1$. The squared-distance differences telescope to $\frac{\Vert x-x^0{\Vert }^2-\Vert x-x^N{\Vert }^2}{2\tau }+\frac{\Vert y-y^0{\Vert }^2-\Vert y-y^N{\Vert }^2}{2\sigma }$; drop the nonpositive $-\Vert x-x^N{\Vert }^2,-\Vert y-y^N{\Vert }^2$. The coupling sum is handled by Proposition 3, contributing only the absorbed nonnegative quantity (dropped) and boundary terms that vanish since $\delta x^0=0$ and the final term is again absorbed. Hence ${\sum }_{n=1}^N[\Phi (x^n,y)-\Phi (x,y^n)]\le \frac{\Vert x-x^0{\Vert }^2}{2\tau }+\frac{\Vert y-y^0{\Vert }^2}{2\sigma }$. By convexity of $\Phi (\cdot ,y)$ and concavity of $\Phi (x,\cdot )$, Jensen gives $\Phi (X_N,y)-\Phi (x,Y_N)\le \frac{1}{N}{\sum }_{n=1}^N[\Phi (x^n,y)-\Phi (x,y^n)]$, and division by $N$ yields the claim. $\square$

Proposition 5 (the partial gap is the right certificate). Taking the supremum of Proposition 4 over $(x,y)\in B_X\times B_Y$ with $(x^{\star },y^{\star })\in B_X\times B_Y$ gives ${\mathcal{G}}_{B_X\times B_Y}(X_N,Y_N)=O(1/N)$, and $\mathcal{G}=0$ iff $(X_N,Y_N)$ is a saddle point of $\Phi$ on $B_X\times B_Y$.

Proof. The left side of Proposition 4 is $\Phi (X_N,y)-\Phi (x,Y_N)$; its supremum over $(x,y)\in B_X\times B_Y$ is exactly ${\max }_{y\in B_Y}\Phi (X_N,y)-{\min }_{x\in B_X}\Phi (x,Y_N)={\mathcal{G}}_{B_X\times B_Y}(X_N,Y_N)$ by the definition of the partial gap. The right side's supremum is $\frac{1}{N}{\sup }_{(x,y)}(\frac{\Vert x-x^0{\Vert }^2}{2\tau }+\frac{\Vert y-y^0{\Vert }^2}{2\sigma })$, finite since $B_X\times B_Y$ is bounded, so $\mathcal{G}=O(1/N)$. The gap is a difference of a max and a min of the same function, hence $\ge 0$; it is $0$ iff $\Phi (X_N,y)\le \Phi (X_N,Y_N)\le \Phi (x,Y_N)$ for all admissible $(x,y)$, the saddle-point inequalities. $\square$

Proposition 6 ($M$-positive-definiteness equals the step condition). The block matrix M = \begin{psmallmatrix} I/\tau & -K^\top \\ -K & I/\sigma\end{psmallmatrix} is positive definite iff $\tau \sigma \Vert K{\Vert }^2<1$.

Proof. $M\succ 0$ iff the leading block $I/\tau \succ 0$ (always, $\tau >0$) and the Schur complement $I/\sigma -K(I/\tau {)}^{-1}{K}^{\top }=I/\sigma -\tau K{K}^{\top }\succ 0$. The latter holds iff $\tau {\lambda }_{\max }(K{K}^{\top })<1/\sigma$, i.e. $\tau \sigma \Vert K{\Vert }^2<1$ since ${\lambda }_{\max }(K{K}^{\top })=\Vert K{\Vert }^2$. Positive-definiteness of $M$ makes $⟨\cdot ,\cdot {⟩}_M$ an inner product, in which the proximal point step of Theorem 1 (Advanced results) is firmly nonexpansive, giving Fejér monotonicity of the iterates toward $\mathrm{zer}T$. $\square$

Connections Master

• Chambolle-Pock solves the Fenchel saddle model of 44.02.03: the primal ${\min }_{x}f(Kx)+g(x)$ becomes ${\min }_x{\max }_y\{⟨Kx,y⟩+g(x)-f^{\ast }(y)\}$ by conjugating $f$, and the dual variable $y$ ranges over $\mathrm{dom}{f}^{\ast }$. The conjugate calculus of that unit — that $f^{\ast }$ of a norm is a dual-ball indicator, that the prox of an indicator is a projection — is exactly what makes the dual prox-ascent step a closed-form clip in the imaging applications.

• The two updates are the proximal operators of 44.06.02: ${\mathrm{prox}}_{\tau g}=(I+\tau \partial g{)}^{-1}$ and ${\mathrm{prox}}_{\sigma f^{\ast }}=(I+\sigma \partial f^{\ast }{)}^{-1}$, and the firm nonexpansiveness of the resolvent proved there is what makes the preconditioned proximal point operator of this unit contractive in the $M$-metric. Forward-backward of that unit is the single-operator special case; Chambolle-Pock is its primal-dual extension across the coupling operator $K$.

• Chambolle-Pock is the no-linear-solve companion of ADMM and Douglas-Rachford 44.06.04: both attack the saddle model of 44.02.03 with proximal primitives, but ADMM is Douglas-Rachford on the Fenchel dual whose subproblems can carry a $K^{\top }K$-coupled quadratic (a linear solve when $K=\nabla$), while Chambolle-Pock keeps $K$ in the metric $M$ and uses only $K,K^{\top }$ actions — the distinction that decides which method suits total-variation imaging.

• Chambolle-Pock is the saddle-point solver that consumes the structured min-max model whose smoothing was studied in 44.06.08: Nesterov smoothing of $f(Kx)={\max }_y\{⟨Kx,y⟩-f^{\ast }(y)\}$ regularizes the inner $y$ and runs an accelerated method on the smoothed primal, while Chambolle-Pock attacks the same saddle function directly without smoothing, trading the $O(1/\epsilon )$ smoothed-primal rate for an $O(1/N)$ gap rate that needs no smoothing parameter, and matching the $O(1/N^2)$ accelerated rate when a block is strongly convex.

Historical & philosophical context Master

The primal-dual hybrid gradient method has roots in the Arrow-Hurwicz scheme of 1958 for finding saddle points of a Lagrangian by alternating gradient ascent in the dual and gradient descent in the primal, developed in the study of constrained optimization and economic equilibrium ^{[Arrow, Hurwicz & Uzawa 1958]}. The modern proximal form for imaging was introduced by Antonin Chambolle and Thomas Pock in 2011 in A first-order primal-dual algorithm for convex problems with applications to imaging (Journal of Mathematical Imaging and Vision 40(1), 120-145), which gave the over-relaxed iteration, the step condition $\tau \sigma \Vert K{\Vert }^2<1$, the $O(1/N)$ ergodic-gap theorem, and the accelerated $O(1/N^2)$ and linear variants under strong convexity, together with the total-variation denoising and deconvolution applications that made the method standard in computational imaging ^{[Chambolle & Pock 2011]}. The closely related primal-dual splitting that adds a smooth Lipschitz-gradient term was given independently by Laurent Condat in 2013 and by Bằng Công Vũ in the same period, yielding the three-operator scheme now called the Condat-Vu method ^{[Condat 2013]}. The proximal-point and variational-inequality interpretation, which placed the method inside maximal-monotone-operator theory and explained its convergence as Fejér monotonicity in a preconditioned metric, was developed by Bingsheng He and Xiaoming Yuan in 2012 ^{[He & Yuan 2012]}. The earlier PDHG iteration without the convergence-securing extrapolation was studied by Mingqiang Zhu and Tony Chan in 2008.

Bibliography Master

@article{chambollepock2011,
  author  = {Chambolle, Antonin and Pock, Thomas},
  title   = {A first-order primal-dual algorithm for convex problems with applications to imaging},
  journal = {Journal of Mathematical Imaging and Vision},
  volume  = {40},
  number  = {1},
  pages   = {120--145},
  year    = {2011}
}

@book{beck2017fom,
  author    = {Beck, Amir},
  title     = {First-Order Methods in Optimization},
  series    = {MOS-SIAM Series on Optimization},
  number    = {25},
  publisher = {SIAM},
  year      = {2017}
}

@article{condat2013,
  author  = {Condat, Laurent},
  title   = {A primal-dual splitting method for convex optimization involving {Lipschitzian}, proximable and linear composite terms},
  journal = {Journal of Optimization Theory and Applications},
  volume  = {158},
  number  = {2},
  pages   = {460--479},
  year    = {2013}
}

@article{vu2013,
  author  = {V\~{u}, B\`{a}ng C\^{o}ng},
  title   = {A splitting algorithm for dual monotone inclusions involving cocoercive operators},
  journal = {Advances in Computational Mathematics},
  volume  = {38},
  number  = {3},
  pages   = {667--681},
  year    = {2013}
}

@article{heyuan2012,
  author  = {He, Bingsheng and Yuan, Xiaoming},
  title   = {Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective},
  journal = {SIAM Journal on Imaging Sciences},
  volume  = {5},
  number  = {1},
  pages   = {119--149},
  year    = {2012}
}

@book{arrowhurwiczuzawa1958,
  author    = {Arrow, Kenneth J. and Hurwicz, Leonid and Uzawa, Hirofumi},
  title     = {Studies in Linear and Non-Linear Programming},
  publisher = {Stanford University Press},
  year      = {1958}
}

@article{zhuchan2008,
  author  = {Zhu, Mingqiang and Chan, Tony F.},
  title   = {An efficient primal-dual hybrid gradient algorithm for total variation image restoration},
  journal = {UCLA CAM Report 08-34},
  year    = {2008}
}