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

The asymptotic behavior of the systems Xn + 1 = 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₀/log (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.