Determining if a quadratic form is non-negative if variables are non-negative Let $f(x_1,\dots,x_n) = \sum_{1 \le i \le j \le n} c_{i,j}x_ix_j$ be a homogeneous quadratic form. Is there a quick-ish way to determine whether $f(x_1,\dots,x_n) \ge 0$ for all $x_1,\dots,x_n \ge 0$?
I have a specific homogeneous quadratic form, where $n=44$. I am wondering whether I have to use a super computer to prove that it is non-negative if all of the variables are. I prefer not to disclose my quadratic form.
In general, I know how to figure out whether a given quadratic form is non-negative if the variables are, in $2^n$ time, since $f$ has at most $2^n$ (quickly computable) local minima on the set $\{(x_1,\dots,x_n) \in \mathbb{R}^n : x_1+\dots+x_n = 1, x_1,\dots,x_n \ge 0\}$ (choose a certain subset of the variables to be $0$, and then we get a bunch of linear equations, from looking at derivatives, that determine the rest). But I'm wondering if there's a quicker way, in general.
 A: It's mentioned in the introduction here that the problem of determining whether a matrix is copositive is NP-complete:
http://www-ljk.imag.fr/membres/Roland.Hildebrand/c6classification/cop_cert.pdf
Checking copositivity is a special case of (nonconvex) quadratic programming. There's a paper which reduces nonconvex quadratic programming to mixed-integer linear programming (with promising results) by using the KKT conditions:
https://arxiv.org/abs/1511.02423
I'd recommend doing the same for your particular quadratic program, and then feeding the resulting mixed-integer linear program into a state-of-the-art solver. These solvers use branch-and-bound techniques to prune the search tree, making it much more efficient in practice than trying to brute-force all $2^{44}$ subsets.
A: You might consider the "sum-of-squares" approach.  The idea is to find a set of polynomials so that your expression is the sum of squares of the elements in the region of interest.  For your case, you could replace each $x_i$ with a new variable $z_i^2$; you are now asking if the corresponding 4-th degree unconstrained polynomial is non-negative.
This restatement may not sound like an improvement, but it turns out that SOS problems can be attacked using semidefinite programming techniques (e.g., see this page).  You can use a freely available SDP solvers.
This is a sufficient approach, i.e., it may prove that your original quadratic form is positive, but it can't disprove it.  Since you're trying to solve a specific problem, though, it may be worth the gamble.
