Reuven Rubinstein

Faculty of Industrial and Engineering Management Technion

Title: The Cross-Entropy Method: A unified approach for Monte-Carlo Simulation, Rare-Event Estimation and Combinatorial Optimization.

Abstract:

The cross-entropy (CE) method is one of the most significant developments in
the fields of Monte-Carlo simulation and simulation-based optimization in
recent years. The former includes  probabilities of rare event estimation in
complex  models, like in queuing models; estimation of normalization constant,
like in Ising models;  counting problems, like calculating the permanent;  the
latter includes approximating the optimal solution of combinatorial and 
multi-extremal problems,  like of Markovian decision problems under uncertainty
and machine learning. The CE method presents  a simple generic adaptive procedure,
where each iteration contains two phases: (a) generating a random data samples 
(trajectories, vectors, etc.) according to a specified probability distribution. 
(b) updating the parameters of the distributions associated with the data generated 
by the random mechanism in order to produce a "better" sample at the next iteration.

In this talk I present a tutorial on the CE, show how it solves some of
the above mentioned problems  and indicate how CE is related to Sequential
Monte-Carlo, MCMC and Gibs Sampler.