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

Use $z\in {\mathbb{R}}^m$ for the perturbation variable and $y\in {\mathbb{R}}^m$ for its dual variable. The full Fenchel conjugate is $f^{\ast }(v,y)={\sup }_{x,z}(⟨v,x⟩+⟨y,z⟩-f(x,z))$. One signed-marginal convention isThe primal problem of convex perturbation duality is ${\inf }_x\phi (x)=p(0)$ and its dual problem of convex perturbation duality is ${\sup }_y\psi (y)=q(0)$. The signed dual marginal $q$ is concave; some conventions instead use $-q$ as a convex marginal. The definitions above fix all signs. Weak duality follows from $f(x,0)+f^{\ast }(0,y)\ge 0$. Also $p^{\ast }(y)=f^{\ast }(0,y)$, so $q(0)=p^{\ast \ast }(0)$.

For a sufficient strong duality condition, assume $f$ is jointly proper convex, $p$ is proper with $p(0)$ finite, and $p$ is finite and continuous in a neighborhood of $0$. More generally $0\in \mathrm{ri}(\mathrm{dom}p)$ suffices in finite dimensions. A supporting subgradient $y^{\ast }\in \partial p(0)$ then exists, andThus the dual is attained with no gap. This condition does not by itself assert attainment of the primal infimum; that needs an additional compactness or coercivity argument.

The same subgradient describes sensitivity analysis in convex perturbation duality: $p(z)\ge p(0)+⟨y^{\ast },z⟩$ bounds the optimum's change under perturbation. When $p$ is finite convex near zero, its one-sided directional derivative is $p^{\prime }(0;d)={\max }_{y\in \partial p(0)}⟨y,d⟩$. If $\partial p(0)=\{y^{\ast }\}$, then $p$ is differentiable there andThese conditions allow first-order sensitivity predictions; without differentiability the subgradient set gives directional bounds. Multipliers can measure the value of relaxing constraints, quantify changes in noise tolerance, and guide parameter choice without resolving every perturbed problem. For the constraint convention in part (b), the noise-budget sensitivity is negative the nonnegative constraint multiplier.

Let $r(u)=\Vert u-g{\Vert }_2^2$ and fix the reference noise budget $\sigma$. Define the convex perturbation functionPositive $z$ increases the allowed squared noise level. The feasible epigraph set $r(u)\le \sigma +z$ is convex and closed, so this is a proper lower semicontinuous jointly convex perturbation. Writing the inequality indicator as a supremum over its multiplier givesThe Lagrange dual function is $d(\lambda )={\inf }_{u}L(u,\lambda )$ for $\lambda \ge 0$. In the signed convex conjugate convention of part (a), $y=-\lambda$; positive $y$ gives dual objective $-\infty$ because the perturbation can be made arbitrarily large.

The feasible ball is nonempty and compact, so lower semicontinuity of total variation gives a primal minimizer. For $\sigma >0$, $u=g$ satisfies $r(g)=0<\sigma$, providing the Slater condition. Total variation is finite everywhere in the given discretization and hence continuous. Strong duality and dual attainment give a finite optimal ${\lambda }^{\ast }\ge 0$. The pair satisfies the Karush-Kuhn-Tucker conditionsEquivalently,Thus the set of saddle points is nonempty. Compactness handles primal attainment, while strict feasibility supplies a finite multiplier; these are distinct steps. An inactive constraint can yield ${\lambda }^{\ast }=0$. At $\sigma =0$, feasibility still forces $u=g$, but this strict-feasibility argument does not apply.

Let $u^{\prime }$ be any constrained minimizer for $\sigma >0$ and let ${\lambda }^{\ast }$ be a dual optimum. Set the common optimal value to $p^{\ast }$. Weak duality and feasibility implyAll inequalities are therefore equalities. In particular, $u^{\prime }$ minimizes $L(\cdot ,{\lambda }^{\ast })$, whose $-{\lambda }^{\ast }\sigma$ term is constant. HenceThis proves the claim for every constrained minimizer, rather than just for the particular one used to establish a saddle point. The multiplier may be zero, and the penalized minimizer then need not be unique.

Conversely, for $\lambda >0$ the quadratic makes the penalized objective coercive and strictly convex, so it has a unique minimizer $u_{\lambda }$. Choose $\boxed{\sigma =\Vert u_{\lambda }-g{\Vert }_2^2}$. If a feasible $u$ had $\mathrm{TV}(u)<\mathrm{TV}(u_{\lambda })$, thencontradicting penalized optimality. Thus $u_{\lambda }$ solves the constrained problem at that budget. This is constrained-penalized equivalence for total variation denoising. It is a correspondence of minimizers and suitable parameters, not a claim that every budget has a unique multiplier or a unique constrained minimizer.