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

Let $\mathcal{H}$ be the family of closed half-spaces containing $C$. Certainly $C\subseteq {\bigcap }_{H\in \mathcal{H}}H$. To prove the reverse inclusion, exclude an arbitrary $z\notin C$.

Suppose first that $C$ is nonempty. Its Euclidean projection onto a convex set $p$ exists: minimizing the continuous squared distance may be restricted to a sufficiently large closed ball, whose intersection with the closed set is compact. Put $d=z-p\ne 0$. For every $x\in C$, convexity puts $p+t(x-p)$ in $C$ for $0\le t\le 1$. Minimality of $p$ givesThus the closed half-spacecontains $C$, while $⟨d,z⟩=⟨d,p⟩+\Vert d{\Vert }^2$ excludes $z$. Since every point outside $C$ is excluded by some member of $\mathcal{H}$,This is the half-space representation of a closed convex set. If $C=\varnothing$, every point can again be excluded by a containing half-space, so the intersection is empty. If $C={\mathbb{R}}^n$, no proper half-space contains it and the empty intersection is, by convention, ${\mathbb{R}}^n$.

The Legendre-Fenchel transform and biconjugate areThe Fenchel-Moreau theorem says that every proper convex function which is lower semicontinuous equals its biconjugate. More generally, if a proper extended-real $f$ has an affine minorant, thenwhere the right side is the greatest lower semicontinuous convex minorant. This is biconjugation as closed convexification. The affine-minorant hypothesis ensures that the closed convexification is proper; an unqualified statement including arbitrary improper functions would need separate conventions.

Here are the essential proof steps. The Fenchel–Young inequality gives $f^{\ast \ast }\le f$. Every term in the supremum defining $f^{\ast \ast }$ is an affine minorant of $f$, and conversely any affine minorant $⟨p,x⟩+a\le f(x)$ has $a\le -f^{\ast }(p)$. Thus $f^{\ast \ast }$ is exactly the supremum of all affine minorants, hence is convex and lower semicontinuous.

Put $g=\mathrm{clconv}f$. Its epigraph is the closed convex hull of the epigraph of $f$. Applying the half-space representation of a closed convex set in ${\mathbb{R}}^{n+1}$ recovers that epigraph from its containing half-spaces. A containing half-space writtenhas $q\le 0$, since epigraphs extend upwards. If $q<0$, it is precisely the epigraph inequality of an affine minorant, $t\ge (⟨v,x⟩-a)/(-q)$.

Vertical half-spaces with $q=0$ must also be accounted for. Choose one affine minorant ${\ell }_0$ of $g$, which exists because $g$ is proper and closed: strictly separate $(x_0,g(x_0)-1)$ from its epigraph for a finite domain point $x_0$; the separating coefficient of $t$ cannot be zero, since that would not distinguish points with the same $x_0$. If a vertical containing inequality is $⟨v,x⟩\le a$, thenis still an affine minorant on the domain of $g$. At a point violating the vertical inequality, these minorants tend to infinity as $L\to \infty$. Thus vertical domain restrictions are also recovered by the supremum of affine minorants.

Consequently $g$ equals that supremum. Every affine minorant of $g$ is below $f$, while the epigraph of any affine minorant of $f$ contains its closed convex epigraph hull. Therefore $f$ and $g$ have the same affine minorants, completing $g=f^{\ast \ast }$. The theorem in the previous solution supplies the geometric separation step behind biconjugation.

Let $C=\mathrm{conv}\{a,b\}$. Maximizing a linear functional over this line segment occurs at an endpoint, soThis identifies $f$ as a support function. Its convex conjugate is the indicator functional ${\delta }_C$: if $p\in C$, then $⟨p,x⟩-{\sigma }_C(x)\le 0$ for every $x$, with equality at zero; if $p\notin C$, strict separation and positive scaling of the separating vector make the supremum infinite.

For a convex function, equality in the Fenchel–Young inequality characterizes its subdifferential. HenceThis is support-function subgradients as exposed faces. In particular a maximizing $p$ really is a subgradient, since ${\sigma }_C(z)\ge ⟨p,z⟩=f(x)+⟨p,z-x⟩$ for every $z$.

Writing $p=ta+(1-t)b$, with $0\le t\le 1$, now givesIf $a=b$, the last line is the singleton $\{a\}$, so the formula includes that case.

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.

One form of Farkas lemma states that exactly one of the following holds:Their mutual exclusion is immediate: if both held, $b^{T}y=z^T{A}^{T}y\ge 0$.

For existence of the alternative certificate, let $C=\{Az:z\ge 0\}$, the finitely generated cone of the columns of $A$. It is convex. It is also closed, a fact that must be justified rather than assumed for arbitrary linear images of closed cones. In a representation with dependent active generators, choose a nonzero dependence ${\sum }_j{d}_j{a}_j=0$ with at least one $d_j>0$. Subtractfrom the nonnegative coefficient vector. The represented point is unchanged, all coefficients remain nonnegative, and at least one active coefficient disappears. Iteration produces a representation with independent active columns. For a convergent sequence in $C$, pass to a subsequence using the same independent set, possible because there are finitely many sets. Its coefficients converge through a fixed left inverse, and their limits remain nonnegative. This proves closedness of finitely generated cones.

