4 ms·

I'm also curious what this adds that's new. I'll add one other bit: If anyone ever claims they have an efficient global optimization algorithm for continuous

• yorwba 9y ago
  Not all continuous optimization algorithms can handle arbitrary equality constraints, especially if they effectively make the optimization domain discrete. You might be able to do an encoding of NP-complete problems that is purely continuous, but if I read the LIPO paper correctly, there is a known exponential lower bound for their problem, so that would just make the NP-complete problem harder. Instead, the algorithm promises to actually match that lower bound, while always being at least as good as random search, and offering exponentially large improvements in certain cases. Not exactly the kind of claim that has implications for P =? NP.
• deleted 9y ago
  [deleted]
• tobmlt 9y ago
  Interval Newton is probably my favorite algorithm. Intervals in concert with the fixed point theorems - amazing stuff. (and all the rest! - contractors, inclusion/exclusion tests exploiting derivative info, etc.) Good tools for optimization, indeed.
• wenc 9y ago
  > If anyone ever claims they have an efficient global optimization algorithm for continuous optimization, ask whether or not P=NP Why? Continuous global optimization on convex problems can be solved in polynomial time. Did you mean on nonconvex problems? Also, x*(x-1)=0 is a complementarity constraint and it is mathematically degenerate (it violates constraint qualifications) when solved as a continuous optimization problem. There are many ways to work-around it [0, 1, 2] and even solvers built for this of problems (MPECs = Mathematical Programs with Equilibrium Constraints) which I suspect only work well for narrow classes of problems like Linear Complementarity Problem (LCPs). I have found that ultimately for nonlinear non-convex problems, the solution technique for continuous optimization of complementarity constraint problems has been empirically unreliable or the solution is often low equality (even if it can be shown that the complementarity penalty method does not violate constraint qualifications). Bilinear constraints generally add nonconvexities and add a lot of difficult terrain for a continuous optimizer. For general nonconvex problems, it's much more reliable to cast the problem as an NP-hard MINLP. And if you're solving an LCP, you might as well recast it as an MIP rather than mucking around with an LCP. MIP solvers like Gurobi and CPLEX are so amazingly performant these days that it's just a no-brainer [0] http://www.tandfonline.com/doi/abs/10.1080/10556780410001654241 http://www.tandfonline.com/doi/abs/10.1080/10556780410001654... [1] http://epubs.siam.org/doi/abs/10.1137/S1052623403429081 http://epubs.siam.org/doi/abs/10.1137/S1052623403429081 [2] http://epubs.siam.org/doi/abs/10.1137/040621065 http://epubs.siam.org/doi/abs/10.1137/040621065 [4] https://www.artelys.com/tools/knitro_doc/2_userGuide/complementarity.html https://www.artelys.com/tools/knitro_doc/2_userGuide/complem...
  • 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 ago
      You are correct. SDPs are a clear counterexample.