Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 325 / 2

For $0<\alpha <1$, an averaged operator has the formfor some nonexpansive mapping $R$, meaning $\Vert Rz-Rw{\Vert }_2\le \Vert z-w{\Vert }_2$ for all $z,w$. The word averaging refers to a convex combination with the identity. It does not mean averaging function values over a neighborhood.

An equivalent and useful averaged-operator inequality isTo see it, put $d=z-w$ and $r=Rz-Rw$ and expandUse $\Vert r{\Vert }_2\le \Vert d{\Vert }_2$ and $(I-T)z-(I-T)w=\alpha (d-r)$. Conversely, substituting $R=[T-(1-\alpha )I]/\alpha$ into the same expansion proves its nonexpansiveness from the displayed inequality. The strict range $0<\alpha <1$ matters for convergence of unrelaxed iterations: a general nonexpansive mapping such as $T=-I$ can have nonconvergent alternating iterates.

A firmly nonexpansive mapping satisfiesWriting $d=z-w$ and $a=Tz-Tw$, this is equivalent toIt is also equivalent to $\Vert 2a-d{\Vert }_2\le \Vert d{\Vert }_2$, so $R=2T-I$ is a nonexpansive mapping. Consequently firm nonexpansiveness is exactly $1/2$-averagedness. A proximal map of a proper lower semicontinuous convex function is a basic example. A $1/2$-averaged operator is also $\alpha$-averaged for every $\alpha \in [1/2,1)$, by combining its nonexpansive part with the identity; the equivalence with firm nonexpansiveness specifically uses the parameter $1/2$.

The Browder convergence theorem for averaged operators states: if $T:{\mathbb{R}}^d\to {\mathbb{R}}^d$ is an averaged operator and its fixed-point set $\mathrm{Fix}T=\{z:Tz=z\}$ is nonempty, then for every starting point, $z^{k+1}=T{z}^k$ converges in norm to a fixed point of $T$. The theorem assumes a fixed point exists; averaging by itself does not create one.

The finite-dimensional mechanism is worth making explicit. For any fixed point $p$, the averaged-operator inequality givesThis is Fejér monotonicity with respect to the fixed-point set. It makes the sequence bounded and, by summation, makes ${\sum }_k\Vert z^{k+1}-z^k{\Vert }_2^2$ finite. Hence its residual tends to zero. Choose a convergent subsequence $z^{k_j}\to \bar{z}$; continuity of the nonexpansive mapping $T$ implies $T\bar{z}=\bar{z}$. Apply Fejér monotonicity with $p=\bar{z}$. The nonincreasing distances $\Vert z^k-\bar{z}{\Vert }_2$ have a subsequence tending to zero, so the whole sequence converges to $\bar{z}$. This last compactness step uses finite dimension; a corresponding general Hilbert space statement usually gives weak convergence.

Here $L$-smooth means that $f$ is differentiable on the entire Euclidean space and has an $L$-Lipschitz gradient, with $L>0$. Together with convexity, this implies $1/L$-cocoercivity:First, integration of the Lipschitz gradient along a line segment proves the descent lemma:Indeed, subtract the linear term and integrate $⟨\nabla f(v+t(w-v))-\nabla f(v),w-v⟩$ for $0\le t\le 1$; its absolute value is at most $Lt\Vert w-v{\Vert }_2^2$.

Fix $u$ and define $q(w)=f(w)-⟨\nabla f(u),w⟩$. This is a convex function, has the same Lipschitz gradient constant, and $\nabla q(u)=0$, so $u$ is a global minimizer. Put $d=\nabla f(v)-\nabla f(u)=\nabla q(v)$. The descent lemma at $v$ with $w=v-d/L$ givesThereforeInterchange $u,v$ and add the inequalities. The function values cancel, leaving the asserted cocoercivity. This is a proof of the Baillon–Haddad theorem without assuming a second derivative. Convexity is essential: $f(u)=-\Vert u{\Vert }_2^2/2$ has a $1$-Lipschitz gradient but its gradient is not cocoercive.

