1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Ziyuan
    Apr 23, 2012 at 8:07
  • $\begingroup$ 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. $\endgroup$
    – Suvrit
    Apr 23, 2012 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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