Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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

 
discard

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.