A theoretical approach to restart in global optimization

While searching for the global minimum of a cost function we have often to decide if a restart from a different initial point would be more advantageous than continuing current optimization. This is a particular case of the efficiency comparison between repeated minimizations and single extended search having the same total length. A theoretical approach for the treatment of this general problem forms the subject of the present paper. A fundamental role is played by the probability of reaching the global minimum, whose asymptotical behavior allows to provide useful information on the efficiency of repeated trials. The second part of this work is devoted to a detailed analysis of three optimization algorithms whose evolution is independent of the cost function to be minimized: pure random search, grid search and random walk. These three examples give an interesting validation of the theoretical results and provide a general procedure which can be employed in the study of more complex optimization problems.