On the convergence of an improved and adaptive kinetic simulated annealing

arXiv2009.00195MaRDI QIDQ6348128FDOQ6348128

Authors: Michael C. H. Choi 

Publication date: 31 August 2020

Abstract: Inspired by the work of [Fang et al.. An improved annealing method and its large-time behaviour. Stochastic Process. Appl. (1997), Volume 71 Issue 1 Page 55-74.], who propose an improved simulated annealing algorithm based on a variant of overdamped Langevin diffusion with state-dependent diffusion coefficient, we cast this idea in the kinetic setting and develop an improved kinetic simulated annealing (IKSA) method for minimizing a target function $U$. To analyze its convergence, we utilize the framework recently introduced by [Monmarch'{e}. Hypocoercivity in metastable settings and kinetic simulated annealing. Probab. Theory Related Fields (2018), Volume 172 Page 1215-1248.] for the case of kinetic simulated annealing (KSA). The core idea of IKSA rests on introducing a parameter $c>infU$, which de facto modifies the optimization landscape and clips the critical height in IKSA at a maximum of $c-infU$. Consequently IKSA enjoys improved convergence with faster logarithmic cooling than KSA. To tune the parameter $c$, we propose an adaptive method that we call IAKSA which utilizes the running minimum generated by the algorithm on the fly, thus avoiding the need to manually adjust $c$ for better performance. We present positive numerical results on some standard global optimization benchmark functions that verify the improved convergence of IAKSA over other Langevin-based annealing methods.

Mathematics Subject Classification ID

Applications of functional analysis in probability theory and statistics (46N30) Diffusion processes (60J60) Continuous-time Markov processes on general state spaces (60J25)

This page was built for publication: On the convergence of an improved and adaptive kinetic simulated annealing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348128)