Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 65 (Convex Optimisation with Applications in Image Processing)

If $C={\mathbb{R}}^n$, the family of proper containing half-spaces is empty and its intersection is, by convention, ${\mathbb{R}}^n$. If $C=\varnothing$, every closed half-space contains it and their intersection is empty. Now suppose $C$ is a nonempty proper closed convex set. Take $x\notin C$ and let $z$ be its Euclidean projection onto a convex set. This projection exists: a minimizing sequence can be restricted to a bounded ball, and closedness gives attainment. It is unique by convexity and strict convexity of squared distance.

For $y\in C$, the segment $z+t(y-z)$ remains in $C$ for $0\le t\le 1$. Minimality at $t=0$ impliesThus the closed half-space $H_x=\{y:⟨x-z,y-z⟩\le 0\}$ contains $C$ but excludes $x$, since $⟨x-z,x-z⟩>0$. Every point outside $C$ is excluded by at least one containing half-space. The reverse inclusion is immediate, givingThis is the half-space representation of a closed convex set. The argument gives an explicit separating hyperplane rather than just citing a Hahn-Banach separation theorem.

For an extended-real function define its Fenchel conjugate by $f^{\ast }(p)={\sup }_x(⟨p,x⟩-f(x))$ and its biconjugate by $f^{\ast \ast }(x)={\sup }_p(⟨p,x⟩-f^{\ast }(p))$. The Fenchel-Moreau theorem states, in the standard proper-envelope setting,Here the right side is the largest lower semicontinuous convex function below $f$, equivalently the function whose epigraph is the closed convex hull of $\mathrm{epi}f$. It is enough to assume $f$ is proper and has an affine minorant, ensuring this envelope is proper. In particular, for a proper convex function that is lower semicontinuous, $\boxed{f^{\ast \ast }=f}$.

First, $⟨p,x⟩-f^{\ast }(p)\le f(x)$ by the definition of the convex conjugate. The biconjugate is a supremum of continuous affine functions, so it is convex, lower semicontinuous and no greater than $f$. Second, the best intercept for an affine minorant with slope $p$ is $-f^{\ast }(p)$: $⟨p,x⟩+a\le f(x)$ for all $x$ precisely when $a\le -f^{\ast }(p)$. Thus $f^{\ast \ast }$ is the supremum of all affine minorants.

To prove that no part of the closed convex envelope is missed, set $E=\mathrm{cl}\mathrm{conv}(\mathrm{epi}f)$. The half-space representation of a closed convex set from part (a), applied in ${\mathbb{R}}^{n+1}$, separates any $(x_0,t_0)\notin E$ from $E$ by an inequality $a\cdot x+bt\le d$. Because $E$ is upward closed, $b\le 0$. If $b<0$, division by $-b$ gives an affine minorant $\ell$ with $\ell (x_0)>t_0$.

A vertical separator has $b=0$. Let ${\ell }_0$ be an existing affine minorant. Combine $a\cdot x\le d$ with ${\ell }_0(x)\le t$ to obtainSince $a\cdot x_0-d>0$, a sufficiently small positive $\epsilon$ makes this affine function exceed $t_0$. Thus vertical half-spaces can be approximated by nonvertical epigraph supports. Every point below the envelope is excluded by an affine minorant, so the supremum of these minorants is exactly the envelope. This is the decisive use of part (a).

Properness and the minorant convention matter for unrestricted extended-real functions. For example, $f(x)=-x^2$ on $\mathbb{R}$ has no affine minorant; $f^{\ast }\equiv +\infty$ and $f^{\ast \ast }\equiv -\infty$. With the corresponding improper-envelope convention its closed convex envelope is also $-\infty$. The theorem should not silently describe such an envelope as proper. The identically $+\infty$ function is another degenerate case, handled separately by extended-real conventions.

