Timeline for Can all convex optimization problems be solved in polynomial time using interior-point algorithms?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 5, 2012 at 19:44 | vote | accept | Optimizationguy | ||
| Apr 5, 2012 at 19:44 | |||||
| Apr 3, 2012 at 5:03 | comment | added | Brian Borchers | Yes, although in most practical situations where you're formulating some problem as an SDP, you can ensure that Slater's condition holds. | |
| Apr 3, 2012 at 3:58 | comment | added | Dima Pasechnik | even SDPs, however, cannot be solved in polynomial time, or at least no algorithms like this are known. See my answer below. | |
| Apr 3, 2012 at 1:33 | history | answered | Brian Borchers | CC BY-SA 3.0 |