English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

This paper investigates the intractability of large-scale optimization withmulti-start methods. For the theoretical performance analysis, we focus onrandom multi-start (RMS), which is one of the representative multi-startmethods, including RMS local search and greedy randomized adaptive searchprocedure (GRASP). Our primary theoretical contribution is to derive, by usingextreme value theory, power-law formulas for the two quantities: (i) theexpected improvement rate of the best empirical objective value (EOV); (ii) theexpected relative gap between the best EOV and the supremum of the EOVs.Notably, the expected relative gap exhibits scale-freeness as a function of thenumber of iterations. Consequently, the half-life of the expected relative gapis asymptotically proportional to the number of iterations executed by the RMSmethod. This result can be interpreted as the curse of scale-freeness -- aZeno's paradox-like phenomenon -- expressed by the metaphor "Reaching for thegoal makes it slip away." Through numerical experiments, we observe thatseveral RMS algorithms applied to traveling salesman problems suffer from thecurse of scale-freeness. Furthermore, we show that overcoming this curserequires a powerful local search algorithm with effective restart anddiversification strategies that exponentially accelerate solution improvementrelative to the RMS method.

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