The conjugate of an infimal convolution is the sum of the conjugates:Here $g^{\ast }(p)=\frac{1}{2}\Vert p{\Vert }_2^2$, and $h^{\ast }(p)={\delta }_{[-1,1{]}^n}(p)$, the indicator functional of the unit infinity-norm ball. ThusThe infimal convolution is finite convex and continuous, so the Fenchel-Moreau theorem applies without a closure defect. By equality in the Fenchel–Young inequality and the subdifferential sum rule,This is precisely the variational characterization of projecting $x$ onto the cube. ConsequentlyFor the primal split, $y_i=\mathrm{clip}(x_i,-1,1)$ and $z_i=\mathrm{sign}(x_i)(|x_i|-1{)}_{+}$. These directly minimize the two scalar terms. The Huber loss is continuously differentiable, including at $x_i=\pm 1$, but its second derivative changes there. The one-dimensional sketch shows a quadratic center joined tangentially to linear tails:

Applied to a discrete gradient, the Huber gradient regularizer penalizes small slopes quadratically and large slopes linearly. Compared with pure squared-gradient smoothing it preserves large edges better; compared with pure total variation denoising it encourages small smooth variations and reduces the strong preference for piecewise-constant plateaus. It can therefore be useful for denoising signals or images containing both smooth regions and sharp transitions. It still penalizes edges and can bias their amplitude, and it does not guarantee complete elimination of staircasing in total variation denoising. The unit threshold must be scaled appropriately for data units and grid spacing.

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.

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.

Introduce the primal slack $s=Ax-b\in K$. The Lagrangian is $L(x,y)=c^{\top }x-⟨y,Ax-b⟩$, with $y\in K^{\ast }=K$. Minimizing over $x$ is finite only when $A^{\top }y=c$. Thus the conic dual problem isThe primal-dual gap at feasible points is $c^{\top }x-b^{\top }y=⟨s,y⟩\ge 0$. Self-duality specifies the multiplier cone; it does not alone guarantee feasible or bounded problems. The central-path discussion assumes primal and dual strict feasibility and a finite optimum. These additional existence conditions are not implied by the given full column rank of $A$.

Let $F$ be the canonical logarithmically homogeneous self-concordant barrier, with parameter $\nu$ and $F(ts)=F(s)-\nu \log t$. For each $\mu >0$, minimizing $c^{\top }x+\mu F(Ax-b)$ defines the primal central path. Its stationarity defines the dual path through $y=-\mu \nabla F(s)\in \mathrm{int}K$. The joint characterization isEuler's identity for logarithmic homogeneity gives $⟨s,\nabla F(s)⟩=-\nu$, so $\boxed{⟨s,y⟩=\nu \mu }$. The gap tends to zero as $\mu \downarrow 0$. If $F_{\ast }(y)={\sup }_{s\in \mathrm{int}K}[-⟨y,s⟩-F(s)]$ is the dual barrier, the equivalent dual relation is $s=-\mu \nabla F_{\ast }(y)$. A self-dual cone does not justify identifying two arbitrary primal and dual barrier functions without this relation.

For a target parameter $\bar{\mu }>0$, form residuals $r_p=Ax-b-s$, $r_d=A^{\top }y-c$ and $r_c=y+\bar{\mu }\nabla F(s)$. Linearization gives the central-path Newton systemFor a strictly feasible primal-dual iterate with $r_p=r_d=0$, elimination reduces it toThe barrier Hessian is positive definite and $A$ has full column rank, so the reduced matrix is positive definite. Alternatively a changing path parameter can be included as an additional linear term $\Delta \mu \nabla F(s)$; the displayed system instead fixes the new target parameter before solving.

This is an interior-point method because iterates stay in the cone interiors where the barrier and its gradient/Hessian are defined. A full Newton step need not do so. Use a fraction-to-boundary or backtracking step: decrease $\alpha >0$ until $s+\alpha \Delta s$ and $y+\alpha \Delta y$ lie in $\mathrm{int}K$, then enforce an appropriate barrier or residual decrease. Such a positive step exists because the current points are interior. Local barrier norms can also certify an interior step via the Dikin ellipsoid.

