I have a minimization problem with quadratic objective and non-negativity constraints: $$\min_u\frac{1}{2}||a-u||^2+\frac{\gamma}{2}||B^Tu-x||^2+\lambda\sum_iu_i\\ \text{s.t } u_i\ge0$$ where $\lambda$ a scalar, $a,x$ are vectors, $B$ a matrix, and $u_i$ the $i$th coordinate of $u$. I am doing a single iteration of projected-gradient algorithm, with $$\text{grad} f=u-a+\gamma B(B^Tu-x)+\lambda$$ where $\lambda$ is now a vector of all coordinates equal to the scalar $\lambda$ (sorry for the abuse of notation). The Lipschitz constant of the gradient is easily calculated to be $$L=||I+\gamma BB^T||_2=1+\gamma\sigma_{\text{max}}^2(B)$$ where the matrix norm is the spectral norm (largest singular value, or $\sigma_{\text{max}}$). All this enables me to choose an optimal step size of $\frac{1}{L}$, which ensures (among other things) that the objective is non-decreasing after the projected gradient step - the projection in my case is simply zeroing the negative coordinates of $u$ after the gradient step.
• Just to be sure, do you mean $L = 1 + \gamma \sigma_{\text{max}}^2(B)$ ? Is your PG scheme the following $u^{(k+1)} \leftarrow \left(u^{(k)} - (1/L)\text{grad}f (u^{(k)})\right)_+$ ? – dohmatob Apr 12 '17 at 13:14
• Yes to both questions (forgot the $\gamma$, thanks) – Itamar Katz Apr 12 '17 at 21:59