RECURSIVE STOCHASTIC ALGORITHMS FOR GLOBAL OPTIMIZATION IN RD

被引:142
作者
GELFAND, SB
MITTER, SK
机构
[1] MIT,DEPT ELECT ENGN & COMP SCI,CAMBRIDGE,MA 02139
[2] MIT,INFORMAT & DECIS SYST LAB,CAMBRIDGE,MA 02139
关键词
GLOBAL OPTIMIZATION; RANDOM OPTIMIZATION; SIMULATED ANNEALING; STOCHASTIC GRADIENT ALGORITHMS; DIFFUSIONS;
D O I
10.1137/0329055
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
An algorithm of the form X(k+1) = X(k) - a(k)(nabla U(X(k) + xi-k) + b(k) W(k), where U(.) is a smooth function on R(d), {xi-k} is a sequence of R(d)-valued random variables, {W(k)} is a sequence of independent standard d-dimensional Gaussian random variables, a(k) = A/k and b(k) = square-root B/ square-root k log log k for k large, is considered. An algorithm of this type arises by adding slowly decreasing white Gaussian noise to a stochastic gradient algorithm. It is shown, under suitable conditions on U(.), {xi-k}, A, and B, that X(k) converges in probability to the set of global minima of U(.). No prior information is assumed as to what bounded region contains a global minimum. The analysis is based on the asymptotic behavior of the related diffusion process dY(t) = -nabla U(Y(t))dt + c(t)dW(t), where W(.) is a standard d-dimensional Wiener process and c(t) = square-root C/square-root log t for t large.
引用
收藏
页码:999 / 1018
页数:20
相关论文
共 11 条
[1]  
[Anonymous], 1984, RANDOM PERTURBATIONS
[2]   DIFFUSION FOR GLOBAL OPTIMIZATION IN RN [J].
CHIANG, TS ;
HWANG, CR ;
SHEU, SJ .
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1987, 25 (03) :737-753
[3]  
Dixon L.C.W., 1978, GLOBAL OPTIMIZATION
[4]  
Doob J. L., 1952, STOCHASTIC PROCESSES
[5]   DIFFUSIONS FOR GLOBAL OPTIMIZATION [J].
GEMAN, S ;
HWANG, CR .
SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1986, 24 (05) :1031-1043
[6]  
GIDAS B, 1985, 24TH P IEEE C DEC CO, P774
[7]  
GRENENDER U, 1984, TUTORIAL PATTERN THE
[8]   LAPLACE METHOD REVISITED - WEAK-CONVERGENCE OF PROBABILITY-MEASURES [J].
HWANG, CR .
ANNALS OF PROBABILITY, 1980, 8 (06) :1177-1182
[9]  
Kushner H. J., 1978, Stochastic approximation methods for constrained and unconstrained systems