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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.