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?

  • $\begingroup$ There 3 independent integers in the problem, $N$, $M$, $n$. Obviously $A_j$ are indefinite. $\endgroup$ – DanielFetchinson Mar 3 '18 at 16:37
  • 1
    $\begingroup$ 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 $\endgroup$ – Markus Sprecher Apr 6 '18 at 19:46
  • $\begingroup$ Things are nicer if all the $A_j$ commute with each other. $\endgroup$ – Dima Pasechnik Apr 10 '18 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.