Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 62 / 4 / a / Solution

The forward subgradient step and backward subgradient step are the set-valued mapsThus $u\in B_{\tau f}(z)$ means $z-u\in \tau \partial f(u)$. They are respectively the explicit and implicit time discretizations of subgradient flow $\dot{x}\in -\partial f(x)$. At a differentiable point the forward update is $x-\tau \nabla f(x)$, while the backward update evaluates the gradient at the new point. For proper closed convex data the latter is the proximal operator

To prove at most one output, suppose $u,v\in B_{\tau f}(z)$. Then $(z-u)/\tau \in \partial f(u)$ and $(z-v)/\tau \in \partial f(v)$. The two subgradient inequalities imply monotonicity of a convex subdifferential, givingSince $\tau >0$, $u=v$. Convexity supplies this monotonicity; lower semicontinuity is not needed for this at-most-one argument.

Under the full printed assumptions the output actually exists at every $z$. Properness ensures a finite point and excludes $-\infty$. Proper lower-semicontinuous convex $f$ has an affine minorant, so the quadratic proximal objective is coercive. Lower semicontinuity makes its minimum attained on a compact sublevel set. Convexity and the positive quadratic curvature make it strongly convex, hence its minimizer is unique. The subgradient optimality condition, with the differentiable quadratic term, is exactly $z-u\in \tau \partial f(u)$. ThusThis also identifies precisely which assumptions provide existence, uniqueness and the update's optimality interpretation.