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

Let $C_1$,$C_2$,...$C_N$ be $M \times M$ indefinite hermitian matrices. What can we say about the following quadratic constriants \begin{align} w^{H}C_1w>0 \\\ w^{H}C_2w>0 \\\ ...~~~~~~~~~~ \\\ ...~~~~~~~~~~ \\\ w^{H}C_Nw>0 \end{align} where $w$ is a non-zero $M\times 1$ complex vector. Can we come up with conditions for existence of such a $w$? I tried using the CVX package to determine the same (after using semi-definite relaxation). It always gives the zero vector as the answer.

share|improve this question
    
Observe that if there is any $w \neq 0$ that satisfies these constraints, then so does $\alpha w$ for any $\alpha > 0$. Thus, we can let $\alpha \to 0$. However, the zero vector itself is not feasible --- this difficulty happens because you have an open set... –  Suvrit Apr 12 '13 at 18:12
    
hmm,, any other insights? are you familiar with joint numerical ranges? if so, do you think we can connect it to the concept of convexity of joint numerical range? –  dineshdileep Apr 13 '13 at 7:48
add comment

2 Answers 2

As mentioned in its user's guide, CVX does not distinguish between constraints in the form of $f(x) < 0$ and $f(x) \leq 0 $, which is very common in numerical optimization. Instead, you should use

$w^{H} C_i w \geq 1, \quad i = 1,2,\cdots,N$

to avoid the zero vector solution. Of course, you can replace $1$ by any positive constant. This is because we can always find $w$ via scaling so that the above conditions hold provided that the conditions in your original post are satisfied, i.e., there exists $\hat{w}$ such that

$\hat{w}^{H} C_i \hat{w} = \epsilon_i > 0, \quad i = 1,2,\cdots,N$.

share|improve this answer
    
Here $C_i$'s are indefinite hermitian matrices, so $w^HC_iw>=1$ will be a non-convex constraint and hence CVX will return an error. –  dineshdileep May 2 '13 at 1:34
add comment

One option for a convex relaxation is to search for a positive semidefinite hermitian $W$ with $\mathrm{Trace}(WC_i)\geq 1$ for all $i$. These conditions are equivalent to the ones you have written when $W$ is also rank one ($W = ww^H$), i.e., they are necessary but not sufficient for existence of the $w$ you seek.

If you like you could also try minimizing the nuclear norm of $W$ subject to these constraints because that is a heuristic convex surrogate for minimizing rank. If the resulting optimal $W$ is not rank one you could also try for example taking the SVD of the optimal $W$ and see if any of the first few singular vectors has the property you seek.

share|improve this answer
    
i thought about this options, unfortunately the convex relaxation solution is all the time a full rank solution. I didn't try the nuclear norm based technique. But, say we got a rank-2 solution, is it sufficient to say that no rank-1 solutions exist? –  dineshdileep Jul 12 '13 at 19:45
    
@dineshdileep: No (that would give you a way to solve the original NP-hard [I think] problem). –  Noah Stein Jul 15 '13 at 12:23
    
exactly, so the rank-2 solution will not help, thus making that technique not a globally viable one. –  dineshdileep Jul 16 '13 at 14:08
    
Right, but I would not expect there to exist a globally viable and efficient solution. What type of answer are you hoping for? –  Noah Stein Jul 16 '13 at 14:24
    
I found a theoretical method to do that for three constraints, it is related to joint numerical range of hermitian matrices. –  dineshdileep Jul 19 '13 at 3:46
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.