Simulated annealing with time-dependent energy function via Sobolev inequalities
The approach to the investigation of the simulated annealing algorithm based on the spectral gap estimates and Sobolev inequalities [see e.g. \textit{R. Holley} and \textit{D. Stroock}, Commun. Math. Phys. 115, No. 4, 553-569 (1988; Zbl 0643.60092)] is extended to the case of a time dependent energy function. More precisely: let \(X\) be a finite set, let us consider a family of energy functions \(U_{t} : X\to \mathbf R\). Let \(q\) be an irreducible transition probability on \(X\) with a reversible measure \(\pi \), let \(\beta : \mathbf R_{+}\to ]0,+\infty [\) be an increasing function. Set \[ q_{t}(x,y) = \exp \{-\beta _{t}(U_{t}(y)-U_{t}(x))^{+}\}q(x,y), \;x\neq y, \quad q_{t}(x,x) = 1-\sum _{y\neq x} q_{t}(x,y), \] then \(q_{t}\) is reversible with respect to the Gibbs measure \(\pi _{t}\) with energy \(U_{t}\) at inverse temperature \(\beta _{t}\) with a reference measure \(\pi \). Define a self-adjoint operator \(L_{t}\) on \(L^{2}(\pi _{t})\) by \(L_{t}\Phi = \sum _{y\in X} (\Phi (y)-\Phi (\cdot))q_{t}(\cdot , y)\) and denote by \(Y_{t}\) the Markov process corresponding to transition kernels \(P_{s,t}\) on \(X\) that solve the Kolmogorov equation \[ \frac {\partial}{\partial t} (P_{s,t}\Phi)(x) = P_{s,t}(L_{t}\Phi)(x), \quad P_{s,s}\Phi = \Phi , \quad t>s, \;x\in X. \] Under some regularity assumptions on \(U_{t}\) and \(\beta _{t}\), at first the precise order of the second smallest eigenvalue of \(-L_{t}\) is established and then an upper bound on the \(L^{2}(\pi _{t})\)-norm of the Radon-Nikodym derivative of the law of \(Y_{t}\) with respect to \(\pi _{t}\) is given. Furthermore, the entrance time of the algorithm into a set \(V\subset X\) is estimated in terms of \(\pi _{t}(X\setminus V)\).
- L^ 2 convergence of time nonhomogeneous Markov processes. I: Spectral estimates
- Applied simulated annealing
- Cooling Schedules for Optimal Annealing
- Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
- Geometric bounds for eigenvalues of Markov chains
- scientific article; zbMATH DE number 3826915 (Why is no real title available?)
- scientific article; zbMATH DE number 41891 (Why is no real title available?)
- scientific article; zbMATH DE number 125396 (Why is no real title available?)
- scientific article; zbMATH DE number 3497315 (Why is no real title available?)
- scientific article; zbMATH DE number 837115 (Why is no real title available?)
- Matrix Analysis
- Neural networks and physical systems with emergent collective computational abilities
- Nonstationary Markov chains and convergence of the annealing algorithm
- On the convergence of genetic algorithms
- Optimization by simulated annealing
- Sharp large deviations estimates for simulated annealing algorithms
- Simulated annealing via Sobolev inequalities
- Simulated annealing with time-dependent energy function
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
- Stochastic protein folding simulation in the three-dimensional HP-model
- Simulated annealing via Sobolev inequalities
- Simulated annealing with time-dependent energy function
- Estimation of the density of simulated annealing
- On the invariant measure of non-reversible simulated annealing
- An adaptive simulated annealing algorithm.
- From simulated annealing to stochastic continuation: a new trend in combinatorial optimization
- Some remarks on replicated simulated annealing
- scientific article; zbMATH DE number 66227 (Why is no real title available?)
- Long‐Time Behaviour of Langevin Algorithms with Time‐dependent Energy Function
- Stochastic gradient descent and fast relaxation to thermodynamic equilibrium: a stochastic control approach
- On simulated annealing with temperature-dependent energy and temperature-dependent communication
This page was built for publication: Simulated annealing with time-dependent energy function via Sobolev inequalities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1272167)
