Timeline for Is there a class of optimization problems more general than semidefinite programming?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 25, 2016 at 7:28 | comment | added | Dima Pasechnik | speaking about complexity, for SDPs in general is it not known, and so one has to tread carefully here. | |
| Feb 25, 2016 at 3:39 | comment | added | Noah Stein | Interesting, I hadn't realized the two-variable case was tractable. I was referring to e.g. the fact that for the degree four case with $n$ variables, checking membership in the cone of nonnegative polynomials is NP-hard. | |
| Feb 24, 2016 at 20:14 | comment | added | Dima Pasechnik | well, it what sense are they intractable? E.g. if you fix the number of variables, things are not as bad (e.g. for 2 variables things can be done in polynomial time, as we showed long time ago; dx.doi.org/10.1016/j.ejor.2003.08.014) | |
| Feb 23, 2016 at 19:31 | comment | added | Noah Stein | Ok, well cones of nonnegative polynomials are more general than SDP cones, but unfortunately computationally intractable. | |
| Feb 23, 2016 at 10:23 | history | edited | Dima Pasechnik | CC BY-SA 3.0 |
generalised more...
|
| Feb 23, 2016 at 10:21 | comment | added | Dima Pasechnik | OK, it's not quite true what I just wrote. I meant cones of nonnegative polynomials. | |
| Feb 23, 2016 at 10:20 | comment | added | Dima Pasechnik | this is only true asymptotically --- and then, you know, every nice function on a compact is asymptotically a polynomial, so why bother :-) | |
| Feb 22, 2016 at 22:55 | comment | added | Noah Stein | But you can rewrite these sum of squares cones as projections of appropriate linear sections of larger positive semidefinite cones, so from a strict representability perspective you don't get anything new here. | |
| Feb 22, 2016 at 21:54 | history | answered | Dima Pasechnik | CC BY-SA 3.0 |