Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 325 (Set-valued Analysis and Optimisation)

Use the extended real numbers $\overline{\mathbb{R}}=\mathbb{R}\cup \{-\infty ,+\infty \}$. A proper convex function never takes $-\infty$ and is finite somewhere. Its effective domain isFor a proper extended-real function, convexity meansThe endpoint cases are identities; taking $0<t<1$ avoids the ambiguous product $0\cdot (+\infty )$. Equivalently, its epigraph is a convex set. In particular, the effective domain is a convex set. Properness is an additional condition: it rules out the identically $+\infty$ function and all $-\infty$ values, rather than requiring finiteness everywhere.

For $x\in \mathrm{dom}f$, the subdifferential is the set of supporting slopesEach element is a subgradient. Define $\partial f(x)=\varnothing$ outside $\mathrm{dom}f$. The defining subgradient inequality must hold globally, not merely in a neighborhood of $x$. For a differentiable finite convex function, $\partial f(x)=\{\nabla f(x)\}$.

Write $h=f\square g$ for the infimal convolution. It is proper by the permitted hypothesis. If $h(x_0)$ and $h(x_1)$ are finite, choose $y_0,y_1$ within $\epsilon$ of their respective infima. For $0<t<1$, put $x_t=(1-t)x_0+t{x}_1$ and $y_t=(1-t)y_0+t{y}_1$. Convexity of $f$ and $g$ givesLet $\epsilon \downarrow 0$. If either endpoint value is infinite, the desired inequality is automatic. Thus the infimal convolution is convex, without assuming the infimum is attained.

For its convex conjugate, replace a negative infimum by a supremum and then change variables $u=x-y$:The two suprema separate because $u$ and $y$ are independent. Properness of $f$ and $g$ makes each supremum strictly greater than $-\infty$, so this separation remains valid when one or both are $+\infty$. Therefore $(f\square g{)}^{\ast }=f^{\ast }+g^{\ast }$. This is the conjugate of an infimal convolution. The bounded-domain assumption is unnecessary for these two calculations; the assumed properness and lower semicontinuity of $h$ will be used when applying subgradient inversion under convex conjugacy.

Use the conventionThis proximal map is also the resolvent of a monotone operator $(I+\tau \partial f{)}^{-1}$. A proper lower semicontinuous convex function has an affine minorant, so the quadratic term makes this minimization coercive and strongly convex. A unique minimizer exists for every $x$. Its subgradient optimality condition isThe Moreau–Yosida regularisation is $f_{\tau }=f\square g^{\tau }$. The conjugate of an infimal convolution and the quadratic conjugate giveThe factor $\tau$ here is essential. Apply subgradient inversion under convex conjugacy, followed by the subdifferential sum rule with the everywhere differentiable quadratic:The last equivalence is precisely the unique proximal minimization condition. ThusThis proves both existence and uniqueness of the subgradient, rather than only identifying a possible element. The finite convex function $f_{\tau }$ is therefore differentiable, with $\nabla f_{\tau }=(I-P_{\tau })/\tau$, the gradient of a Moreau envelope.

For completeness, monotonicity of $\partial f$ applied to the two proximal conditions givesHence $P_{\tau }$ is firmly nonexpansive. Expanding the same inequality shows that $I-P_{\tau }$ is firmly nonexpansive too. In particular, $\nabla f_{\tau }$ is $1/\tau$-Lipschitz continuous. None of this requires a bounded effective domain; the result applies to the next example as well.

For the Euclidean norm, rotational symmetry and minimizing the radial objective give the radial soft thresholding formulaIndeed, if $r=\Vert x{\Vert }_2$, an optimal $u$ is a nonnegative scalar multiple of $x$; minimizing $s+(r-s{)}^2/(2\tau )$ over $s\ge 0$ gives $s=(r-\tau {)}_{+}$. The gradient of a Moreau envelope is consequentlyAt $x=0$ this is $\{0\}$, and the two expressions agree when $\Vert x{\Vert }_2=\tau$. The Moreau envelope of the Euclidean norm itself isThus a quadratic core replaces the nondifferentiable tip while the outer gradient remains the normalized radial direction. The Euclidean norm has an unbounded effective domain, unlike the earlier bounded-domain hypothesis; the preceding argument explicitly shows that this restriction is unnecessary here.

For convex optimization, this Moreau–Yosida regularisation permits gradient descent and other methods for functions with a Lipschitz gradient, using a gradient Lipschitz constant $1/\tau$. It approximates the norm uniformly: $0\le \Vert x{\Vert }_2-f_{\tau }(x)\le \tau /2$. Smaller $\tau$ improves approximation but makes the permitted gradient steps smaller. Minimizing $f_{\tau }$ alone preserves the minimizers and minimum value of $f$; replacing one term in a larger objective can shift the minimizer, so the smoothing parameter controls that approximation error.

