1
$\begingroup$

Gradient descent sometimes works better than simulated annealing and vice versa.

Are there conditions under which we can prove that, given perhaps a restriction on the set of allowed algorithms, one of these is optimal for solving an optimization problem?

I am particularly interested in those two examples, but in general interested in this question for metaheuristics for search and optimization problems.

(The no free lunch theorems show that (for certain problem statements) this is not possible in general, since for a uniform diatribution on problems, there usually isnt an optimal algorithm. However it might hold for special cases.)

$\endgroup$
1
$\begingroup$

In general, we definitely don't know this. In fact, it's practically always so that a-priori, we don't know how well a particular metaheuristic performs (let alone proving optimality) on a given instance (or family of instances) until we try.

It should also be noted that we usually go for metaheuristics only when the problem is so hard it seems unlikely it admits an algorithm that is always fast and correct (i.e., the problem is NP-hard). Put differently, when a problem is solvable in polynomial-time with some other methods, we don't even bother considering metaheuristics.

So if a metaheuristic is always optimal (and assuming it always runs in polynomial time), then the problem must be in P (assuming that P is not equal to NP). Of course, no one is stopping you from taking a problem that is known to be in P and applying a metaheuristic on that, but that's probably not that useful anymore.

| cite | improve this answer | |
$\endgroup$

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.