simulated annealing

Named for slow-cooled metal settling into a low-energy crystal structure, simulated annealing maintains a current point x and a temperature T: each iteration proposes a random neighbor x', always accepts an improving move (\Delta E=f(x')-f(x)\le0), and accepts a worsening move with probability P=e^{-\Delta E/T} (the Metropolis criterion), then cools T. High T explores broadly; T\to0 behaves like ordinary local search.