For $0<\alpha <1$, an averaged operator has the formfor some nonexpansive mapping $R$, meaning $\Vert Rz-Rw{\Vert }_2\le \Vert z-w{\Vert }_2$ for all $z,w$. The word averaging refers to a convex combination with the identity. It does not mean averaging function values over a neighborhood.

An equivalent and useful averaged-operator inequality isTo see it, put $d=z-w$ and $r=Rz-Rw$ and expandUse $\Vert r{\Vert }_2\le \Vert d{\Vert }_2$ and $(I-T)z-(I-T)w=\alpha (d-r)$. Conversely, substituting $R=[T-(1-\alpha )I]/\alpha$ into the same expansion proves its nonexpansiveness from the displayed inequality. The strict range $0<\alpha <1$ matters for convergence of unrelaxed iterations: a general nonexpansive mapping such as $T=-I$ can have nonconvergent alternating iterates.

A firmly nonexpansive mapping satisfiesWriting $d=z-w$ and $a=Tz-Tw$, this is equivalent toIt is also equivalent to $\Vert 2a-d{\Vert }_2\le \Vert d{\Vert }_2$, so $R=2T-I$ is a nonexpansive mapping. Consequently firm nonexpansiveness is exactly $1/2$-averagedness. A proximal map of a proper lower semicontinuous convex function is a basic example. A $1/2$-averaged operator is also $\alpha$-averaged for every $\alpha \in [1/2,1)$, by combining its nonexpansive part with the identity; the equivalence with firm nonexpansiveness specifically uses the parameter $1/2$.

The Browder convergence theorem for averaged operators states: if $T:{\mathbb{R}}^d\to {\mathbb{R}}^d$ is an averaged operator and its fixed-point set $\mathrm{Fix}T=\{z:Tz=z\}$ is nonempty, then for every starting point, $z^{k+1}=T{z}^k$ converges in norm to a fixed point of $T$. The theorem assumes a fixed point exists; averaging by itself does not create one.

The finite-dimensional mechanism is worth making explicit. For any fixed point $p$, the averaged-operator inequality givesThis is Fejér monotonicity with respect to the fixed-point set. It makes the sequence bounded and, by summation, makes ${\sum }_k\Vert z^{k+1}-z^k{\Vert }_2^2$ finite. Hence its residual tends to zero. Choose a convergent subsequence $z^{k_j}\to \bar{z}$; continuity of the nonexpansive mapping $T$ implies $T\bar{z}=\bar{z}$. Apply Fejér monotonicity with $p=\bar{z}$. The nonincreasing distances $\Vert z^k-\bar{z}{\Vert }_2$ have a subsequence tending to zero, so the whole sequence converges to $\bar{z}$. This last compactness step uses finite dimension; a corresponding general Hilbert space statement usually gives weak convergence.

Here $L$-smooth means that $f$ is differentiable on the entire Euclidean space and has an $L$-Lipschitz gradient, with $L>0$. Together with convexity, this implies $1/L$-cocoercivity:First, integration of the Lipschitz gradient along a line segment proves the descent lemma:Indeed, subtract the linear term and integrate $⟨\nabla f(v+t(w-v))-\nabla f(v),w-v⟩$ for $0\le t\le 1$; its absolute value is at most $Lt\Vert w-v{\Vert }_2^2$.

Fix $u$ and define $q(w)=f(w)-⟨\nabla f(u),w⟩$. This is a convex function, has the same Lipschitz gradient constant, and $\nabla q(u)=0$, so $u$ is a global minimizer. Put $d=\nabla f(v)-\nabla f(u)=\nabla q(v)$. The descent lemma at $v$ with $w=v-d/L$ givesThereforeInterchange $u,v$ and add the inequalities. The function values cancel, leaving the asserted cocoercivity. This is a proof of the Baillon–Haddad theorem without assuming a second derivative. Convexity is essential: $f(u)=-\Vert u{\Vert }_2^2/2$ has a $1$-Lipschitz gradient but its gradient is not cocoercive.

Assume $\mathrm{argmin}f\ne \varnothing$, as is necessary for convergence to a minimizer. The printed hypotheses alone omit this condition: $f(x,y)=x$ in scalar $x$ is convex with an $L$-Lipschitz gradient for any prescribed $L>0$, but has no minimizer, and the update sends $x^k=x^0-k\tau$ to $-\infty$.

Under existence, define the full update $T(x,y)=(x^{+},y^{+})$. The proximal $y$-step is uniquely defined by strong convexity of its quadratic term and satisfiesThe partial subdifferential in this equation belongs to the scalar function $y\mapsto f(x,y)$; differentiating a subdifferential itself would not define the printed proximal minimization.

