Simulated annealing via Sobolev inequalities (Q1102047)

The new idea of the paper is to use the Sobolev inequality and logarithmic Sobolev inequality to study the simulated annealing algorithm. Even though the state space treated here is finite many results are meaningful for other cases. The approach yields some information about the rate at which the annealing process is tending to the minima of the given cost function. In fact, it is proved that the estimates for the rate are optimal in some sense.