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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 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... $\endgroup$– SuvritCommented Apr 12, 2013 at 18:12
-
$\begingroup$ 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? $\endgroup$– dineshdileepCommented Apr 13, 2013 at 7:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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$.
-
$\begingroup$ 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. $\endgroup$ Commented May 2, 2013 at 1:34
$\begingroup$
$\endgroup$
5
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.
answered Jul 12, 2013 at 17:49
-
$\begingroup$ 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? $\endgroup$ Commented Jul 12, 2013 at 19:45
-
$\begingroup$ @dineshdileep: No (that would give you a way to solve the original NP-hard [I think] problem). $\endgroup$ Commented Jul 15, 2013 at 12:23
-
$\begingroup$ exactly, so the rank-2 solution will not help, thus making that technique not a globally viable one. $\endgroup$ Commented Jul 16, 2013 at 14:08
-
$\begingroup$ Right, but I would not expect there to exist a globally viable and efficient solution. What type of answer are you hoping for? $\endgroup$ Commented Jul 16, 2013 at 14:24
-
$\begingroup$ I found a theoretical method to do that for three constraints, it is related to joint numerical range of hermitian matrices. $\endgroup$ Commented Jul 19, 2013 at 3:46