Report on MASCOS One-Day Symposium

The Cross-Entropy Method: a New Approach to Rare Event Simulation and Randomized Optimization

The University of Queensland
Thursday 22nd January 2004

General   The cross-entropy method is a powerful and versatile technique for both rare-event simulation and combinatorial optimisation. This symposium, sponsored by the ARC Centre of Excellence for Mathematics and Statistics of Complex Systems (MASCOS), will highlight recent developments in the area. For details on the Cross-Entropy Method, see http://www.cemethod.org/.

Invited speakers

• Soren Asmussen (University of Aarhus)
• Kin Ping Hui (Defence Science and Technology Organisation, Australia)
• Dirk Kroese (University of Queensland)
• Sho Nariai (University of Queensland)

[There were no contributed papers]

Organizer   Phil Pollett (MASCOS, University of Queensland)

Contact   Phil Pollett (P.Pollett at complex.org.au)

Venue   Lectures took place in the Priestley Building (Building 67) Basement Lecture Theatre (Room 141) at the St Lucia Campus, University of Queensland

Programme  

	10:00	Opening
	10:15	Dirk Kroese	"A Tutorial Introduction to the Cross-Entropy Method"
	11:15	--Break--	[Refeshments provided]
	11:30	Sho Nariai	"Application of the Cross-Entropy Method to Continuous Optimisation"
	12:30	--Lunch Break--
	14:00	Soren Asmussen	"Heavy Tails, Importance Sampling and Cross-Entropy"
	15:00	--Break--	[Refeshments provided]
	15:15	Kin Ping Hui	"The Cross-Entropy Method for Network Reliability Estimation"
	16:15	Close

Abstracts

• Søren Asmussen

  Heavy Tails, Importance Sampling and Cross-Entropy

  Abstract: We consider the problem of estimating P(Y₁+ ... +Y_n > x) by importance sampling when the Y_i are i.i.d. and heavy-tailed. The idea is to exploit the cross-entropy method as a tool for choosing good parameters in the importance sampling distribution; in doing so, we use the asymptotic description that given P(Y₁+...+Y_n >x), n-1 of the Y_i have distribution F and one the conditional distribution of Y given Y>x. We show in some specific parametric examples (Pareto and Weibull) how this leads to precise answers which, as demonstrated numerically, are close to being variance minimal within the parametric class under consideration. Related problems for M/G/1 and GI/G/1 queues are also discussed. This is joint work with Kroese and Rubinstein

• Kin Ping Hui

  The Cross-Entropy Method for Network Reliability Estimation

  Abstract: Consider a network of unreliable links, modelling for example a communication network. Estimating the reliability of the network - expressed as the probability that certain nodes in the network are connected - is a computationally difficult task. In this talk we will look at how the Cross-Entropy method can be used to obtain more efficient network relaibility estimation procedures. Three techniques of estimation are considered: Crude Monte Carlo and the more sophisticated Permutaion Monte Carlo and Merge Process. We show that the Cross-Entropy method yields a speed-up over all three techniques. This is a joint work with Kroese, Bean and Kraetzl.

• Dirk Kroese

  A Tutorial Introduction to the Cross-Entropy Method

  Abstract: The cross-entropy (CE) method is a versatile and powerful new technique for efficient Monte Carlo simulation and optimisation. The method derives its name from the cross-entropy (or Kullback-Leibler) distance, a well-known measure of "information", which has been successfully employed in diverse fields of engineering, science and statistics.

  In this talk I would like to give a gentle introduction to the CE method. I will start with two simple examples in rare event simulation and combinatorial optimisation. In the middle section of the talk I will explain the cross-entropy concept in more detail and its significance for both simulation and optimisation. I will conclude with a more elaborate application in combinatorial optimisation.

• Sho Nariai

  Application of the Cross-Entropy Method to Continuous Optimisation

  Abstract: The CE method can be used not only for estimating the probability of rare events and solving combinatorial optimisation problems, but also for continuous optimisation. In this talk I will show how the CE method is used to optimise continuous multi-extremal functions. I will also show how the CE parameters such as sample size N and the rarity parameter r should be chosen in order to obtain the solution in the shortest time possible. Numerical results show the effectiveness of the CE approach, and demonstrate that the method still works well if a significant amount of noise is added to the objective function.