7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ will not diagonaliztion of symmetric matrices algorithm work here? $\endgroup$
    – vidyarthi
    Sep 19 '20 at 4:24
  • 3
    $\begingroup$ @vidyarthi if you diagonalize, it is very hard to use the non-negativity condition, which might be (and is, in my particular case) crucial. I think you might be thinking about showing the quadratic form is positive definite, which is stronger. $\endgroup$ Sep 19 '20 at 4:36
  • 3
    $\begingroup$ Isn't this just a form of Quadratic Programming? Since you have no constraints on your $c_{ij}$ I believe it'll be NP-hard, so you shouldn't expect a much quicker way. $\endgroup$ Sep 19 '20 at 5:56
  • 3
    $\begingroup$ You want to test whether a matrix is "copositive". $\endgroup$
    – Harry West
    Sep 21 '20 at 7:56
  • $\begingroup$ You might find the criteria that you're looking for in this article Hannu Väliaho - Criteria for copositive matrices (1986) $\endgroup$
    – alezok
    Sep 21 '20 at 8:25
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thank you for your answer. On page 4 of the first link you gave, do I have to solve (6) or can I solve (5)? I.e., will the branch-and-bound techniques apply to and be quick enough to handle (5)? $\endgroup$ Sep 22 '20 at 4:55
  • $\begingroup$ Also, if the quadratic form had $46$ variables instead of $44$, how long do you think it would take for a state-of-the-art solver to solve the resulting mixed-integer linear program? Thanks! $\endgroup$ Sep 22 '20 at 4:59
  • $\begingroup$ @mathworker21 Equation (5) contains a nonlinear constraint $x^T \lambda = 0$ (because neither $x$ nor $\lambda$ is a constant), so it's not a MILP. Equation (6) has purely linear constraints and objective, so it's in the correct form for you to input it into a MILP solver. $\endgroup$ Sep 22 '20 at 9:00
  • $\begingroup$ Thank you! May you please address my second comment when you get a chance? It's my last question to you. $\endgroup$ Sep 22 '20 at 12:25
  • $\begingroup$ I'm afraid I can't answer the comment [about the 46-variable quadratic form]: the runtime will depend on both the quadratic form itself (not just the number of variables) and the solver you're using, so the best way to answer that question is to experiment yourself. $\endgroup$ Sep 22 '20 at 22:41
2
+50
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I'm asking about copositivity. As I already said in the comments, my quadratic form is sometimes negative (if some of the variables are). $\endgroup$ Sep 21 '20 at 12:55
  • 1
    $\begingroup$ Oh, I see my answer was confusing; I've tried to edit it for clarity. Does it make sense now? $\endgroup$ Sep 21 '20 at 19:42
  • $\begingroup$ Oh, I'm just stupid. I understand now. I'll think more and get back to you. Thank you for your input. $\endgroup$ Sep 21 '20 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.