论文标题
规模繁琐的诅咒：通过多开始方法的大规模优化的顽固性
Curse of scale-freeness: Intractability of large-scale optimization with multi-start methods
论文作者
论文摘要
本文通过多启动方法研究了大规模优化的可行性。对于理论性能分析，我们关注随机多启动（RMS），这是代表性的多开始方法之一，包括RMS本地搜索和贪婪的随机自适应搜索程序（GRASP）。我们的主要理论贡献是通过使用极值理论，对两个量的幂律公式得出：（i）最佳经验目标价值的预期提高率（EOV）； （ii）最佳EOV与EOV至上的预期相对差距。值得注意的是，预期的相对差距表现出比迭代次数的函数表现出尺度繁琐。因此，预期相对差距的半衰期与RMS方法执行的迭代次数渐近成正比。该结果可以解释为尺寸柔性的诅咒 - Zeno的悖论般的现象 - 由隐喻“达到目标使其滑倒”表示。通过数值实验，我们观察到适用于旅行推销员问题的几种RMS算法遭受了规模繁琐的诅咒。此外，我们表明，克服这一诅咒需要具有有效重新启动和多元化策略的强大本地搜索算法，该策略与RMS方法相对于RMS方法呈指数级加速。
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.
