Asymptotic Global Behavior for Stochastic Approximation and Diffusions with Slowly Decreasing Noise Effects: Global Minimization via Monte Carlo

The asymptotic behavior of the systems X₍ + ₁ = Xₙ + aₙ b (Xₙ, ₙ) + aₙ (Xₙ) ₙ and dy = b (y) dt + a (t) (y) dw is studied, where \ { ₙ \} is i. i. d. Gaussian, \ ₙ \ is a (correlated) bounded sequence of random variables and aₙ A₀/ (A₁ + n). Without \ ₙ \, such algorithms are versions of the “simulated annealing” method for global optimization. When the objective function values can only be sampled via Monte Carlo, the discrete algorithm is a combination of stochastic approximation and simulated annealing. Our forms are appropriate. The \ ₙ \ are the “annealing” variables, and \ ₙ \ is the sampling noise. For large A₀, a full asymptotic analysis is presented, via the theory of large deviations: Mean escape time (after arbitrary time n) from neighborhoods of stable sets of the algorithm, mean transition times (after arbitrary time n) from a neighborhood of one stable set to another, approximate asymptotic invariant measures, and location of the values of \ Xₙ \ or y (), the case where Eb (x, ) = b (x) is the (negative) of a gradient of a function B (x), and application to global function minimization via Monte Carlo methods.