For a practical starting point, choose $e\in \mathrm{int}K$ and solve a conic phase-I problem, for example minimizing $t$ subject to $Ax-b+te\in K$ and $t\ge -1$. A large positive $t$ with an arbitrary $x$ gives a strictly feasible start for this auxiliary problem. A feasible point with $t<0$ certifies $Ax-b\in \mathrm{int}K$. If the original problem is strictly feasible, a small negative $t$ is feasible, so phase I can find such a certificate. A similar feasibility procedure handles the dual equality and interior. Alternatively an infeasible-start primal-dual method or homogeneous self-dual embedding starts with interior cone variables while allowing nonzero linear residuals, and can report infeasibility rather than presume an interior solution exists.

The fidelity norm here is unsquared, as in the original PDF. Write $(s{)}_{+}=\max (s,0)$, so $h(Gu)={\sum }_i((Gu{)}_i{)}_{+}^2$. Introduce $a,q\in {\mathbb{R}}^n$ and $t\in \mathbb{R}$. The second-order cone reformulation of one-sided quadratic denoising issubject to the affine cone constraintswhere ${\mathcal{Q}}_d=\{(r,z):r\ge \Vert z{\Vert }_2\}$ is the second-order cone. All coordinates displayed inside the cone memberships are affine in the optimization variables, so stacking them has precisely the form $Ax-b\in K$. The first cone enforces $t\ge \Vert u-g{\Vert }_2$, and each three-dimensional cone enforces $q_i\ge a_i^2$. The two scalar inequalities give $a_i\ge ((Gu{)}_i{)}_{+}$.

Every feasible lift therefore has objective at least the original objective. Conversely, for any $u$, choose $a_i=((Gu{)}_i{)}_{+}$, $q_i=a_i^2$ and $t=\Vert u-g{\Vert }_2$ to attain equality. Thus the reformulation is exact. It is a second-order cone program over the product $K={\mathcal{Q}}_{n+1}\times {\mathcal{Q}}_3^n\times {\mathbb{R}}_{+}^{2n}$, a proper closed self-dual cone. It preserves the asymmetric derivative penalty; replacing it by $\Vert Gu{\Vert }^2$ would change the problem.

The canonical Lorentz-cone barrier is $-\log (r^2-\Vert z{\Vert }^2)$ on $r>\Vert z\Vert$, and each orthant coordinate contributes $-\log s$. Their sum, composed with the affine slack map, isIts domain explicitly requires $t>\Vert u-g\Vert$, $q_i>a_i^2$, $a_i>0$ and $a_i>(Gu{)}_i$; the positive Lorentz branch must not be inferred merely from positivity of a squared expression. The barrier parameter of the product-cone barrier is $\boxed{\nu =4n+2}$, with two per Lorentz block and one per scalar orthant slack. A strict feasible lift can always be obtained by choosing $a$ above both bounds, $q$ above $a^2$, and $t$ above the fidelity norm.

A kernel support vector machine constructs a large-margin classifier in a feature Hilbert space. Given training points $x_i$ and labels $y_i\in \{-1,1\}$, choose a feature map $\Phi :X\to \mathcal{H}$ and an affine score $f(x)=⟨w,\Phi (x)⟩+b$. Prediction is the sign of the score. Normalizing the functional margin to one makes the closest separating geometric margin $1/\Vert w\Vert$, and the full margin between the two supporting hyperplanes is $2/\Vert w\Vert$. Maximizing that margin therefore minimizes $\frac{1}{2}\Vert w{\Vert }^2$.

For separable data, the hard-margin support vector machine primal isNoisy or nonseparable data use slack variables and the soft-margin support vector machine:Eliminating $\xi$ gives the equivalent hinge loss objective $\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i(1-y_{i}f(x_i){)}_{+}$. The parameter balances margin size against violations; it is not a hard bound on their number. The bias is unpenalized here, which determines the equality constraint in the dual.

