1
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\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 ♦
    Commented Sep 1, 2019 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
    Commented Sep 2, 2019 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 ♦
    Commented Sep 2, 2019 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
    Commented Sep 2, 2019 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
    Commented Sep 2, 2019 at 10:23

2 Answers 2

Reset to default
2
$\begingroup$

Even if there were, remember that there is no free lunch in search and optimization. An optimization algorithm necessarily trades proficiency in one class of problems for inefficiency in another class of problems. This is related to why the fact that neural networks, SVMs, and even the humble step function are "universal" is of little practical import.

Even within a specific class of optimization problem— say, linear programming— it is well known that a general, off-the-shelf optimizer e.g. Gurobi isn't likely going to do as well as some specialized optimizer tailored to your use case, should one be available (of course, frequently, there isn't one, which is why general purpose optimizers exist).

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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$
    – ABu
    Commented Jan 11, 2021 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. ♦
    Commented Jan 11, 2021 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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