Chambolle–Pock primal-dual hybrid gradient

Let $X={\mathbb{R}}^n$, $Y={\mathbb{R}}^m$, let $f:X\to (-\mathrm{\infty },+\mathrm{\infty }]$ and $g:Y\to (-\mathrm{\infty },+\mathrm{\infty }]$ be proper closed convex, and let $K:X\to Y$ be linear. Its unique adjoint $K^{\ast }:Y\to X$ exists by Every linear map between finite-dimensional inner product spaces has a unique adjoint, including zero-dimensional spaces. Identify $K$ with its matrix in the standard Euclidean bases when using the induced matrix norm below. The primal problem is ${\min }_{x}f(x)+g(Kx)$, with saddle function $\mathrm{\Phi }(x,y)=f(x)+⟨Kx,y⟩-g^{\ast }(y),$ where $g^{\ast }$ is defined by Fenchel conjugate of an extended-real function. The saddle function $\mathrm{\Phi }$ is evaluated on $\mathrm{dom}f\times \mathrm{dom}{g}^{\ast }$, where both function values are finite; no undefined extended-real subtraction is used outside this domain. Assume $\tau ,\sigma >0$ and $\tau \sigma \mathrm{\parallel }K{\mathrm{\parallel }}_2^2<1$, where $\mathrm{\parallel }K{\mathrm{\parallel }}_2$ is the induced Euclidean operator norm of The matrix norm induced by a published vector p-norm. Starting from $x^0,y^0$ and ${\bar{x}}^0=x^0$, the exact recurrence is $y^{k+1}={\mathrm{prox}}_{\sigma g^{\ast }}(y^k+\sigma K{\bar{x}}^k),x^{k+1}={\mathrm{prox}}_{\tau f}(x^k-\tau K^{\ast }{y}^{k+1}),{\bar{x}}^{k+1}=2x^{k+1}-x^k\mathrm{.}$ In positive-dimensional spaces the proximal maps are everywhere single-valued by Existence, resolvent characterization, and firm nonexpansiveness of the proximal map; in a zero-dimensional space its sole input and output are the zero vector, so that proximal call is single-valued directly. The proper closed convexity of $g^{\ast }$ follows from The Fenchel conjugate of a proper closed convex function is proper closed convex. These are mathematical existence statements, not finite evaluators.

The finite procedure also takes positive integer caps $C_y,C_x$ and supplied deterministic solver programs $S_y,S_x$ and Boolean certificate-checker programs $V_y,V_x$, with their complete instructions and data representations. Each program uses discrete steps that terminate. On input $(h,t,v)$, a solver may halt with failed or a candidate-certificate pair $(w,e)$. The supplied checker is admissible only if $V(h,t,v,w,e)=\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{e}$ implies that $h(w)$ is finite and $w$ minimizes $h(z)+\mathrm{\parallel }z-v{\mathrm{\parallel }}_2^2\mathrm{/}(2t)$ over all $z$ in its Euclidean space. This is a soundness condition on supplied programs; it does not promise that an arbitrary proximal map has an exact finite evaluator or that a certificate is always found. Proper closed convexity and the strict step-size condition remain admissibility assumptions on the mathematical data.

Initialize ${\bar{x}}^0=x^0$. At each sweep retain the old state $(x^k,y^k,{\bar{x}}^k)$. Return invalid-input for mismatched dimensions, nonpositive $\tau$ or $\sigma$, or caps that are not positive integers. First call $S_y$ on $(g^{\ast },\sigma ,y^k+\sigma K{\bar{x}}^k)$, then, if it returns $(w,e)$, call $V_y$ on those inputs and that pair. Allow at most $C_y$ program steps in total for the solver and checker. After each step inspect for termination: an explicit failure, malformed output, or false checker result returns prox-call-failed with call = dual; a true result stores $w$ as tentative $y^{k+1}$. Accept a true result on the last allowed step. If the budget is used without such a result or failure, return prox-cap-exhausted with call = dual. After dual success, apply the identical rule with $S_x,V_x,C_x$ to $(f,\tau ,x^k-\tau K^{\ast }{y}^{k+1})$, recording call = primal on failure or exhaustion. Every failure returns the unchanged old state. Only after both calls succeed, commit $x^{k+1},y^{k+1}$ and ${\bar{x}}^{k+1}=2x^{k+1}-x^k$, and return success with this state. A requested finite run repeats this sweep for an input nonnegative integer number of sweeps and stops at its first nonsuccess status. No convergence claim is made for a failed run.