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

Use the maximizing-dual convention. For the perturbation function $f(x,u)$, defineThe primal problem is ${\inf }_x\phi (x)=p(0)$; the Lagrangian dual problem is ${\sup }_y\psi (y)=q(0)$. The sign convention makes the dual marginal $q$ concave for jointly convex data; some formulations negate $q$ to express a minimization problem.

The central convex perturbation duality calculation isThe last inequality is weak duality. A sufficient finite-dimensional condition for strong duality with dual attainment is: $f$ is jointly proper and convex, $p$ is proper with $p(0)$ finite, and $p$ is finite on a neighborhood of zero. More generally $0\in \mathrm{ri}(\mathrm{dom}p)$ suffices.

Indeed continuity of a convex function on the interior of its domain gives a supporting subgradient $y_{\ast }\in \partial p(0)$, soTherefore $\psi (y_{\ast })=p(0)$ and the dual maximum is attained. This qualification establishes equality and dual attainment; it does not by itself establish a primal minimizer.

For each fixed $z$, choose the convex perturbation functionIt is jointly convex and has marginalBecause $h$ and $k$ are nonnegative and finite everywhere,for every $w$. The inf-convolution is convex: for approximate decompositions of $w_1,w_2$, take their convex combination and use convexity of both costs; then let their approximation errors tend to zero. Thus $F$ is a finite convex function on all of ${\mathbb{R}}^n$, hence continuous everywhere. In particular $p_z$ is proper and finite near zero, so the qualification in the previous solution applies at every $z$:This is strong duality for a finite-valued infimal convolution.

No primal attainment was used. For example $k(x)=e^x$ and $h(x)=0$ meet all the stated assumptions, but $F(z)=0$ is approached only as $x\to -\infty$. This illustrates why a proof based on an assumed minimizing decomposition would be incomplete. The printed functions are real-valued everywhere, not merely extended-real; that distinction supplies continuity and the strong-duality qualification.

Compute the convex conjugate of $f_z$ at a general pair $(v,y)$. With $w=z+u-x$, the independent variables become $(x,w)$ and $u=w+x-z$, soTherefore the Lagrange dual function isUsing strong duality from the preceding solution givesEquivalently the conjugate of an infimal convolution is $F^{\ast }=k^{\ast }+h^{\ast }$, and the continuous convex $F$ equals its biconjugate.

For practical subgradient computation, minimize the known convex dual objectiveEvery optimizer, and only an optimizer, belongs to $\partial F(z)$ by Fenchel–Young inequality. The full characterization isThis is infimal-convolution dual subgradients; the set is nonempty because $F$ is finite convex everywhere. If both conjugates are differentiable at the optimizer, solve $\nabla k^{\ast }(y)+\nabla h^{\ast }(y)=z$. For nonsmooth conjugates, use the displayed aggregate subdifferential or a convex minimization algorithm. Replacing it by $\partial k^{\ast }(y)+\partial h^{\ast }(y)$ requires the usual subdifferential sum rule qualification; it is not automatically justified solely by knowing the two conjugates.