MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to solve the follong QCQP problem:

$$ \mbox{Minimize}\quad\beta^TA\beta+\mu\Omega(\beta)$$ $$ \mbox{s.t.}\quad\beta^TB\beta=1 \quad\mbox{and}\quad\beta\ge0 $$

where $A$ and $B$ are both positive definite, and $\Omega(\cdot)$ is a sparse(thus non-smooth, but still convex) norm, like $\ell_1$ norm or $\ell_1/\ell_2$ norm for a certain group set.

My tentative plan is to combine FISTA algorithm and Homotopy methods (a relevant paper I've found) for $f(\beta)=\beta^TA\beta++\lambda(\beta^TB\beta-1)+\mu\Omega(\beta)$, which can handle both $\beta$ and the Lagrange multiplier $\lambda$, but I did not find an algorithm considering the constraint $\beta\ge 0$(in the entry-wise sense). So can I improve the algorithm to embrace the conic constraits? Thank you.

share|cite|improve this question
up vote 2 down vote accepted

There are several methods that one could apply to this problem. I don't have time to write out a full solution, but here's a quick idea. Replace $\Omega$ by $\hat\Omega = \Omega + \delta_+$, where $\delta_+$ is the indicator function for the nonnnegative orthant. Now, if you can reduce your problem to a proximal splitting method that works roughly as (not exactly this because of your equality constraints)

$$ \beta^{k+1} \gets \mbox{prox}(\beta^k - \eta_k\nabla L(\beta^k)), $$ where $L$ is the differentiable part of the problem, and $\mbox{prox}$ is the proximity-operator that handles $\hat\Omega$, then you are done.

Fortunately, the proximity-operator of $\hat\Omega$ is merely the composition of the proximity operator of $\Omega$ with projection onto the nonnegative orthant. Thus, in some sense, you can easily use FISTA style methods.

share|cite|improve this answer
Why is it a sum? Did you mean $\hat{\Omega}(\beta)=\Omega(\beta)+1$ if $\beta\in\mathbb{R}^p_+$ and $\hat{\Omega(\beta)}=\Omega(\beta)$ otherwise? – Ziyuan Lin Apr 23 '12 at 8:07
No, I mean $\delta_+$ to be indicator function for the nonnegative orthant. So, if $\beta \ge 0$, $\delta_+=0$, otherwise $\delta_+ = +\infty$. It is just an alternative way of writing the constraint $\beta \ge 0$, but it reveals how to handle the constraint via the proximity operator itself. – Suvrit Apr 23 '12 at 16:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.