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

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.