Recursive stochastic algorithms for global optimization in IRd

Considered is an algorithm of the form X_k+1=X_k -a_k (ΔU(X_k)+ζ)+b_kW_k, where U(·) is a smooth function on IR^d, {ζ_k} is a sequence of IR^d-valued random variables, {W_k} is a sequence of independent standard d-dimensional Gaussian random variables, a_k=A/k and b_k=√B/√kloglogk for k large. 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(·), {ζ_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