> 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
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:
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/10556780410001654...
[1] http://epubs.siam.org/doi/abs/10.1137/S1052623403429081
[2] http://epubs.siam.org/doi/abs/10.1137/040621065
[4] https://www.artelys.com/tools/knitro_doc/2_userGuide/complem...