The indicator functional ${\delta }_C$ is therefore proper, lower semicontinuous and convex. Its Legendre-Fenchel transform isIndeed a positive pairing with a cone generator can be scaled arbitrarily, while all nonpositive pairings give supremum zero. The Fenchel-Moreau theorem now givesIf $b\notin C$, the left side is infinite, so some feasible $w$ has $⟨w,b⟩>0$. Taking $y=-w$ gives $A^{T}y\ge 0$ and $b^{T}y<0$. If $b\in C$, the first alternative holds. The biconjugation theorem applied to a closed finitely generated cone proves the alternative.

For inequalities $Cx\le d$ with unrestricted $x$, split $x=x_{+}-x_{-}$ and add nonnegative slack:The equivalent Farkas certificate for linear inequalities is

Use the standard form $Cz\le d$ with unrestricted $z=(x,y{)}^T$:The nonnegative multipliersatisfies $C^{T}w=0$ and $d^{T}w=-1<0$. This is a Farkas certificate for linear inequalities, so the system is infeasible by Farkas lemma. In scalar form, adding twice the first inequality to the other two produceswhich directly exhibits the contradiction.

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.

Use the nonnegative-pairing dual cone $K^{\ast }=\{y:⟨y,s⟩\ge 0\text{ for all }s\in K\}$. The Lagrangian is $L(x,y)=c^{T}x-y^T(Ax-b)$ for $y\in K^{\ast }$. Its infimum over unrestricted $x$ is finite exactly when $A^{T}y=c$. Therefore the conic dual problem isThe final equality uses the self-dual cone assumption.

For the canonical self-concordant barrier, use its logarithmically homogeneous barrier normalizationAt parameter $\mu >0$, the primal barrier problem isWrite $F_{†}(y)=F^{\ast }(-y)$, the Legendre dual cone barrier. The matching dual barrier problem isDefining the dual barrier this way is valid generally; self-duality of the cone alone does not assert that an arbitrarily selected barrier equals its Legendre dual.

The joint central path characterization isThe primal stationarity equation is $c+\mu A^T\nabla F(s)=0$, exactly the dual feasibility equation after defining $y$. For the dual relation, logarithmic homogeneity gives $\nabla F(s/\mu )=-y$, so $\nabla F_{†}(y)=-s/\mu$. Thus dual stationarity is $-b+\mu \nabla F_{†}(y)+Ax=0$, giving the same primal equation. At these points,

Newton step. At a chosen target parameter $\hat{\mu }>0$, defineLinearizing the three equality conditions gives the central-path Newton systemEliminating the slack and dual directions yieldsThe barrier Hessian is positive definite. Full column rank of $A$ therefore makes $A^{T}HA$ positive definite and the reduced solve unique. Use a damped step with $s+\alpha \Delta s$ and $y+\alpha \Delta y$ remaining interior; a full Newton step need not do so.

At an exact point with parameter $\mu$, choosing $\hat{\mu }<\mu$ gives $r_p=r_d=0$ and $r_c=(\hat{\mu }-\mu )\nabla F(s)$, the usual predictor towards the next path point. Infinitesimally,

The path definition presupposes interior feasibility and attainment of the barrier problems; strict primal-dual feasibility is a standard sufficient setting. The printed full-rank condition by itself is insufficient. For example $K={\mathbb{R}}_{+}^2$, $A=(1,-1{)}^T$, $b=0$ and $c=0$ give the sole primal feasible point $x=0$, with no interior slack at all, despite full column rank. Rank guarantees the Newton solve at an interior point, not existence of the central path.

Put $d_i(u)=((G^{(1)}u{)}_i,(G^{(2)}u{)}_i)$. The image penalty is discrete isotropic total variation ${\sum }_i\Vert d_i(u){\Vert }_2$; the fidelity term is the L1 norm $\Vert u-f{\Vert }_1$. Introduce scalars $v_i,t_i$ and minimize the linear objectivesubject to the following affine residuals being cone-feasible:where ${\mathcal{L}}_3=\{(t,a,b):t\ge \sqrt{a^2+b^2}\}$ is the Lorentz cone. Every component displayed is affine in $(u,v,t)$, so stacking them gives exactly the requested $Ax-b\in K$ form, withThe first two inequalities imply $v_i\ge |u_i-f_i|$, so separate nonnegativity constraints for $v_i$ are unnecessary. The cone constraints imply $t_i\ge \Vert d_i(u){\Vert }_2$. Every lifted feasible objective bounds the original objective from above; choosing $v_i=|u_i-f_i|$ and $t_i=\Vert d_i(u){\Vert }_2$ gives equality. Since both objective weights are positive, an optimum uses these tight values. Thus the lift is an exact second-order cone program for box-constrained TV-L1 denoising.

The product cone is proper, closed, convex and self-dual. The stacked $A$ has full column rank: the box rows recover $u$, the fidelity rows then recover $v$, and the first coordinates of the Lorentz blocks recover $t$. Strict feasibility is also explicit: choose $u_i=1/2$, then take $v_i>|u_i-f_i|$ and $t_i>\Vert d_i(u){\Vert }_2$.

For generic cone slack $(r,q)$, a canonical barrier ison $r_j>0$ and $q_{i0}>\sqrt{q_{i1}^2+q_{i2}^2}$. The positive sheet condition matters: positivity of the quadratic expression alone would also include the wrong Lorentz nappe.

Composing the barrier with the affine residual map givesIts domain includes the strict inequalities above. Each orthant coordinate contributes one to the self-concordant barrier parameter and each Lorentz block contributes two. Therefore the product-cone logarithmically homogeneous barrier hasThe affine composition $\Phi$ is the barrier used in the primal variables; it need not itself be logarithmically homogeneous in $(u,v,t)$ because the image data and box offsets are affine constants.