Implicit nonsmooth block in alternating proximal-gradient iteration (source code)

= Implicit nonsmooth block in alternating proximal-gradient iteration

Let $h:\mathbb R^p\times\mathbb R^q\to\mathbb R$ be <convex> with an $L_h$-<Lipschitz gradient>, $L_h>0$, and let $\phi:\mathbb R^q\to\mathbb R\cup\{+\infty\}$ be a proper <lower semicontinuous> <convex function>. For $f(x,y)=h(x,y)+\phi(y)$, take
$$
y^+=\operatorname{prox}_{\tau(h(x,\cdot)+\phi)}(y),\qquad x^+=x-\tau\nabla_xh(x,y^+).
$$
The proper closed convex assumption on $\phi$ ensures that the implicit section has a well-defined <proximal operator>.

For two mixed points with difference $(p,q)$, write $(a,b)$ for the gradient difference of $h$ and $w$ for the difference of the selected <subgradients> of $\phi$. Inputs differ by $(p,q+\tau(b+w))$ and outputs by $(p-\tau a,q)$. <Monotonicity of a convex subdifferential> gives $\langle q,w\rangle\geq0$, while <cocoercivity> gives $\langle p,a\rangle+\langle q,b\rangle\geq L_h^{-1}(\|a\|^2+\|b\|^2)$. Expanding these squared norms proves
$$
\|Tz-Tw\|^2\leq\|z-w\|^2-\|(I-T)z-(I-T)w\|^2
$$
for $0<\tau L_h\leq1$. Thus the combined update is <firmly nonexpansive>. Its <fixed points> are the minimizers of $h+\phi$; if one exists, the <Browder convergence theorem for averaged operators> gives norm convergence in finite dimensions.