4 ms·
Oh I very much agree that good MIP solvers work well for complementary problems. And, I suppose my point about P=NP was that if we had a general scalable globa
by kxyvr 9y ago
Oh I very much agree that good MIP solvers work well for complementary problems. And, I suppose my point about P=NP was that if we had a general scalable global optimization solver, then it would have all sorts of implications outside of continuous optimization. I didn't qualify convex vs nonconvex and, of course, many convex problems can be solved in polynomial time. Though, funny enough, not all. De Klerk and Pasechnik have a paper,"Approximation of the stability number of a graph via copositive programming," where they prove that NP hard problems can be encoded as convex problems. Pasechnik has a nice explanation here:
https://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-ti https://mathoverflow.net/questions/92939/is-that-true-all-th...
- wenc 9y agoYou are correct. SDPs are a clear counterexample.