Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 339 / 1

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.