Alternating proximal-gradient operator (source code)

= Alternating proximal-gradient operator
{title2=$y-y^+=\tau\nabla_yf(x,y^+),\quad x-x^+=\tau\nabla_xf(x,y^+)$}

Let $f:\mathbb R^p\times\mathbb R^q\to\mathbb R$ be a differentiable <convex function> whose full <gradient> is $L$-<Lipschitz continuous>, with $L>0$. The alternating update first solves the implicit $y$ step and then the explicit $x$ step:
$$
y-y^+=\tau\nabla_yf(x,y^+),\qquad x-x^+=\tau\nabla_xf(x,y^+).
$$
The implicit step is the <proximal operator> of $\tau f(x,\cdot)$, so it exists uniquely. The gradient bound must control the full joint variable; smoothness alone supplies no global constant $L$.

For two updates, let $(p,q)$ be the difference of their mixed points $(x,y^+)$ and $(a,b)$ the corresponding full gradient difference. The input and output differences are $(p,q+\tau b)$ and $(p-\tau a,q)$. The <mixed-point norm identity for alternating updates> and <Baillon–Haddad theorem> give
$$
\|Tz-Tw\|^2\leq\|z-w\|^2-\left(\frac{2}{\tau L}-1\right)\|(I-T)z-(I-T)w\|^2.
$$
Hence $T$ is a $(\tau L/2)$-<averaged operator> for $0<\tau L<2$. Its <fixed points> have both block gradients zero and are exactly the <global minimizers> of $f$. If a minimizer exists, <Browder convergence theorem for averaged operators> gives norm convergence of iteration in the stated finite-dimensional setting.