Algorithm for solving system of quadratic equations and linear equations

Question

Let $x \in R^N$. From a Spectral Chebyshev collocation method, I have a system of quadratic and linear equations. Denote them, $$ x^T Q_i x + L_i^T x = 0 $$ and $$ A x = 0 $$ Furthermore, I know the solution will fulfill $$ B x \geq 0 $$ for $Q_i \in R^{N \times N}, L_i \in R^{N}, A\in R^{M \times N}, B\in R^{S\times N}$, and $i = 1,\ldots P$. To get a sense of sizes, I have $N \approx M\approx S \approx P \approx 400$. The matrices $A$ and $B$ would have about $N/2$ nonzeros and each $Q_i$ is going to have around $N/4$ nonzeros.

Question: I can solve this with a nonlinear solver, but are there any other methods (and accompanying software implementations) which can solve this and exploit the fact that everything is linear or quadratic? I have no reason to believe that $Q_i$ lead to any particular structure (e.g., not necessarily positive semi-definite, etc.). That said, I am willing to throw caution to the wind and accept local solutions (especially if there is appropriate software I can throw the problem at).

Apologies for my general ignorance of these types of problems. I have looked at QCQP methods, but they seem to focus on inequality constraints. I am also not sure I can naively put the quadratic constraints as objectives to minimize due to their unknown structure/convexity.

Answer 1

Quadratically constrained quadratic programming (QCQP) focuses on convex inequalities because those preserve the convexity of the problem. Quadratic equalities do not, so this problem is much harder.

Any polynomial equation can be re-written as a system of quadratic equations. (For example: $x^3 = 1$ is equivalent to $\{xy = 1,\, x^2 - y = 0\}$.) So solving a set of quadratic equations is not fundamentally easier than solving a set of polynomial equations.

The Wikipedia page on systems of polynomial equations explains the basics of how these systems are solved. Commercial packages like Maple and Wolfram can do this, and apparently so can the free, open source package Sage.

The advantage of these packages, compared to a non-linear solver is that you would be guaranteed a solution if one exists. The disadvantage is that the search tree grows exponentially in the number of unknowns, so $N \approx 400$ might be impossible unless the inequalities permit very efficient pruning.