0
$\begingroup$

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.

My problem is that when I apply this step to real data, the objective sometimes grows, which doesn't make sense. Do I have a mistake in the above derivation?

$\endgroup$
  • $\begingroup$ 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)_+$ ? $\endgroup$ – dohmatob Apr 12 '17 at 13:14
  • $\begingroup$ Yes to both questions (forgot the $\gamma$, thanks) $\endgroup$ – Itamar Katz Apr 12 '17 at 21:59
  • $\begingroup$ You derivations above seem correct to me. I'd advice to check for bugs in your code. Such a scheme is provably monotone. $\endgroup$ – dohmatob Apr 13 '17 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.