Global Optimization

Both deterministic algorithms like Newton's method and stochastic ones like simulated annealing can converge very slowly to a global extremum or become trapped at a local one with high probability. By restarting the algorithm properly, one can be assured that the probability the goal has not been attained by the nth iteration converges to 0 geometrically fast. The Perron-Frobenius theory of non-negative matrices or generalizations are used to prove this. In Restarting Search Algorithms with Applications to Simulated Annealing the authors study the case of simulated annealing. In both the deterministic and stochastic cases, parallelization leads to more rapid convergence. In Estimating the convergence rate of a restarted search process. real-time estimation of crucial parameters to determine the number of processors to add in order to achieve high probability of attaining the goal by a given time is studied.