Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 65 / 3

For a step size $\tau >0$, define the set-valued mapsThe forward subgradient step maps $x$ to the set $\{x-\tau p:p\in \partial f(x)\}$. If $f$ is differentiable this is the explicit gradient step $x-\tau \nabla f(x)$. The backward subgradient step consists of the $y$ satisfying $x-y\in \tau \partial f(y)$, an implicit step for the subgradient flow. It is the resolvent of a monotone operator associated with $\partial f$.

Suppose $y_1,y_2\in B_{\tau f}(x)$. Then $p_i=(x-y_i)/\tau \in \partial f(y_i)$. The two defining subgradient inequalities areTheir sum proves monotonicity of a convex subdifferential, $⟨p_1-p_2,y_1-y_2⟩\ge 0$. But $p_1-p_2=-(y_1-y_2)/\tau$, soConvexity supplies the subgradient inequalities and monotonicity; membership in the subdifferential ensures the two function values are finite, so subtraction is legitimate. Positivity of $\tau$ supplies the decisive sign. Properness rules out the identically infinite and negative-infinity pathologies in the overall setting, but lower semicontinuity is not needed for this at-most-one argument. Its role is in existence, proved next. The backward step cannot have two values, though uniqueness alone has not yet shown its domain is all of ${\mathbb{R}}^n$.

Fix $x$ and minimize $J_x(y)=f(y)+\Vert y-x{\Vert }^2/(2\tau )$. A proper lower semicontinuous convex function has an affine minorant $f(y)\ge a\cdot y+b$, as follows by separating a point below its closed epigraph. HenceThe quadratic dominates the linear term, proving coercivity. Properness supplies at least one finite trial value, lower semicontinuity passes to limits, and finite-dimensional compactness makes a bounded minimizing sequence converge along a subsequence to a minimizer. Thus the proximal operator exists at every $x$.

The subdifferential sum rule applies because the quadratic is finite and continuous everywhere. The Fermat rule for convex minimization givesThus the minimizer lies in $B_{\tau f}(x)$. The uniqueness proved in part (a), or strict convexity of the quadratic sum, now yieldsThis proof displays the separate roles of properness, lower semicontinuity, convexity and finite dimension. In particular, compactness here is not inferred merely from strict convexity.

Write $A_1={\mathrm{Div}}_1$ and $A_2={\mathrm{Div}}_2$, with Euclidean adjoints $A_1^{\ast },A_2^{\ast }$ determined by the chosen discretization and boundary conditions. Take the usual positive total generalized variation weights ${\alpha }_1,{\alpha }_2$. Introduce a primal variable $w\in {\mathbb{R}}^{n\times 2}$ throughThe support function of the row-ball product is a sum of row norms. Convex duality gives the equivalent augmented saddle problemThe equality follows by dualizing the row-ball constraint. With positive radii, $v=0$ strictly satisfies both row constraints, supplying the finite-dimensional qualification for this splitting. The original feasible dual set is compact and nonempty, and the quadratic primal term is coercive; saddle points exist. The TGV divergence splitting avoids the difficult projection onto $\{v:v\in C,A_{1}v\in D\}$.

Use the Chambolle–Pock algorithm. Choose $\tau ,\sigma >0$ with $\tau \sigma \Vert K{\Vert }^2<1$; the sufficient bound $\tau \sigma (\Vert A_2{\Vert }^2+\Vert A_1{\Vert }^2)<1$ is convenient. Initialize $u^0,w^0,v^0$ and ${\bar{u}}^0=u^0$, ${\bar{w}}^0=w^0$. For $k=0,1,\dots$, computeThe dual update is a Euclidean projection onto a convex set onto $C$; the two primal updates are the quadratic proximal operator and radial soft thresholding. Their signs follow from $K^{\ast }v=(A_{2}v,-A_{1}v)$. All substeps are closed form, and the standard finite-dimensional primal-dual convergence result applies to this saddle problem with the stated step-size condition. The iterates $v^k$ satisfy $C$; the additional $D$ constraint is enforced through the splitting at convergence, not claimed for every intermediate iterate. If a weight is zero, the corresponding row projection or support-function proximal step is interpreted directly rather than by division by zero.