An improved annealing method and its large-time behavior (Q1965868)

Let \(U\in \mathcal C^{3}(\mathbb R^{d})\) be a function such that \(\Delta U(x)/|\nabla U(x)|^{2}\to 0\) as \(|x|\to \infty \) and with the Hessian matrix \(D^{2}U(x)\) uniformly positive for all \(x\) outside some ball. Simulated annealing is a probabilistic procedure for searching for global minima of the function \(U\). Its usual version is based on the convergence of the inhomogeneous Markov process governed by the equation \(dY_{t} = - \nabla U(Y_{t}) dt + \varepsilon (t)^{1/2} d B_{t}\) to the set \(\{x: U(x) = \min U\}\) of global minima of \(U\), if \(\varepsilon (t)\) is a suitable function going slowly to zero as \(t\to \infty \). A new (faster) version of the simulated annealing algorithm is proposed. Namely, asymptotic behaviour of the Markov process defined by \[ dX_{t} = - \nabla U(X_{t}) dt + (f((U(X_{t})-c)^{+}) +\varepsilon (t))^{1/2} d B_{t}\tag{1} \] is studied, where \(B\) is a \(d\)-dimensional Wiener process, \(f\in \mathcal C^{2}([0,\infty [)\) is an increasing bounded function, \(f(0) = f'(0) = f''(0) = 0\), \(c>\min U\), and \(\varepsilon (t) = b(\log (t+ t_{0}))^{-1}\) with sufficiently large constants \(b\), \(t_0\). Towards this end, the generator of the Markov process corresponding to (1) with \(\varepsilon (t)\equiv \varepsilon >0\) is investigated, the spectral gap being estimated and a logarithmic Sobolev inequality established.