Description of Methods

    Search Methods
       Adaptive
           Single Working Point Methods
                Simulated Annealing

Simulated Annealing (analog from Physics) is a repeated three stage procedure. In each stage: a trial point is sampled from a Boltzmann distribution, the point is accepted or rejected based on an acceptance criterion which may even accept a worse point than the current, and the acceptance criterion is updated so that accepting a worse point is less probable in the next round. When some stopping criterion is fulfilled the algorithm gives as result the current point. [Kirkpatrick et al 1982]

One procedure to generate a new trial point is by generating a Markov chain of L points according to a distribution defined over A and with its mode in the previous point in the chain. L is normally proposed to be a linear function of n, eg. L=10n.

The reduction of the probability to accept a worse point is called the cooling schedule. This affects the efficiency and the quality of the algorithm. Fast cooling makes the algorithm to stop quickly in some local minimum, slow cooling makes the algorithm jump more or less randomly for long before settling. Under certain conditions the infinitely applied algorithm can be shown to converge in probability.

Several modifications exist, a recent one uses local information of f that adapt the length L of the Markov chain and is used in the stopping condition [Ali and Storey 1997].