Attach multipliers ${\alpha }_i\ge 0$ to $1-{\xi }_i-y_{i}f(x_i)\le 0$ and ${\eta }_i\ge 0$ to $-{\xi }_i\le 0$. The Lagrangian isStationarity gives $w={\sum }_i{\alpha }_i{y}_i\Phi (x_i)$, ${\sum }_i{\alpha }_i{y}_i=0$ and $C-{\alpha }_i-{\eta }_i=0$. Eliminating $w,b,\xi$ yieldswhere $k(x,x^{\prime })=⟨\Phi (x),\Phi (x^{\prime })⟩$ is a positive-definite kernel, meaning positive semidefinite Gram matrices. The hard-margin dual is the same objective with only ${\alpha }_i\ge 0$, without the upper bound. Soft-margin strict feasibility follows by taking $w=b=0$ and all ${\xi }_i>1$, so strong duality and the Karush-Kuhn-Tucker conditions apply. For separable hard-margin data a separator can be rescaled to give strict margins, supplying the analogous qualification. Although the feature space may be infinite dimensional, projecting $w$ onto the finite span of the training feature vectors preserves scores and cannot increase its norm, so this optimization reduces to a finite span.

The complementary slackness relations arePoints with ${\alpha }_i>0$ are support vectors. If $0<{\alpha }_i<C$, then ${\xi }_i=0$ and $y_{i}f(x_i)=1$; such a point gives $b=y_i-{\sum }_j{\alpha }_j{y}_{j}k(x_j,x_i)$. A point with ${\alpha }_i=C$ can lie inside the margin or be misclassified, while ${\alpha }_i=0$ contributes no term to $w$. If no coefficient lies strictly between the bounds, an admissible bias must be obtained from the KKT inequalities, rather than dividing by a nonexistent margin vector. Bias and dual coefficients can be nonunique even when the optimal feature-space weight is unique.

The kernel trick operates both during training and prediction. The dual optimization uses only the Gram matrix $K_{ij}=k(x_i,x_j)$, so the feature vectors need not be formed. Prediction likewise usesA nonlinear kernel therefore makes a linear separator in feature space represent a nonlinear boundary in input space. For example, on ${\mathbb{R}}^2$ the degree-two polynomial kernel $(x\cdot x^{\prime }{)}^2$ corresponds to $\Phi (x)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2)$. Gaussian kernels yield infinite-dimensional feature spaces. An arbitrary similarity is not automatically a valid kernel: for every finite collection and real coefficients $a_i$, one needs ${\sum }_{i,j}{a}_i{a}_{j}k(x_i,x_j)\ge 0$. This makes the dual quadratic form positive semidefinite and the maximization concave.

Mercer's theorem gives a spectral realization under its additional analytic hypotheses. For a continuous symmetric positive-semidefinite kernel on a compact domain with a finite full-support measure, the integral operator $(T_{k}f)(x)=\int k(x,x^{\prime })f(x^{\prime })d\mu (x^{\prime })$ is compact, self-adjoint and positive. The Mercer expansion iswith the standard uniform convergence conclusions under these hypotheses. Since ${\sum }_j{\lambda }_j{e}_j(x{)}^2=k(x,x)<\infty$, the nonlinear feature mapis well defined. This explains the connection of Mercer kernels to Hilbert space features, rather than treating the kernel trick as a purely formal substitution.

The finite-Gram positivity condition is more general than this compact-domain spectral theorem. Every such kernel generates a Reproducing-kernel Hilbert space: on finite sums of kernel sections definequotient out zero-norm elements, and complete. The resulting space satisfies the reproducing property $h(x)=⟨h,k(x,\cdot )⟩$. Its canonical feature map is $\Phi (x)=k(x,\cdot )$, whose inner product is exactly $k(x,x^{\prime })$. A feature map need not be injective; calling it an embedding does not by itself prove distinct inputs remain distinct. The kernel support vector machine uses this geometry together with convex duality to fit and evaluate a maximum-margin classifier while accessing the geometry only through kernel evaluations.