2
$\begingroup$

I have, for $6n$ real variables, a system of O$(n^2)$ inequalities over the reals. $n$ of these are linear, while the rest are quadratic. How do I determine that for some $n$

  1. a solution exists,
  2. and if it does, what is the solution set?

I am looking for the algorithms with the best possible computational complexity. For (2) I will even be happy with finding one solution if doing so is faster than finding the solution set. What are some methods to do this?

If codes already exist for these methods I will appreciate links.

$\endgroup$
1
  • 3
    $\begingroup$ You'd be interested in literature on "QCQP" (quadratically constrained quadratic programming) $\endgroup$
    – Suvrit
    Aug 20, 2016 at 23:47

1 Answer 1

2
$\begingroup$

The complexity is going to be horrible, since this is as hard as the general ETR hard problem. For more, see https://en.wikipedia.org/wiki/Existential_theory_of_the_reals

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.