A Quadratically-Constrainted Quadratic Program consists of optimizing a quadratic objective function while imposing quadratic constraints, which can be inequalities or equalities. Obviously, describing the problem with inequalities alone can suffice, as $a\le b$ and $a\ge b$ is equivalent to just $a=b$. For this reason, a lot of literature just focuses on the inequalities.

However, I only have quadratic equality constraints, without any inequalities. In fact, it's enough constraints, that I believe in my case the space of points satisfying the constraints is discrete (like $2^{n/2}$ separate points or something). So it becomes very little of an "optimization" problem, and much more of a "search space" problem. I would like to figure out a way to transform this system into a form amenable to discrete search, but I can't find any directives on how to accomplish that. All the heuristics/approximations I could find for QCQP definitely seem to treat more of the "not very constrained" case, where you're moving around continuously in the allowed region -- that picture doesn't apply here, though.

I realize that searching all $2^{n/2}$ points is intractable in general, of course. But I hope that whatever form it would come in would then be amenable to its own heuristic searches, like a binary quadratic program is.

  • $\begingroup$ Are the variables possibly over a small finite domain? Or are they continuous (real numbers)? I wonder if any of the methods for solving systems of polynomial equations (e.g., Groebner bases, etc.) would be helpful here. $\endgroup$
    – D.W.
    Feb 10, 2019 at 7:23
  • $\begingroup$ The variables are continuous (complex numbers -- can obviously be rewritten in terms of real numbers if need be). I think something like Groebner bases would work, I would like to get a nice description of the discrete structure of the solutions, but I'm not sure how to do that. $\endgroup$ Feb 10, 2019 at 8:47
  • $\begingroup$ Hmm. I don't have any great ideas for you; sorry. In general the problem remains NP-hard even with only equality constraints. For instance, there's an easy reduction from 3SAT: replace each clause $(x_i \lor x_j \lor x_k)$ with the quadratic equations $(1-x_i)(1-x_j)=t_{ij}$, $t_{ij}(1-x_k)=0$, and add the quadratic equations $x_i(1-x_i)=0$ for each $i$. So I suspect it might be necessary to know something about the structure of your equations to come up with good algorithms. $\endgroup$
    – D.W.
    Feb 10, 2019 at 18:17


Your Answer

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