Escaping Local Minima: A Finite-Time Markov Chain Analysis of Constant-Temperature Simulated Annealing

摘要

Simulated Annealing (SA) is a widely used stochastic optimization algorithm, yet much of its theoretical understanding is limited to asymptotic convergence guarantees or general spectral bounds. In this paper, we develop a finite-time analytical framework for constant-temperature SA by studying a piecewise linear cost function that permits exact characterization. We model SA as a discrete-state Markov chain and first derive a closed-form expression for the expected time to escape a single linear basin in a one-dimensional landscape. We show that this expression also accurately predicts the behavior of continuous-state searches up to a constant scaling factor, which we analyze empirically and explain via variance matching, demonstrating convergence to a factor of sqrt(3) in certain regimes. We then extend the analysis to a two-basin landscape containing a local and a global optimum, obtaining exact expressions for the expected time to reach the global optimum starting from the local optimum, as a function of basin geometry, neighborhood radius, and temperature. Finally, we demonstrate how the predicted basin escape time can be used to guide the design of a simple two-temperature switching strategy.