I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX.

In trying to answer this question, I realized that I don't know enough about optimization theory to answer a more general question: Just how interchangeable are heuristic approaches for solving computationally hard optimization problems?

Coming from an ML background, I'm reasoning by analogy with supervised learning problems: In ML, some methods like Neural Networks (with a sufficient number of layers) or Support Vector Machines are universal, in that they can approximate any shape decision boundary or regression function up to an arbitrary level of precision.

Are there equivalent algorithms in optimization theory that can be used to solve any optimization problem (linear, non-linear, continuous, discrete, etc...), e.g. can Genetic Algorithms or Particle Swarm Optimization be thrown at any optimization problem and give us a reasonable solution? SGD is used to solve NP-Complete problems (i.e. training a neural network) - does that mean that it can be used for any optimization problem?

I assume that the reverse is true: Not all optimization are universal, for example methods that work for LP or QP don't necessarily work for harder problems.

If it is indeed the case that some optimization algorithms are universal, is Bayesian Optimization one of these universal algorithms? Can be used to approach LP, QP, MIP, TSP, and NP-Hard problems in general?

  • $\begingroup$ What do you mean by "solve" ? Find an optimal solution within reasonable time? Find a reasonable solution within reasonable time? Find an optimal solution within any time at all? Also, there is no algorithm for solving (for almost all meanings of "solve") all NP-hard problems, as this class includes problems that are undecidable. Maybe you want to consider NP-complete problems instead? $\endgroup$ – Discrete lizard Sep 1 '19 at 20:43
  • $\begingroup$ @Discretelizard I meant "Find a reasonable solution within reasonable time" - for average case real world problems. I understand that some NP-hard problems will be difficult to solve, but assume there is an average case complexity consideration that makes some algorithms generally applicable? $\endgroup$ – Sasha the Noob Sep 2 '19 at 0:05
  • $\begingroup$ Ok, then I think I see what you mean by "solve". The problem with considering all NP-hard problems is that the Halting problem is an NP-hard problem. Under standard assumptions on the capabilities of computers, there cannot exists an algorithm that gives valid solution to the Halting problem, no matter how much time or resources it has (this is what it means for a problem to be undecidable ). $\endgroup$ – Discrete lizard Sep 2 '19 at 8:01
  • $\begingroup$ Deep networks are not a panacea. Consider for example navigation apps like Google maps or Waze. They use dedicated shortest path algorithms. Similarly, SAT solvers use dedicated algorithms. The advantage of general-purpose algorithms is that they might work even if a special-purpose algorithm doesn't exist. $\endgroup$ – Yuval Filmus Sep 2 '19 at 10:21
  • $\begingroup$ In the discrete and bounded setting, exhaustive search is guaranteed to find the best solution. In this sense, universal algorithms do exist, but they are typically not very useful. Deep learning is a heuristic which works well on some problems, and not as well on others. $\endgroup$ – Yuval Filmus Sep 2 '19 at 10:23

There is no heuristic that is "universal" in practice. Which heuristic works best in practice often depends on the specific problem you're dealing with. There's no one "silver bullet" heuristic that works great on every optimization problem.

  • $\begingroup$ Isn't all NP-hard problems reducible to non-linear programming? I know that a lot of NP-hard problems are reducible to integer linear programming; I remember even reading that the simplex algorithm (which I know, it's for LP, not ILP), was called NP-mighty or something like that, meaning that any NP-complete problem instance belongs to the lineal programming problem, and it's solvable using the simplex algorithm; I don't know at which extent a similar affirmation can be stated about NP-hard problems though. $\endgroup$ – Peregring-lk Jan 11 at 13:18
  • $\begingroup$ @Peregring-lk, No. All NP-complete problems are reducible to integer linear programming, but that's not a very useful statement, as the same is true if you replace ILP with any other NP-complete problem. The simplex algorithm is not a state-of-the-art method for ILP. None of this changes my statements in my answer. $\endgroup$ – D.W. Jan 11 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.