Advances in Cross-Entropy Methods

Thomas Taimre (2009). Advances in Cross-Entropy Methods PhD Thesis, School of Physical Sciences, The University of Queensland.

       
Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
n40143109_PhD_abstract.pdf Final Thesis Abstract application/pdf 17.24KB 21
n40143109_PhD_totalthesis.pdf n40143109_PhD_totalthesis.pdf application/pdf 2.68MB 29
Author Thomas Taimre
Thesis Title Advances in Cross-Entropy Methods
School, Centre or Institute School of Physical Sciences
Institution The University of Queensland
Publication date 2009-05
Thesis type PhD Thesis
Total pages 217
Total black and white pages 217
Subjects 240000 Physical Sciences
Abstract/Summary The cross-entropy method is an established technique for solving difficult estimation, simulation, and optimisation problems. The method has its origins in an adaptive importance sampling procedure for rare-event estimation published by R. Y. Rubinstein in 1997. In that publication, the adaptive procedure produces a parametric probability density function whose parameters minimise the variance of the associated likelihood ratio estimator. This variance minimisation can also be viewed as minimising a measure of divergence to the minimum-variance importance sampling density over all members of the parametric family in question. Soon thereafter it was realised that the same adaptive importance sampling procedure could be used to solve combinatorial optimisation problems by viewing the set of solutions to the optimisation problem as a rare-event. This realisation led to the debut of the cross-entropy method in 1999, where it was introduced as a modification to the existing adaptive importance sampling procedure, with a different choice of directed divergence measure, in particular, the Kullback-Leibler cross-entropy. The contributions of this thesis are threefold. Firstly, in a review capacity, it provides an up-to-date consolidation of material on the cross-entropy method and its generalisations, as well as a collation of background material on importance sampling and Monte Carlo methods. The reviews are elucidated with original commentary and examples. Secondly, two new major applications of the cross-entropy methodology to optimisation problems are presented, advancing the boundary of knowledge on cross-entropy in the applied arena. Thirdly, two contributions to the methodological front are (a) an original extension of the generalised cross-entropy framework which enables one to construct state- and time-dependent importance sampling algorithms, and (b) a new algorithm for counting solutions to difficult binary-encoded problems.
Keyword cross-entropy
importance sampling
rare events
optimisation

 
Citation counts: Google Scholar Search Google Scholar
Access Statistics: 400 Abstract Views, 50 File Downloads  -  Detailed Statistics
Created: Thu, 14 May 2009, 11:34:27 EST by Mr Thomas Taimre on behalf of Library - Information Access Service