# Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?

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.

• 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. – D.W. Feb 10 at 7:23
• 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. – Alex Meiburg Feb 10 at 8:47
• 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. – D.W. Feb 10 at 18:17