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.

Improve this question
$\endgroup$
5
  • $\begingroup$ will not diagonaliztion of symmetric matrices algorithm work here? $\endgroup$
    – vidyarthi
    Commented Sep 19, 2020 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$
    – mathworker21
    Commented Sep 19, 2020 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$
    – Steven Stadnicki
    Commented Sep 19, 2020 at 5:56
  • 3
    $\begingroup$ You want to test whether a matrix is "copositive". $\endgroup$
    – Harry West
    Commented Sep 21, 2020 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
    Commented Sep 21, 2020 at 8:25

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – mathworker21
    Commented Sep 22, 2020 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$
    – mathworker21
    Commented Sep 22, 2020 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$
    – Adam P. Goucher
    Commented Sep 22, 2020 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$
    – mathworker21
    Commented Sep 22, 2020 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$
    – Adam P. Goucher
    Commented Sep 22, 2020 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.

Improve this answer
$\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$
    – mathworker21
    Commented Sep 21, 2020 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$
    – Bill Bradley
    Commented Sep 21, 2020 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$
    – mathworker21
    Commented Sep 21, 2020 at 20:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .