# Solving a QCQP problem with sparse regularization

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.

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.
• 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