METROPOLIS-TYPE ANNEALING ALGORITHMS FOR GLOBAL OPTIMIZATION IN RD

作     者：GELFAND, SB MITTER, SK 

作者机构：MITDEPT ELECT ENGN & COMP SCICAMBRIDGEMA 02139 MITINFORMAT & DECIS SYST LABCAMBRIDGEMA 02139 

出 版 物：《SIAM JOURNAL ON CONTROL AND OPTIMIZATION》 (工业与应用数学会控制与最佳化杂志)

年 卷 期：1993年第31卷第1期

页      面：111-131页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0811[工学-控制科学与工程] 0701[理学-数学] 

主　　题：GLOBAL OPTIMIZATION RANDOM OPTIMIZATION SIMULATED ANNEALING STOCHASTIC GRADIENT ALGORITHMS MARKOV CHAINS 

摘      要：The convergence of a class of Metropolis-type Markov-chain annealing algorithms for global optimization of a smooth function U(.) on R(d) 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 X(k+1) = X(k) - a(k)(del U(X(k)) + xi(k)) + b(k)W(k), where {W(k)} is a standard white Gaussian sequence, {xi(k)} are random variables, and a(k) = A/k, b(k) = square-root B/square-root k log log k for k large. Convergence results for (X(k)} are then applied from our previous work [SIAM Journal on Control and Optimization, 29 (1991), pp. 999-1018]. Since the analysis of {X(k)} is based on the asymptotic behavior of the related Langevin-type Markov diffusion annealing algorithm dY(t) = -del U (Y(t)) dt + c(t) dW(t), where W(.) is a standard Wiener process and c(t) = square-root C/square-root log t for t large, this work demonstrates and exploits the close relationship between the Markov chain and diffusion versions of simulated annealing.