Optimal Restart Strategies for Parameter-dependent Optimization Algorithms

This paper examines restart strategies for algorithms whose successful termination depends on a parameter λ. After each restart, λ is increased, until the algorithm terminates successfully. It is assumed that there is an unknown, optimal value for λ. For the algorithm to run successfully, this value must be surpassed. The key question is whether there exists an optimal strategy for selecting λ after each restart taking into account that the computational costs increase with λ. Potential restart strategies are classified into parameter-dependent strategy types. A loss function is introduced to quantify the wasted computational cost relative to the optimal strategy. A crucial requirement for any efficient restart strategy is that its loss, relative to the optimal λ, remains bounded. To this end, upper and lower bounds of the loss are derived. Using these bounds it will be shown that not all strategy types are bounded. However, for a particular strategy type, where λ is increased multiplicatively by a constant factor ρ, the relative loss function is bounded. Furthermore, it will be demonstrated that within this strategy type, there exists an optimal value ρ = 2 that minimizes the maximum relative loss. In the asymptotic limit, this optimal choice does not depend on the unknown optimal A. While the multiplicative strategy with ρ = 2 was already used in implementations of evolutionary algorithms to control the population size showing acceptable performance in applications, a formal proof of its optimality is presented and the underlying conditions are discussed in this paper the first time.