Good that you are after continuous space :-). There are many different definitions for convergence that I can categorize into two main groups:

1) convergence to a point

2) convergence to an optimum

For 1 (also known as stability analysis) you may have first order or second order stability (or nth order).  You need to note that such convergence has nothing to do with the quality of the solutions at the end of the run. It ONLY talks about a sequence that will end up inside the search space rather than going to infinity. The idea is: is there any guarantee that the sequence of the generated solutions by the algorithm converges to a single point, i.e., the generated sequence is not divergent. You can find such studies in PSO very frequently (see Clerk paper or Poli, or myself for SPSO2011). There are many types of such convergence: first order, second order, etc. First order tells you if the geneated sequence converges in expectation. Meaning that if I run the algorithm for infinite number of steps, does the average of the positions of the generated points converge. You need to note that this is not enough to guarantee that the positions generated end up inside the search space. However, second order stability guarantee that the varaince (rather than the expected value) of the generated solutions is also zero, meaning that positions converge to a point inside the search space AND do not move.

For 2, you are after a proof that the generated solution WILL converge to a local optimum (or global optimum) eventually (note the difference with 1, where no assumption was made for the quality of the solution). This also may have many different types, but one frequently used is convergence in probaility (or almost surely, or asymptotically). The idea is: the generated solutions will be arbitrarily close to a local optimum when time goes to infinity, See my paper on "a locally convergent rotationaly invariant PSO". You can find a proper proof for a varaint of PSO that does such a thing. Note that there are metaheuristic methods that DO guarantee local convergence.

I have also put a small discussion on wikipedia some time ago that might be of your interest: http://en.wikipedia.org/wiki/Particle_swarm_optimization. See also: http://en.wikipedia.org/wiki/Convergence_of_random_variables. Note that all of these methods you mentioned actually generate random positions with some distribusion that is adapted by the algorithm. Hence, you can see the sequence as a random variable and study its convergence properties from that point of view. I hope this help.

Note that such proofs are completely invariant from the landscape menaing that if you prove that a PSO variant converges to a local optimum, it means for ANY land scape it does it.

Note also that local optimum is a good point, unlike what is assumed in most experimental litrature, in theoretical studies a local optimum is very important to be hit. There is another topic that might be of your interest that is called first hitting time. Search for it for PSO again and you will find a couple of papers about it (it is not that well established yet, but it is very interesting and related to convergence).

Hi Antonio,

By definition an heuristic algorithm (genetic algorithms, evolutionary programming, ant algorithm, etc) never guaranties its convergence to the best and unique solution (if any) nor the best solution. It only gives you one solution (probably a good one). That's it. Why ? Because it does not requires that the search space is differentiable such as gradient methods (or newton methods) which provide you the exact solution.

Cheers, Patrick.

One idea that you might consider is that some models while not exactly solved to optimality have tight, good (cheap to compute?) lower bounds. With that you could compute the gap between your incumbent (best feasible solution = upper bound; UB) and the lower bound (LB);  assuming we are working with a problem in the minimization sense. At least that way you know that the optimal solution is somewhere between the UB and LB.

I think this is a different issue from the fact that a greedy heuristic will get the optimal answer for certain special problems (e.g. minimum weight spanning tree; see Nemhauser and Wolsey).

If you do not have a special problem, and do not have a lower bound, I feel that there are no guarantees. (This is an edited form of my earlier answer, which was a bit too sweeping.)

This is a good question with more than one  possible answer.

Convergence for a metaheurstic algorithm is considered in

W.J. Gutjar, A generalized convergence result for the graph-based ant system metaheuristic, University of Vienna:

https://homepage.univie.ac.at/walter.gutjahr/papers/antsPeisFinal.pdf

For a good discussion of convergence a Graph-Based Ant System, see Section 1, starting on page 2.   A proof that the Graph-Based Ant System algorithm holds with relaxed conditions is given in Section 3, starting on page 6.

If you relax your approaches from the ones you have listed, local search (sometimes referred to in some contexts as a meta-heuristic technique, I would just call it an algorithmic technique) sometimes allows you to prove convergence depending on your problem.  It's often by indirect proof using a potential function.  Sometimes you're lucky with your problem and can use this technique to provide an approximation algorithm as oppose to something less specific that isn't guaranteed to terminate in polynomial time.  I will remind that we talk about algorithms with respective to a problem, not the other way around, so it's a very bold statement to claim a certain kind of algorithm can never converge to an optimal solution, but that's aside the point.  

I recommend looking at Chapter 9 of "The Design of Approximation Algorithms" by Williamson and Shmoys.  Some problems they consider using local search (that end up being greedy algorithms effectively) are:

-Uncapacitated Facility Location Problem

-k-Median Problem

