Simulated Annealing

Gradient descent and its relatives only ever move downhill, which means on a bumpy non-convex landscape, once they roll into a shallow local dip, they're stuck — there's no downhill move available, even if a much deeper valley sits just beyond a nearby ridge. Simulated annealing takes a deliberately different approach: sometimes accept a step that makes things worse, so the search can climb out of a shallow trap, but make that willingness fade over time so the search still eventually settles down rather than wandering forever.

An analogy: cooling metal into a strong crystal

The method borrows its name and logic from metallurgy. Heat a metal and let it cool slowly, and its atoms have enough thermal energy early on to jostle into many different configurations, occasionally settling briefly into a poor, high-energy arrangement before jostling free of it again — but as the temperature drops, that jostling weakens, and the atoms increasingly can only accept moves that lower their energy, eventually locking into a strong, low-energy crystal lattice. Cool it too fast (quench it) and the atoms get frozen into whatever disordered arrangement they happened to be in — a weak, defect-riddled structure, exactly analogous to gradient descent getting stuck in the first local minimum it meets.

The method, one symbol at a time

At each step, given current point $x$ with objective value $f(x)$, propose a random nearby candidate $x'$. If $f(x') < f(x)$ (a genuine improvement), always accept it. If $f(x') \geq f(x)$ (a worse move), accept it anyway with probability

$$P(\text{accept}) = \exp\!\left( -\frac{f(x') - f(x)}{T} \right),$$

where $T$ is a temperature parameter that starts high and is gradually lowered according to a cooling schedule. In plain English: a slightly worse move is often accepted, but a much worse move is rarely accepted, and the tolerance for worse moves shrinks as $T$ falls — early on the search happily wanders through the landscape (exploration), and late in the process it behaves almost exactly like plain downhill descent (exploitation), because by then $T$ is so small that only genuine improvements have any real chance of being accepted.

Worked example 1: computing acceptance probability by hand

Suppose the search is at a point with $f(x) = 10$, and a proposed move has $f(x') = 12$ — a worsening of $\Delta = 2$. At high temperature $T=5$: $P = \exp(-2/5) = \exp(-0.4) \approx 0.670$, so this worse move is accepted about 67% of the time — the search is still exploring freely. Later, once the schedule has cooled to $T=0.5$: $P = \exp(-2/0.5) = \exp(-4) \approx 0.018$, so the same-sized worsening is now accepted only about 1.8% of the time — the search has become nearly pure downhill descent. The exact same move (same $\Delta$) is treated very differently depending purely on how far along the cooling schedule the search is.

Worked example 2: escaping a local minimum on the two-dip function

Recall $f(x) = x^4 - 5x^2 + 2x$ from non-convex landscapes, with a local minimum near $x\approx -1.66$ (value $\approx -3.62$) and the true global minimum near $x\approx 1.46$ (value $\approx -3.85$). Plain gradient descent from $x_0=-3$ gets stuck at $-1.66$. Simulated annealing starting from the same point, with a moderately high initial temperature, will sometimes accept moves that temporarily raise $f$ — for instance stepping from $x=-1.66$ (value $-3.62$) to $x=0$ (value $0$, much worse, $\Delta=3.62$) has acceptance probability $\exp(-3.62/T)$; at $T=3$ that's $\exp(-1.21)\approx0.30$, a real chance of accepting. Enough such uphill excursions, tried repeatedly across many candidate moves, let the search occasionally cross the local max separating the two dips and discover the deeper global minimum near $1.46$ — something gradient descent from that same starting point can never do.

What this means in practice

Simulated annealing is a practical, easy-to-implement heuristic for hard combinatorial or non-convex problems where an exact method is too slow or doesn't apply — portfolio construction with awkward discrete constraints, scheduling execution across venues, or tuning strategy parameters on a genuinely bumpy backtest-performance surface. It comes with no guarantee of finding the true global optimum in finite time, but empirically it often finds much better solutions than plain hill-climbing on the same problem, for a modest extra computational cost.