Efficient Multi-Start Strategies for Local Search Algorithms
  Local search algorithms applied to optimization problems often suffer from
getting trapped in a local optimum. The common solution for this deficiency is
to restart the algorithm when no progress is observed. Alternatively, one can
start multiple instances of a local search algorithm, and allocate
computational resources (in particular, processing time) to the instances
depending on their behavior. Hence, a multi-start strategy has to decide
(dynamically) when to allocate additional resources to a particular instance
and when to start new instances. In this paper we propose multi-start
strategies motivated by works on multi-armed bandit problems and Lipschitz
optimization with an unknown constant. The strategies continuously estimate the
potential performance of each algorithm instance by supposing a convergence
rate of the local search algorithm up to an unknown constant, and in every
phase allocate resources to those instances that could converge to the optimum
for a particular range of the constant. Asymptotic bounds are given on the
performance of the strategies. In particular, we prove that at most a quadratic
increase in the number of times the target function is evaluated is needed to
achieve the performance of a local search algorithm started from the attraction
region of the optimum. Experiments are provided using SPSA (Simultaneous
Perturbation Stochastic Approximation) and k-means as local search algorithms,
and the results indicate that the proposed strategies work well in practice,
and, in all cases studied, need only logarithmically more evaluations of the
target function as opposed to the theoretically suggested quadratic increase.
