# Feasibility of a given set of homogenuous nonconvex quadratic inequality constraints

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.

-
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

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

-
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

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.

-
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