The Cross-Entropy Method for Monte-Carlo Simulation, Rare-Event Estimation and Combinatorial Optimization

Reuven Rubinstein
Faculty of Industrial and Engineering Management
Technion


Wednesday, November 24, 2004
4:30 - 5:45 PM
Terman Engineering Center, Room 453


Abstract:

The cross-entropy (CE) method is one of the most significant developments in the fields of Monte-Carlo simulation and combinatorial optimization via randomized algorithms in recent years. The former includes probabilities of rare event estimation in complex dynamic systems, like probabilities of buffer overflows in queueing systems with both, light and heavy-tailed input distributions; the latter includes approximating the optimal solution of NP-hard combinatorial and multi-extremal problems, like the optimal buffer allocation in a production line containing a number of queues and driven via simulation, scheduling, clustering, Markovian decision problems under uncertainty and machine learning. The CE method is based on a simple adaptive procedure, where each iteration contains two phases: (a) generating a random data samples (trajectories, vectors, etc.) according to a specified randomized mechanism. (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 we present a tutorial on the CE, discuss its convergence and point out further areas of its application in engineering and science.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html