= Five-state barrier example for simulated annealing
Consider the chosen finite <minimization problem>
$$
F=\{0,1,2,3,4\},\qquad (E(0),E(1),E(2),E(3),E(4))=(2,1,4,2,0).
$$
Only adjacent <integers> are neighbors. At each interior state propose left or right with <probability> $1/2$ each; at an endpoint propose its sole neighbor with <probability> $1/2$ and itself with <probability> $1/2$. This <proposal distribution> is symmetric, including at the endpoints. The <local minimum> at $1$ is relative to these allowed moves; $4$ is the unique <global minimum>.
\Image[/simulated-annealing-five-state-barrier.png]
{title=An uphill step opens a route out of a local minimum in a chosen five-state problem}
{description=Points are the only allowed states; joining lines show adjacency, not additional <feasible points>. Starting at $1$, improving-only <local search> is trapped. The possible route $1\to2\to3\to4$ first raises the <objective function> by $3$, then lowers it twice.}
At $1$, improving-only <local search> rejects both neighbors because $E(0)=2$ and $E(2)=4$ exceed $E(1)=1$. For <simulated annealing>, choose $T_*=1/\ln2$, using the <natural logarithm>. Conditional on proposing $2$ from $1$, the acceptance <probability> is
$$
a_{T_*}(1,2)=e^{-3/T_*}=\frac18.
$$
The one-step <transition probability> is instead $P_{T_*}(1,2)=(1/2)(1/8)=1/16$. Both subsequent rightward proposals are downhill, so the <conditional probability> of the precise next three states being $2,3,4$, given $X_0=1$ and fixed $T_*$, is
$$
\Pr(X_1=2,X_2=3,X_3=4\mid X_0=1)
=\frac1{16}\frac12\frac12=\frac1{64}.
$$
This is one possible escape route, not the <probability> of eventually reaching $4$. Rejections, excursions toward $0$, and repeated attempts give many other <sample paths>. The calculation establishes possibility, without claiming a general performance advantage from a selected <sample path>.
For comparison, halving $T_*$ makes the uphill acceptance <probability> $1/64$; doubling it makes that <probability> $1/(2\sqrt2)$. Cooling makes it harder to leave this <local minimum>, even though the <stationary distribution> increasingly favors the <global minimum>. That tension is the central scheduling problem.
Back to article page
