Metropolis-Type Annealing Algorithms for Global Optimization in Rᵈ

The convergence of a class of Metropolis-type Markov-chain annealing algorithms for global optimization of a smooth function U( · ) on Rᵈ is established. No prior information is assumed as to what bounded region contains a global minimum. The analysis contained herein is based on writing the Metropolis-type algorithm in the form of a recursive stochastic algorithm Xk + 1 = Xₖ - aₖ (∇ U(Xₖ ) + ξ ₖ ) + bₖ Wₖ, where \ Wₖ \ is a standard white Gaussian sequence, \ ξ ₖ \ are random variables, and aₖ = A / k, bₖ = √ B / √klog log k for k large. Convergence results for \ Xₖ \ are then applied from our previous work [SIAM Journal on Control and Optimization, 29 (1991), pp. 999–1018]. Since the analysis of \ Xₖ \ is based on the asymptotic behavior of the related Langevin-type Markov diffusion annealing algorithm dY(t) = - ∇ U(Y(t))dt + c(t)dW(t), where W( · ) is a standard Wiener process and c(t) = √ C / √log t for t large, this work demonstrates and exploits the close relationship between the Markov chain and diffusion versions of simulated annealing.