ISSN:
1432-0541
Keywords:
Simulated annealing
;
Random search
;
Stochastic approximation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We study the convergence of a class of discrete-time continuous-state simulated annealing type algorithms for multivariate optimization. The general algorithm that we consider is of the formX k +1 =X k −a k (▽U(X k ) + ξk) +b k W k . HereU(·) is a smooth function on a compact subset of ℝ d , {ξk} is a sequence of ℝ d -valued random variables, {W k } is a sequence of independent standardd-dimensional Gaussian random variables, and {a k }, {b k } are sequences of positive numbers which tend to zero. These algorithms arise by adding decreasing white Gaussian noise to gradient descent, random search, and stochastic approximation algorithms. We show under suitable conditions onU(·), {ξ k }, {a k }, and {b k } thatX k converges in probability to the set of global minima ofU(·). A careful treatment of howX k is restricted to a compact set and its effect on convergence is given.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01759052
Permalink