Random Linkage: A family of acceptance/rejection algorithms for global optimisation

This paper introduces a new, infinite, class of stochastic algorithms for the optimization of multi-modal functions defined over a compact set. The main idea is that of generalizing some well known methods inspired by clustering techniques which make use of local search routines started at selected points in a random sample. It is shown that there exist interesting classes of global optimization algorithms all possessing the following theoretical properties: convergence to the global optimum with probability (w.p.) 1; detection of the global optimum in a finite number of interations w.p.1; probability of starting a local search decreasing to 0; total number of local searches performed even if the algorithm is run forever, finite w.p.1.