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

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.