-Minimum-Degree Spanning Trees

Observe that these three problems do have some special properties that allow this to work.  Not every problem will be able to provide such guarantees, but some can (such as these).

Convergence by techniques like this is very much dependent on the problem in question.  I'd personally not say that no technique of the kind can guarantee convergence as there are infinitely many problems out there to be solved or to be solved.  I agree that some of the techniques you posed for many problems will not guarantee an optimal solution (if the problem lacks any structural properties we can use to prove it does), but it doesn't imply that none of them can.  It will depend greatly on the problem at hand.  If you give a very trivial problem to solve, you can probably guarantee convergence with several meta-heuristic techniques.  But I see what others are saying as we normally use these techniques on problems that often lack structural properties that algorithms can exploit.

@Humyun:  I think you mean "No free lunch", not "No free launch".

Hi Antonio,

In general, you cannot prove the convergence of a metaheuristic independently of the problem at hand. But as Mr. Page explained, the structural properties of some "easy" problems could allow you to do so. I don't know if you can be as lucky with the "difficult" problems, though.

The only proof of convergence I'm aware of is that of Aarts, Korst and Laarhoven (1997) for the simulated annealing. They proved that under some specific cooling schedules, the algorithm converges in probability towards a global optimal solution when the number of iterations tends towards infinity.

You should also take a look at the following article :

-A. Dekkers, E. Aarts. Global optimization and simulated annealing. Mathematical Programming, March 1991, Volume 50, Issue 1-3, pp 367-393.

I hope this helped.

Best regards,

Imène.

Good that you are after continuous space :-). There are many different definitions for convergence that I can categorize into two main groups:

1) convergence to a point

2) convergence to an optimum

For 1 (also known as stability analysis) you may have first order or second order stability (or nth order).  You need to note that such convergence has nothing to do with the quality of the solutions at the end of the run. It ONLY talks about a sequence that will end up inside the search space rather than going to infinity. The idea is: is there any guarantee that the sequence of the generated solutions by the algorithm converges to a single point, i.e., the generated sequence is not divergent. You can find such studies in PSO very frequently (see Clerk paper or Poli, or myself for SPSO2011). There are many types of such convergence: first order, second order, etc. First order tells you if the geneated sequence converges in expectation. Meaning that if I run the algorithm for infinite number of steps, does the average of the positions of the generated points converge. You need to note that this is not enough to guarantee that the positions generated end up inside the search space. However, second order stability guarantee that the varaince (rather than the expected value) of the generated solutions is also zero, meaning that positions converge to a point inside the search space AND do not move.

For 2, you are after a proof that the generated solution WILL converge to a local optimum (or global optimum) eventually (note the difference with 1, where no assumption was made for the quality of the solution). This also may have many different types, but one frequently used is convergence in probaility (or almost surely, or asymptotically). The idea is: the generated solutions will be arbitrarily close to a local optimum when time goes to infinity, See my paper on "a locally convergent rotationaly invariant PSO". You can find a proper proof for a varaint of PSO that does such a thing. Note that there are metaheuristic methods that DO guarantee local convergence.

I have also put a small discussion on wikipedia some time ago that might be of your interest: http://en.wikipedia.org/wiki/Particle_swarm_optimization. See also: http://en.wikipedia.org/wiki/Convergence_of_random_variables. Note that all of these methods you mentioned actually generate random positions with some distribusion that is adapted by the algorithm. Hence, you can see the sequence as a random variable and study its convergence properties from that point of view. I hope this help.

Note that such proofs are completely invariant from the landscape menaing that if you prove that a PSO variant converges to a local optimum, it means for ANY land scape it does it.

Note also that local optimum is a good point, unlike what is assumed in most experimental litrature, in theoretical studies a local optimum is very important to be hit. There is another topic that might be of your interest that is called first hitting time. Search for it for PSO again and you will find a couple of papers about it (it is not that well established yet, but it is very interesting and related to convergence).

Dear Antonio,

Meta heuristics are based on systematic progression of random evolution. And it has no mathematical proof. Hence, its convergence can not prove. However, it can be measure in terms of best, average and standard deviation. 

Such comparison can judge effectiveness of  Meta heuristics.

Thanks for this wonderful Q.

Hi Antonio

I think this is a very hard task due to the inherent non-determinism (or randomness if you want) of the metaheuristics.

Regards

Salim

what is the difference between convergence in metaheuristic and exact algorithm?

Short answer:  I'm afraid, you can't really talk about any formal notion of convergence in the case of meta-heuristics. For meta-heuristics are empirical by construction. If you're worried about convergence, then you should quit meta-heuristics in favor of more formal optimization techniques (e.g convex optimization). However you might need to relax your problem for it to become amenable to such formal methods. No free launch!