# Homogeneous linear and quadratic inequalities

I have a bunch of vectors $b_i \in R^n$ for $i = 1,\ldots,N$ and a bunch of (indefinite) matrices $A_j$ for $j = 1,\ldots,M$. Let's consider the set $S \subset R^n$ of $x \in R^n$ vectors such that

$$(x,b_i) \geq 0$$ $$(x,A_j x) \geq 0$$

for all $i$ and $j$. Clearly $0 \in S$ and since both conditions are homogeneous, $\lambda x \in S$ if $x \in S$ for $\lambda \geq 0$. So $S$ contains the origin and is connected. It is either the origin only (trivial case) or a set with positive dimension (non-trivial case).

Are there general theorems for finding out if for given $b_i$ and $A_j$ data the situation is trivial or not?

• There 3 independent integers in the problem, $N$, $M$, $n$. Obviously $A_j$ are indefinite. – DanielFetchinson Mar 3 '18 at 16:37
• your problem can be seen as checking feasability of a special case of a QCQP-problem en.wikipedia.org/wiki/… In general the problem is NP-hard. However on page 6 here web.stanford.edu/~boyd/papers/pdf/qcqp.pdf they mention that something can be done if the Aj's have only one negative eigenvalue – Markus Sprecher Apr 6 '18 at 19:46
• Things are nicer if all the $A_j$ commute with each other. – Dima Pasechnik Apr 10 '18 at 23:24