The Impact of Move Schemes on Simulated Annealing Performance

Ruichen Xu, Haofan Wang, Yuefan DengarXiv 2025 · DOI · arXiv

TL;DR

In high-dimensional optimization, "less is more" when it comes to perturbing your variables. This paper demonstrates that updating only a small subset of coordinates—ideally just one—per iteration in Simulated Annealing (SA) leads to higher acceptance rates, faster mixing, and significantly better convergence compared to moving all variables at once.

What Problem Does This Paper Address?

Simulated Annealing (SA) is a powerhouse for solving complex, non-convex optimization problems, but its performance hinges on a "black box" component: the move-generation function. When the algorithm proposes a new state, it faces a fundamental trade-off. If the move is too large, it is almost always rejected; if it is too small, the algorithm crawls through the search space and gets stuck in local minima.

This challenge is amplified in high-dimensional spaces. As the number of variables ($N$) increases, the probability that a simultaneous change to all variables results in a "better" (or even acceptable) state drops precipitously. The authors seek to move beyond trial-and-error by providing a theoretical and empirical framework for how to allocate "proposal variance"—essentially, deciding whether to spread your "movement budget" across all coordinates or concentrate it on a few.

Methods

The researchers recast SA as a Markov Chain Monte Carlo (MCMC) process operating at varying temperatures. Their approach combines rigorous math with numerical experiments:

  • Theoretical Analysis: They use second-order Taylor expansions and Edgeworth expansions to analyze the log-acceptance ratio ($Z$). By calculating the first three cumulants (mean, variance, and skewness) of the acceptance probability, they quantify how the number of updated coordinates ($d$) affects the likelihood of a move being accepted.
  • Variance Allocation: They compare "full-coordinate" moves (updating all $N$ variables) against "partial-coordinate" moves (updating $d < N$ variables) while keeping the total proposal variance ($\sigma^2_{total}$) fixed.
  • Algorithmic Comparison: They implemented standard Metropolis-Hastings within an SA framework, testing various "move schemes" where $d$ ranges from 1 to the full dimensionality of the problem.

Datasets

The authors evaluated their move schemes on three classic optimization benchmarks that represent different types of "difficulty":

  1. Lennard-Jones (L-J) Potential: A molecular physics problem used to find the minimum energy configuration of $N$ particles. It is highly coupled and notorious for having a massive number of local minima.
  2. Rosenbrock Function: The classic "banana function." It features a very narrow, curved valley where the global minimum resides, making it a standard test for an algorithm's ability to navigate "flat" directions.
  3. Hyper-Elliptic Function: A benchmark used to test how algorithms handle elongated constraints and high-dimensional scaling.

Key Insights and Ideas

  • The Concentration of Variance: The "aha moment" is that spreading a fixed amount of variance across many coordinates is counterproductive. By concentrating that variance into a single coordinate ($d=1$), the algorithm can take a "meaningful" step in that one dimension without triggering a massive energy increase that would lead to a rejection.
  • Acceptance Rate Stability: Partial updates prevent the "acceptance rate collapse" typically seen in high-dimensional SA. When $d$ is small, the acceptance probability remains "sensible" even as the temperature drops, allowing the chain to continue mixing and exploring.
  • Mixing vs. Dimensionality: Mathematically, the authors show that reducing $d$ reduces the second-largest eigenvalue of the Markov operator, which is a direct indicator of faster mixing. In plain English: moving one variable at a time actually helps the whole system reach equilibrium faster than trying to move everything at once.

Key Results

  • The "Rule of One": In the Lennard-Jones experiments (for $N=6, 39, 89$), moving exactly one randomly chosen particle per iteration ($d=1$) consistently yielded the lowest relative error.
  • Error Escalation: As the number of updated coordinates ($d$) increased, the final error increased. For example, in the $N=89$ Lennard-Jones system, the relative error for $d=1$ was roughly 8.2%, while for $d=89$ (full update), it ballooned to over 46% under the same variance settings.
  • Efficiency in High Dimensions: On the Rosenbrock and Hyper-Elliptic benchmarks, partial-coordinate updates significantly outperformed full-coordinate moves, especially as the problem dimensionality grew to $N=200$. The plots show that for large $d$, the acceptance rate drops to near zero much earlier in the cooling process, effectively "freezing" the algorithm in a sub-optimal state.

Limitations and Future Work

While the paper provides a strong case for $d=1$, the authors acknowledge some boundaries:

  • Isotropic Proposals: The study primarily focused on Gaussian increments. Future work could explore non-Gaussian or "heavy-tailed" proposal distributions.
  • Static Subset Selection: The coordinates to be updated were chosen randomly. The authors suggest that "adaptive" subset selection—choosing which coordinates to move based on the local geometry of the function—could further improve performance.
  • Complex Coupling: While L-J is coupled, even more complex molecular or machine learning models might require "blockwise" updates (moving specific groups of related variables) rather than just one at a time.

Summary updated

Abstract

Designing an effective move-generation function for Simulated Annealing (SA) in complex models remains a significant challenge. In this work, we present a combination of theoretical analysis and numerical experiments to examine the impact of various move-generation parameters -- such as how many particles are moved and by what distance at each iteration -- under different temperature schedules and system sizes. Our numerical studies, carried out on both the Lennard-Jones problem and an additional benchmark, reveal that moving exactly one randomly chosen particle per iteration offers the most efficient performance. We analyze acceptance rates, exploration properties, and convergence behavior, providing evidence that partial-coordinate updates can outperform full-coordinate moves in certain high-dimensional settings. These findings offer practical guidelines for optimizing SA methods in a broad range of complex optimization tasks.
BibTeX
@misc{xu2025impact,
  author = {Ruichen Xu and Haofan Wang and Yuefan Deng},
  title = {{The Impact of Move Schemes on Simulated Annealing Performance}},
  year = {2025},
  eprint = {2504.17949},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.17949},
  howpublished = {arXiv},
}
Figure