Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 339 / 2

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.