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

A vector $g$ is a subgradient of the convex function $f$ at $x$ whenfor every $y$. The set of all such vectors is the subdifferential $\partial f(x)$. The proximal operator satisfiesMore generally, $u={\mathrm{prox}}_{tf}(x)$ exactly when $(x-u)/t\in \partial f(u)$.

The proximal optimality condition givesThe subgradient inequality therefore yields, for every $u$,

Rearranging part i and using the polarization identity givesDropping the final nonpositive term proves

The defining minimization, compared with the candidate $x_k$, shows that $f(x_{k+1})\le f(x_k)$. Put $u=x^{\ast }$ in part ii and sum from $j=0$ to $k-1$. The squared distances telescope, while monotonicity givesHence

The Fenchel conjugate of $h$ is

Set $g(u)=tf(u)+\Vert u{\Vert }^2/2$. Expanding the square givesThe function $g$ is one-strongly convex, so its Fenchel conjugate is differentiable with one-Lipschitz gradient. The displayed identity therefore proves that the Moreau envelope $M_{t}f$ is differentiable even when $f$ is nonsmooth.

The maximizer defining $g^{\ast }(x)$ is ${\mathrm{prox}}_{tf}(x)$, soConsequentlyThus the proximal point algorithm for $f$ is ordinary gradient descent with step $t$ on its smooth Moreau envelope.