On Eigenvalues and Annealing Rates

We evaluate asymptotically the eigenvalues of transition rate matrices (Q_ij^ϵ)_i,j=1ⁿ with Q_ij^ϵ ∼ exp(−(U(j) − U(i))⁺/ϵ) for some function U using Ventcel's graphic method. As a consequence, we can compare the “nearly optimal” annealing rate in (Gidas, B. 1985. Global optimization via the Langevin equation. Proc. 24th IEEE Conf. Decision and Control, Ft. Lauderdale, FL, December.) with the true optimal rate in (Hajek, B. Cooling schedules for optimal annealing. Preprint.). A necessary and sufficient condition is given for the coincidence of those rates.