Random Restarts in Global Optimization

Abstract

In this article we study stochastic multistart methods for global optimization, which combine local search with random initialization, and their parallel implementations. It is shown that in a minimax sense the optimal restart distribution is uniform. We further establish the rate of decrease of the ensemble probability that the global minimum has not been found by the nth iteration. Turning to parallelization issues, we show that under independent identical processing (iip), exponential speedup in the time to hit the goal bin normally results. Our numerical studies are in close agreement with these finndings.