In principle, MetropolisHastings algorithms can also be used to find the set of global maxima of
a given function. The button below opens a separate window from your browser containing a
demonstration of this. The window is resizable, but you may need to adjust its dimensions
depending on your system configuration.
The principle of simulated annealing
Suppose we wish to find the set of global maxima of a given function. Conventionally, we could
proceed by differentiating the function, and setting this derivative to zero. This would give the
set of local extrema and inflection points, which we could then analyse further to find the
maxima etc.
The classical (non random) numerical methods which perform this task are often impractical
when the function is complicated.
The simulated annealing approach consists in thinking of the function to be maximized as a
probability density, and running a Markov chain with this density as equilibrium distribution.
However, this will not yet give the maxima. At the same time the chain is run, the density is
gradually raised to higher and higher powers (this is called lowering the temperature). In the
limit as the temperature goes to zero, the successive densities turn into a collection of point
masses located on the set of global maxima of the function. Thus when the temperature is very
low, the corresponding Markov chain will spend most of its time near the global maxima.
You can try out some of the standard Metropolis Hastings algorithms from the
MetropolisHastings applet on simulated annealing. But beware of choosing cooling schedules
that are too fast, for then the algorithm can easily get "stuck".
