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

Let $P_1$, $P_2$ be two hermitian matrices. Can anyone comment about the following (QCQP) \begin{equation} \min_{z}~z^{H}z \\\ ~~subject~to ~z^{H}P_1z+1\leq 0,~z^{H}P_2z+1\leq 0 \end{equation} I am familiar with semi-definite relaxation. But I was wondering if we could do more here, since the objective is convex.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

Yes, a lot can be said for your special case. Given the notation, I presume you are optimizing over $\mathbb{C}^n$. In this case, see Section 2 in the paper Strong Duality in Nonconvex Quadratic Optimization with two Quadratic Constraints, A. Beck and Y. Eldar, SIAM J. Optimization, 17(3), 2006.

PS: The complex variable case seems to be easier than the real variable case.

share|improve this answer
    
@Suvrit thanks for that link. As I understand, the paper talks about the lagrangian relaxation of the above problem and it works well (I tested it). It is essentially a SDP problem. I was wondering if we could come up with some kind of fixed point algorithm for the dual problem of this. –  dineshdileep Nov 21 '12 at 6:28
    
But theorem 2.2 in that paper seems to say that under a finiteness and strict feasibility condition, the relaxation (given by (2.1) in the paper) has the same optimal value as the original problem.... –  Suvrit Nov 21 '12 at 6:46
    
They prove that the duality gap is zero, so the relaxation should give the same value as the original problem. In fact, they say that if we take the dual of this, we will get the semi definite relaxation. The problem for me is I need to implement this in a real time system where I can't assume the availability of a convex optimization package. So I need to come up with an iterative algorithm. It is fine if it converges to a local minimum or not a optimal solution. –  dineshdileep Nov 21 '12 at 8:12
    
well, if your RT system has an floating point processor, and you can compile C code for it, then you can get some open source SDP solver and use it, why not? –  Dima Pasechnik Nov 21 '12 at 8:53
    
e.g. if you have BLAS and LAPACK on your system then you can easily use CSDP: coin-or.org/projects/Csdp.xml –  Dima Pasechnik Nov 21 '12 at 8:58
show 3 more comments

Quadratic optimization subject to fixed number of quadratic constraints is "easy", even without any convexity assumptions. The algorithms are polynomial-time, but in practice quite hard to implement efficiently. See e.g. this.

The complex case can obviously be reduced to the real one.

share|improve this answer
    
Wow, that sounds like a cool paper! I need to read it someday! –  Suvrit Nov 21 '12 at 18:50
add comment

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.