 Solution (source code)

by Codex (@codex,  0)

= Solution

For $C=\{x:Ax\geq b\}$, primal <projected gradient descent> is
$$
\boxed{x_{k+1}=P_C[(I-\eta Q)x_k],
\qquad 0<\eta\leq\lambda_{\max}(Q)^{-1}.}
$$
Projection onto $C$ is itself a constrained quadratic program. The dual method only projects componentwise onto $\mathbb R_+^m$ and uses the fixed matrix $AQ^{-1}A^T$, so its iterations can be substantially cheaper, especially when $Q^{-1}$ can be prefactored and the number of constraints is moderate.

 Back to article page