Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 339 (Topics in Convex Optimisation)

The Euclidean projection onto a convex set is nonexpansive, and $x^{\ast }=P_C(x^{\ast })$ because the optimum is feasible. Therefore the projected subgradient method satisfiesThe subgradient inequality gives $⟨g_i,x_i-x^{\ast }⟩\ge f(x_i)-f^{\ast }$, while Lipschitz continuity of the finite convex function gives $\Vert g_i{\Vert }_2\le G$. HenceSumming this telescoping inequality for $0\le i<k$, and then bounding the smallest term by the average, yieldsWriting $D=\Vert x_0-x^{\ast }{\Vert }_2$, the right-hand side is minimized by the constant step sizeSubstitution givesIf $D=0$, the initial point is already optimal and the result is immediate.

Associate a nonnegative Lagrange multiplier ${\lambda }_i$ with each inequality. The Lagrangian dual problem begins withIts infimum over $x\in {\mathbb{R}}^n$ is finite exactly when $A^T\lambda +c=0$, in which case it equals $-b^T\lambda$. The dual linear program is consequentlyFor any primal-feasible $x$ and dual-feasible $\lambda$,which proves weak duality. Strong duality means equality of the two optimal values. The stated strict feasibility is the Slater condition; together with finiteness of the primal optimum it gives strong duality and an attained dual optimum ${\lambda }^{\ast }$.

Let ${\lambda }^{\ast }$ be an optimal dual multiplier and define the maximum violationDual stationarity and strong duality imply, for every $x$,Since every component of $Ax-b$ is at most $v(x)$ and ${\lambda }^{\ast }\ge 0$,It follows that the exact maximum-violation penalty obeysChoose any $M>\Vert {\lambda }^{\ast }{\Vert }_1$. A primal optimum has $v(x)=0$ and penalized value $p^{\ast }$, whereas every infeasible point has $v(x)>0$ and penalized value strictly greater than $p^{\ast }$. Thus the penalized problem and the original linear program have exactly the same minimizers.

Write $a_i^T$ for row $i$ of $A$, and define affine functionsThenThe pointwise maximum of convex functions is convex, so $f$ is a convex function. Moreover,so $f$ has Lipschitz continuity. The simpler bound $L\le \Vert c{\Vert }_2+M{\max }_i\Vert a_i{\Vert }_2$ is also valid.

Let $I(x)=\{i:{\ell }_i(x)=f(x)\}$ be the active set. The subdifferential isthe convex hull of all active slopes. In particular, choosing any active index gives the subgradientAt a tie, every convex combination of the tied slopes is also valid.

The objective is strictly convex, so the minimizer is unique. The Slater condition makes the Karush-Kuhn-Tucker conditions necessary and sufficient. Absorb the box constraints into the Euclidean projection onto a convex set and attach a scalar multiplier $\nu$ to $a^{T}x=b$. Stationarity over the box is equivalent towhile primal feasibility requires $a^T{x}^{\ast }=b$. Coordinatewise, these conditions areThey are also sufficient because they minimize the Lagrangian over the box and satisfy the equality constraint. Thus the projection onto a box-constrained hyperplane reduces to solving the displayed one-dimensional continuous, nonincreasing equation for $\nu$. The multiplier need not be unique on a flat interval, but the projected vector is unique.

For a proper lower-semicontinuous convex function $f$, its proximal operator isThe squared norm is strongly convex, so the minimizer is unique. The subdifferential sum rule gives the necessary and sufficient conditionMore generally,The subgradient inversion rule for the convex conjugate says $u\in \partial f(x)$ exactly when $x\in \partial f^{\ast }(u)$. Hencewhich is precisely the proximal optimality conditionSince $x=y-tu$, this proves the generalized Moreau decomposition

The function $\varphi (x)={\max }_{v\in C}⟨x,v⟩$ is the support function ${\sigma }_C$. For a nonempty compact convex set,so its convex conjugate is the indicator function ${\iota }_C$. Applying the Moreau decomposition,Multiplication of an indicator function by a positive scalar does not change it, and its proximal operator is the Euclidean projection onto a convex set. Therefore

Take $a=1$ and $b=k$, sois the capped simplex. A linear objective over this convex polytope attains its maximum at a zero-one extreme point. Choosing the $k$ coordinates at which $x_i$ is largest givesEquivalently, an exchange of weight from a smaller component to a larger one never decreases the objective. Thus the sum of the largest components is the support function ${\sigma }_C$.

Part c now givesBy the projection onto a box-constrained hyperplane, $v=P_C(y/t)$ hasConsequently the proximal operator is evaluated by solving this one-dimensional equation for $\nu$, then substituting the resulting projection.

SetThe gradient has Lipschitz continuity with constantwhere the norm is the spectral norm. The proximal gradient method is thereforeFor $\lambda >0$, part d makes the second step explicit:where $C$ is the capped simplex; when $\lambda =0$, this proximal step is the identity.

A standard fixed choice is $0<\alpha \le 1/L$; the wider interval $0<\alpha <2/L$ also gives convergence under the usual forward-backward conditions. For a general convex objective, the function-value error is $O(1/r)$. If $A$ has full column rank, the quadratic term is strongly convex and an appropriate fixed step gives a linear convergence rate.