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

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.

LetThe proximal operator optimality condition saysBy subgradient inversion under convex conjugacy, which uses Fenchel–Young inequality and $f^{\ast \ast }=f$ from the Fenchel-Moreau theorem,Consequently $z-p=\tau v\in \tau \partial f^{\ast }(p)$, meaning $p=B_{\tau f^{\ast }}(z)$. Uniqueness of the backward subgradient step identifies the result:This is the scaled Moreau decomposition. It requires one backward step on $f$, with reciprocal parameter $1/\tau$ and scaled input $z/\tau$, followed by a scalar multiplication and subtraction. No separate proximal computation of the convex conjugate is needed.