Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 339 / 3

A map $T$ is a firmly nonexpansive mapping whenfor all $x,y$. Put $p={\mathrm{prox}}_f(x)$ and $q={\mathrm{prox}}_f(y)$. Then $x-p\in \partial f(p)$ and $y-q\in \partial f(q)$. Monotonicity of the subdifferential giveswhich rearranges to

Write $P_f={\mathrm{prox}}_f$ and $P_h={\mathrm{prox}}_h$. Since $w_k=x_k+z_{k-1}$,and thereforeWith reflected proximal maps $R_f=2P_f-I$ and $R_h=2P_h-I$,Firm nonexpansiveness of each proximal map is equivalent to nonexpansiveness of its reflection. Thus $R_f{R}_h$ is nonexpansive, and its average with the identity is firmly nonexpansive. This is the Douglas–Rachford method.

Take $f=I_C$ and $h=I_D$. Their proximal maps are the projections $P_C,P_D$, soThe Douglas--Rachford shadow sequence $P_D{w}_k$ converges in finite dimensions to a point of $C\cap D$ when the intersection is nonempty.

The functionis the Moreau envelope of the convex indicator $I_D$, and is therefore convex. It is nonnegative and vanishes exactly on $D$. Since $C\cap D\ne \varnothing$, the minimum of $d_D$ over $C$ is zero, and every minimizer belongs to both $C$ and $D$.

The squared distance to a convex set satisfiesThe map $I-P_D$ is firmly nonexpansive because $P_D$ is firmly nonexpansive, soThus $d_D$ is one-smooth in the Euclidean norm.

Projected gradient descent with unit step isThus this instance reduces to alternating Euclidean projections.

Work in the product space $({\mathbb{R}}^n{)}^{\ell }$ and defineThen $\mathcal{C}\cap \mathcal{D}$ is nonempty exactly when ${\bigcap }_j{C}_j$ is nonempty. For $X=(x_1,\dots ,x_{\ell })$,while, with $\bar{x}={\ell }^{-1}{\sum }_j{x}_j$,This is the product-space reformulation of convex feasibility.