= Cooling schedule for simulated annealing
{title2=$T_n>0$}
A <cooling schedule for simulated annealing> specifies successive effective temperatures and how many proposals to attempt at each. For example, $T_k=T_0r^k$ with $0<r<1$, using the <geometric sequence>, can define stages of equal chosen length. Changing $T$ changes the <transition matrix>: if the state <probability distribution> is $\mu_n$, then $\mu_{n+1}=\mu_nP_{T_n}$, which generally differs from $\pi_{T_{n+1}}$. Time spent at one temperature must be compared with its <mixing time> before equilibrium intuition is justified.
In the <five-state barrier example for simulated annealing>, fixed $T_*>0$ gives a finite <irreducible Markov chain>, so $4$ is eventually visited with <probability> one. That unbounded-time statement gives no fixed finite deadline. Over any finite number $N$ of trials starting at $1$, the <probability> of staying at $1$ throughout is
$$
\prod_{n=0}^{N-1}\left[1-\frac12e^{-1/T_n}-\frac12e^{-3/T_n}\right]>0.
$$
Each factor is the rejection <probability> at $1$. This is an explicit failure event even when every $T_n$ is positive: the best visited <objective function> value remains $1$, above the <global minimum> value $0$. More exploratory proposals can help cross a barrier; cooling before those moves occur can preserve a poor <local minimum>. Successful asymptotic schedules need additional analysis of the allowed moves and barriers.
Historically, <Scott Kirkpatrick>, <Charles Daniel Gelatt Jr.> and <Mario P. Vecchi> connected <statistical mechanics> with <mathematical optimization> in 1983. They adapted the <Metropolis–Hastings algorithm> to cooling searches with symmetric proposals and illustrated computer-design problems.<Optimization by Simulated Annealing by Scott Kirkpatrick and others>[Printed pp. 672–673 and 675: Metropolis procedure, cooling schedule, logic partitioning]{ref}
Back to article page
