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

A vector $g$ is a subgradient of the convex function $f$ at $x$ whenfor every $y$. The set of all such vectors is the subdifferential $\partial f(x)$. The proximal operator satisfiesMore generally, $u={\mathrm{prox}}_{tf}(x)$ exactly when $(x-u)/t\in \partial f(u)$.

The proximal optimality condition givesThe subgradient inequality therefore yields, for every $u$,

Rearranging part i and using the polarization identity givesDropping the final nonpositive term proves

The defining minimization, compared with the candidate $x_k$, shows that $f(x_{k+1})\le f(x_k)$. Put $u=x^{\ast }$ in part ii and sum from $j=0$ to $k-1$. The squared distances telescope, while monotonicity givesHence

The Fenchel conjugate of $h$ is

Set $g(u)=tf(u)+\Vert u{\Vert }^2/2$. Expanding the square givesThe function $g$ is one-strongly convex, so its Fenchel conjugate is differentiable with one-Lipschitz gradient. The displayed identity therefore proves that the Moreau envelope $M_{t}f$ is differentiable even when $f$ is nonsmooth.

The maximizer defining $g^{\ast }(x)$ is ${\mathrm{prox}}_{tf}(x)$, soConsequentlyThus the proximal point algorithm for $f$ is ordinary gradient descent with step $t$ on its smooth Moreau envelope.

For the equality constraint, the Lagrangian and dual function areand the Lagrangian dual problem is ${\sup }_{z\in {\mathbb{R}}^m}q(z)$. Weak duality says $q(z)\le p^{\ast }$ for every $z$. Strong duality means the dual supremum equals the primal infimum, usually with a dual maximizer. A sufficient convex constraint qualification is that $f$ be proper, closed and convex and that some $x\in \mathrm{ri}(\mathrm{dom}f)$ satisfy $Ax=b$.

Use multiplier $-z$ for $Ax-b-s=0$. The Lagrangian isThe infimum over $s$ is finite exactly when $z\ge 0$. The infimum over $x$ occurs at $x=Q^{-1}{A}^{T}z$, and henceThe dual is ${\max }_{z\ge 0}h(z)$. Since the primal objective is coercive, the explicit Slater conditionis sufficient for feasibility, attainment, and equality of primal and dual values.

Let $M=A{Q}^{-1}{A}^T$. Since $\nabla h(z)=b-Mz$, projected gradient ascent on the nonnegative orthant iswhere the positive part is componentwise and one may take $0<\eta \le 1/L$.

The Hessian of $-h$ is $M=A{Q}^{-1}{A}^T$. Thus $-h$ is strongly convex exactly when $A$ has full row rank. In that case one may useIn all cases, the gradient has Lipschitz constant bounded by

When $A$ has full row rank, projected gradient ascent with step $1/L$ has linear convergence and requiresiterations, up to the initial-error constant. The accelerated projected method of Nesterov requiresWithout full row rank, the general smooth-convex bounds are $O(L{R}^2/ϵ)$ and $O(\sqrt{L{R}^2/ϵ})$, respectively, when a dual optimum lies within distance $R$ of the initial point.

For $C=\{x:Ax\ge b\}$, primal projected gradient descent isProjection onto $C$ is itself a constrained quadratic program. The dual method only projects componentwise onto ${\mathbb{R}}_{+}^m$ and uses the fixed matrix $A{Q}^{-1}{A}^T$, so its iterations can be substantially cheaper, especially when $Q^{-1}$ can be prefactored and the number of constraints is moderate.

A map $T$ is a firmly nonexpansive mapping whenfor all $x,y$. Put $p={\mathrm{prox}}_f(x)$ and $q={\mathrm{prox}}_f(y)$. Then $x-p\in \partial f(p)$ and $y-q\in \partial f(q)$. Monotonicity of the subdifferential giveswhich rearranges to

Write $P_f={\mathrm{prox}}_f$ and $P_h={\mathrm{prox}}_h$. Since $w_k=x_k+z_{k-1}$,and thereforeWith reflected proximal maps $R_f=2P_f-I$ and $R_h=2P_h-I$,Firm nonexpansiveness of each proximal map is equivalent to nonexpansiveness of its reflection. Thus $R_f{R}_h$ is nonexpansive, and its average with the identity is firmly nonexpansive. This is the Douglas–Rachford method.

Take $f=I_C$ and $h=I_D$. Their proximal maps are the projections $P_C,P_D$, soThe Douglas--Rachford shadow sequence $P_D{w}_k$ converges in finite dimensions to a point of $C\cap D$ when the intersection is nonempty.

The functionis the Moreau envelope of the convex indicator $I_D$, and is therefore convex. It is nonnegative and vanishes exactly on $D$. Since $C\cap D\ne \varnothing$, the minimum of $d_D$ over $C$ is zero, and every minimizer belongs to both $C$ and $D$.

The squared distance to a convex set satisfiesThe map $I-P_D$ is firmly nonexpansive because $P_D$ is firmly nonexpansive, soThus $d_D$ is one-smooth in the Euclidean norm.

Projected gradient descent with unit step isThus this instance reduces to alternating Euclidean projections.

Work in the product space $({\mathbb{R}}^n{)}^{\ell }$ and defineThen $\mathcal{C}\cap \mathcal{D}$ is nonempty exactly when ${\bigcap }_j{C}_j$ is nonempty. For $X=(x_1,\dots ,x_{\ell })$,while, with $\bar{x}={\ell }^{-1}{\sum }_j{x}_j$,This is the product-space reformulation of convex feasibility.