Assume $\mathrm{argmin}f\ne \varnothing$, as is necessary for convergence to a minimizer. The printed hypotheses alone omit this condition: $f(x,y)=x$ in scalar $x$ is convex with an $L$-Lipschitz gradient for any prescribed $L>0$, but has no minimizer, and the update sends $x^k=x^0-k\tau$ to $-\infty$.

Under existence, define the full update $T(x,y)=(x^{+},y^{+})$. The proximal $y$-step is uniquely defined by strong convexity of its quadratic term and satisfiesThe partial subdifferential in this equation belongs to the scalar function $y\mapsto f(x,y)$; differentiating a subdifferential itself would not define the printed proximal minimization.

We prove directly that the alternating proximal-gradient operator $T$ is averaged. For two inputs $z=(x,y)$ and $\tilde{z}=(\tilde{x},\tilde{y})$, setThe input difference is $(p,q+\tau b)$, the output difference is $(p-\tau a,q)$, and the difference of the two update residuals is $\tau (a,b)$. Exact expansion givesThe first inequality uses cocoercivity at the mixed points $w,\tilde{w}$. Therefore $T$ is $(\tau L/2)$-averaged for the requested $0<\tau L\le 1$. In particular, the endpoint $\tau L=1$ is covered: $T$ is firmly nonexpansive, not merely nonexpansive.

A fixed point has $y^{+}=y$ and $x^{+}=x$, so the two optimality equations give ${\nabla }_{y}f=0$ and ${\nabla }_{x}f=0$. Conversely, at a minimizer both gradients vanish and neither step moves. By convexity,The assumed existence of a minimizer supplies a fixed point. The Browder convergence theorem for averaged operators now givesNo uniqueness of the minimizer is needed. The same estimate even proves averagedness for $0<\tau L<2$ in this smooth setting, but the requested interval already suffices. The existence condition and the use of the gradient at $(x^k,y^{k+1})$ are both essential to the proof as presented.

Set $r^k=A{x}^k-c$. Completing the square in the $y$-minimization givesThus, with $\sigma =\tau /(1+2\tau )$, the steps in terms of the proximal map of $\varphi$ areThe factor $2$ comes from the squared residual without a $1/2$ prefactor. The proximal map can equivalently be denoted $(I+\sigma \partial \varphi {)}^{-1}$. Since $\varphi$ is a finite convex function, it is continuous, and the quadratic makes the proximal minimizer unique.

A general convex $\varphi$ may be nondifferentiable, so this last example need not satisfy the full $L$-smooth hypothesis of the preceding part. The formulas nevertheless remain well-defined: only the $x$ derivative is used explicitly. If $\varphi$ has an $L_{\varphi }$-Lipschitz gradient, one may take $L=2(\Vert A{\Vert }_2^2+1)+L_{\varphi }$ in the smooth proof, where $\Vert A{\Vert }_2$ is the operator norm.

There is also a useful nonsmooth extension. Put $h(x,y)=\Vert Ax+y-c{\Vert }_2^2$, whose Lipschitz gradient constant is $L_h=2(\Vert A{\Vert }_2^2+1)$. For two updates, retain the mixed-point differences $(p,q)$ above, let $(a,b)=\nabla h(w)-\nabla h(\tilde{w})$, and let $d$ be the difference of the two selected subgradients of $\varphi$ at $y^{+},{\tilde{y}}^{+}$. The input difference is $(p,q+\tau (b+d))$ and the output difference is $(p-\tau a,q)$. Monotonicity of $\partial \varphi$ gives $⟨q,d⟩\ge 0$. The same norm expansion now yieldsFor $0<\tau L_h\le 1$, discard the nonpositive $b$ term and use $2\tau /L_h-{\tau }^2\ge {\tau }^2$. The result is the firmly nonexpansive mapping inequality for the full residual $\tau (a,b+d)$. Fixed points satisfy ${\nabla }_{x}h=0$ and $0\in {\nabla }_{y}h+\partial \varphi$, exactly the subgradient optimality condition for the convex objective. Thus the stated algorithm also converges for nonsmooth $\varphi$ under this sufficient step bound, provided a minimizer exists; this extension uses monotonicity, not an unavailable gradient of $\varphi$.