Timeline for Determining if a quadratic form is non-negative if variables are non-negative
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 23, 2020 at 2:01 | comment | added | mathworker21 | Maybe I should clarify that I just seek an upper bound. I can tell you that the coefficients of the quadratic form are integers between $0$ and $10$. Is the runtime at most one year on a standard computer? Is it at most $10$ hours? How about on a super computer? If you say it might be a couple of years, then of course I cannot just "experiment myself"... | |
| Sep 22, 2020 at 22:41 | comment | added | Adam P. Goucher | 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. | |
| Sep 22, 2020 at 12:25 | comment | added | mathworker21 | Thank you! May you please address my second comment when you get a chance? It's my last question to you. | |
| Sep 22, 2020 at 9:00 | comment | added | Adam P. Goucher | @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. | |
| Sep 22, 2020 at 4:59 | comment | added | mathworker21 | 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! | |
| Sep 22, 2020 at 4:55 | comment | added | mathworker21 | 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)? | |
| Sep 21, 2020 at 12:18 | history | answered | Adam P. Goucher | CC BY-SA 4.0 |