We prove directly that the alternating proximal-gradient operator $T$ is averaged. For two inputs $z=(x,y)$ and $\tilde{z}=(\tilde{x},\tilde{y})$, setThe input difference is $(p,q+\tau b)$, the output difference is $(p-\tau a,q)$, and the difference of the two update residuals is $\tau (a,b)$. Exact expansion givesThe first inequality uses cocoercivity at the mixed points $w,\tilde{w}$. Therefore $T$ is $(\tau L/2)$-averaged for the requested $0<\tau L\le 1$. In particular, the endpoint $\tau L=1$ is covered: $T$ is firmly nonexpansive, not merely nonexpansive.

A fixed point has $y^{+}=y$ and $x^{+}=x$, so the two optimality equations give ${\nabla }_{y}f=0$ and ${\nabla }_{x}f=0$. Conversely, at a minimizer both gradients vanish and neither step moves. By convexity,The assumed existence of a minimizer supplies a fixed point. The Browder convergence theorem for averaged operators now givesNo uniqueness of the minimizer is needed. The same estimate even proves averagedness for $0<\tau L<2$ in this smooth setting, but the requested interval already suffices. The existence condition and the use of the gradient at $(x^k,y^{k+1})$ are both essential to the proof as presented.

Set $r^k=A{x}^k-c$. Completing the square in the $y$-minimization givesThus, with $\sigma =\tau /(1+2\tau )$, the steps in terms of the proximal map of $\varphi$ areThe factor $2$ comes from the squared residual without a $1/2$ prefactor. The proximal map can equivalently be denoted $(I+\sigma \partial \varphi {)}^{-1}$. Since $\varphi$ is a finite convex function, it is continuous, and the quadratic makes the proximal minimizer unique.

A general convex $\varphi$ may be nondifferentiable, so this last example need not satisfy the full $L$-smooth hypothesis of the preceding part. The formulas nevertheless remain well-defined: only the $x$ derivative is used explicitly. If $\varphi$ has an $L_{\varphi }$-Lipschitz gradient, one may take $L=2(\Vert A{\Vert }_2^2+1)+L_{\varphi }$ in the smooth proof, where $\Vert A{\Vert }_2$ is the operator norm.

There is also a useful nonsmooth extension. Put $h(x,y)=\Vert Ax+y-c{\Vert }_2^2$, whose Lipschitz gradient constant is $L_h=2(\Vert A{\Vert }_2^2+1)$. For two updates, retain the mixed-point differences $(p,q)$ above, let $(a,b)=\nabla h(w)-\nabla h(\tilde{w})$, and let $d$ be the difference of the two selected subgradients of $\varphi$ at $y^{+},{\tilde{y}}^{+}$. The input difference is $(p,q+\tau (b+d))$ and the output difference is $(p-\tau a,q)$. Monotonicity of $\partial \varphi$ gives $⟨q,d⟩\ge 0$. The same norm expansion now yieldsFor $0<\tau L_h\le 1$, discard the nonpositive $b$ term and use $2\tau /L_h-{\tau }^2\ge {\tau }^2$. The result is the firmly nonexpansive mapping inequality for the full residual $\tau (a,b+d)$. Fixed points satisfy ${\nabla }_{x}h=0$ and $0\in {\nabla }_{y}h+\partial \varphi$, exactly the subgradient optimality condition for the convex objective. Thus the stated algorithm also converges for nonsmooth $\varphi$ under this sufficient step bound, provided a minimizer exists; this extension uses monotonicity, not an unavailable gradient of $\varphi$.

Let $S:{\mathbb{R}}^p\rightrightarrows {\mathbb{R}}^q$ be a set-valued mapping and let $\bar{v}\in S(\bar{u})$. The Aubin property at $(\bar{u},\bar{v})$ means there are neighborhoods $U$ of $\bar{u}$, $V$ of $\bar{v}$, and a finite constant $\kappa \ge 0$ such thatHere ${\mathbb{B}}_q$ is the closed unit ball. Equivalently, every solution $v\in S(u)$ near $\bar{v}$ can be matched to a solution $v^{\prime }\in S(u^{\prime })$ within $\kappa \Vert u-u^{\prime }{\Vert }_2$. The localization is on the left-hand side: the matching point need not be in $V$. The property is also called the Lipschitz-like property.

For sensitivity analysis, let $u$ represent data or perturbations and $S(u)$ the set of feasible or optimal solutions. The Aubin property bounds how far a nearby solution can move when the data change. Taking $u=\bar{u}$, $v=\bar{v}$ also guarantees a nearby solution for each sufficiently small perturbation $u^{\prime }$. It is a stability estimate for a relation, and by itself does not imply uniqueness or differentiability. For a single-valued solution map, it reduces to local Lipschitz continuity.

Work in finite-dimensional Euclidean spaces. Suppose the graph of a set-valued mapping,is locally closed at $(\bar{u},\bar{v})\in \mathrm{gph}S$. Local closedness means that its intersection with some neighborhood of this point is closed relative to that neighborhood. This assumption is part of the criterion.

For a set $C$ and $z\in C$, define the Fréchet normal cone byAt an isolated point the condition is vacuous, so all vectors are regular normals. The limiting normal cone consists of limits of these regular normals at nearby points:It can be nonconvex. The Mordukhovich coderivative isThe minus sign in the output-dual component is part of the definition. For a single-valued continuously differentiable mapping $s$, the graph normal is $(Ds(\bar{u}{)}^T{v}^{\ast },-v^{\ast })$, giving $D^{\ast }s(\bar{u}\mid s(\bar{u}))(v^{\ast })=\{Ds(\bar{u}{)}^T{v}^{\ast }\}$. Thus the coderivative extends a transpose derivative, rather than the ordinary forward derivative.

The exact Mordukhovich criterion isThis is equivalent to excluding a nonzero horizontal limiting graph normal $(u^{\ast },0)$. One must use the limiting normal cone; simply checking regular normals at the reference point can miss normals inherited from neighboring graph pieces.

For sensitivity analysis, apply this test to a solution map or use coderivative and normal cone calculus to express its graph normals through optimality constraints. Triviality of this kernel then proves Lipschitz-like stability without solving the perturbed problem explicitly. Under these same finite-dimensional, locally closed assumptions, the exact Lipschitz modulus is the outer normThe zero-kernel condition is the qualitative criterion; the modulus quantifies the sensitivity bound. For the next problem an explicit local formula is simpler than evaluating these graph normals.

Write the objective as $F_a(x)=\alpha x^2/2+n^{-1}{\sum }_i{\ell }_i(x)$ with ${\ell }_i(x)=\max \{0,1-a_{i}x\}$. Each hinge loss is finite and convex, so the subdifferential sum rule applies without a qualification gap. Its subdifferential isThis formula also covers $a_i=0$, if such a sample is allowed, because the loss is then constant. For a convex function, zero in the subdifferential is necessary and sufficient for global optimality. Thus $x$ is optimal exactly when there are weights ${\lambda }_i$ such thatEquivalently, using $I(x)=\{i:a_{i}x<1\}$ and $J(x)=\{i:a_{i}x=1\}$,The notation $[0,1]a_i$ denotes the segment between $0$ and $a_i$, also when $a_i<0$. This avoids reversing interval endpoints for negative-class samples.

Because $\alpha >0$, the objective is strongly convex, and $F_a(x)\ge \alpha x^2/2$ makes it coercive. It is continuous, so a minimizer exists and is unique for every finite data vector $a$. The weights at exact margins need not be unique even though $x$ is. These are the hinge-loss optimality weights for the one-dimensional support vector machine.

Yes: the solution map is locally affine, hence has the Aubin property. Keep the regularization parameter $\alpha >0$ fixed and define the active hinge setSince none of the margins vanishes, the optimality condition at the reference data has no fractional weights:For nearby $a$, define the candidateEach map $a\mapsto 1-a_i{x}_I(a)$ is continuous and is nonzero at $\hat{a}$. Because there are finitely many samples, all their signs remain unchanged on a common neighborhood $U$ of $\hat{a}$. Therefore the same set $I$ is active at $x_I(a)$ for every $a\in U$. The hinge-loss optimality weights are still $1$ on $I$ and $0$ off $I$, and the defining equation for $x_I(a)$ proves the subgradient optimality condition. Strong convexity makes this candidate the unique global minimizer. Consequently the solution map of a parametric optimization problem satisfiesThis argument establishes stability of the active pattern without presupposing continuity of the unknown optimizer; continuity is used only for an explicit candidate and then optimality is checked.

For $a,b\in U$, the Cauchy-Schwarz inequality givesThis is the Aubin property with $\kappa =\sqrt{|I|}/(\alpha n)$. In fact this constant is the exact local Lipschitz continuity modulus of the affine branch, since its derivative isThe active-set dependence of this derivative is the active-set sensitivity of hinge-loss minimization. At a vanishing margin the affine-branch argument no longer applies, although failure of this particular argument does not by itself prove failure of the Aubin property.

For the illustration, take $n=2$, $\alpha =1$, and $a=(s,1)$ with $s>0$. The hinge-loss optimality weights giveOn the middle branch the first margin is exactly zero, so that branch lies outside the strict-margin hypothesis. The example makes clear why the local affine conclusion is tied to that hypothesis, and also shows that a zero margin need not destroy local Lipschitz stability.