Skip to main content
2 of 4
added 22 characters in body
mathworker21
  • 1.4k
  • 1
  • 12
  • 27

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 know how to do it 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.

mathworker21
  • 1.4k
  • 1
  • 12
  • 27