Curse of scale-freeness: Intractability of large-scale optimization with multi-start methods

Abstract This paper investigates the intractability of large-scale optimization with multi-start methods. For the theoretical performance analysis, we focus on random multi-start (RMS), which is one of the representative multi-start methods, including RMS local search and greedy randomized adaptive search procedure (GRASP). Our primary theoretical contribution is to derive, by using extreme value theory, power-law formulas for the two quantities: (i) the expected improvement rate of the best empirical objective value (EOV); (ii) the expected relative gap between the best EOV and the supremum of the EOVs. Notably, the expected relative gap exhibits scale-freeness as a function of the number of iterations. Consequently, the half-life of the expected relative gap is asymptotically proportional to the number of iterations executed by the RMS method. This result can be interpreted as the curse of scale-freeness —a Zeno’s paradox-like phenomenon—expressed by the metaphor “ Reaching for the goal makes it slip away. ” Through numerical experiments, we observe that several RMS algorithms applied to traveling salesman problems suffer from the curse of scale-freeness. Furthermore, we show that overcoming this curse requires a powerful local search algorithm with effective restart and diversification strategies that exponentially accelerate solution improvement relative to the RMS method.