On the Convergence of Statistical Search
Luc Devroye · IEEE Transactions on Systems Man and Cybernetics · 1976
The convergence of statistical (random) search for the minimization of an arbitrary multimodal functional Q(w) is dealt with by using the theorems of convergence of random processes of Braverman and Rozonoer. It is shown that random search can be regarded as a gradient algorithm in the Q-domain. Using this gradient to define the minimum of the functional, the convergence to this minimum is discussed at length. The theorems proved in this paper apply as well to discrete as to continuous optimization problems and as such, the developed technique is competitive with stochastic automata with a variable structure. The optimality of the scheme follows from the convergence in probability of the average performance to the minimum. The freedom in the organization of the search within the boundaries outlined by the conditions of convergence is emphasized. Finally, it is pointed out how various mixed random search and hierarchical search systems fall into the domain of application of the theorems.