Cross-entropy method

The cross-entropy (CE) method is a Monte Carlo method for importance sampling and optimization. It is applicable to both combinatorial and continuous problems, with either a static or noisy objective.

The method approximates the optimal importance sampling estimator by repeating two phases:

Reuven Rubinstein developed the method in the context of rare-event simulation, where tiny probabilities must be estimated, for example in network reliability analysis, queueing models, or performance analysis of telecommunication systems. The method has also been applied to the traveling salesman, quadratic assignment, DNA sequence alignment, max-cut and buffer allocation problems.

Consider the general problem of estimating the quantity

${\displaystyle \ell =\mathbb {E} _{\mathbf {u} }[H(\mathbf {X} )]=\int H(\mathbf {x} )\,f(\mathbf {x} ;\mathbf {u} )\,{\textrm {d}}\mathbf {x} }$,

where ${\displaystyle H}$ is some performance function and ${\displaystyle f(\mathbf {x} ;\mathbf {u} )}$ is a member of some parametric family of distributions. Using importance sampling this quantity can be estimated as

${\displaystyle {\hat {\ell }}={\frac {1}{N}}\sum _{i=1}^{N}H(\mathbf {X} _{i}){\frac {f(\mathbf {X} _{i};\mathbf {u} )}{g(\mathbf {X} _{i})}}}$,

where ${\displaystyle \mathbf {X} _{1},\dots ,\mathbf {X} _{N}}$ is a random sample from ${\displaystyle g\,}$. For positive ${\displaystyle H}$, the theoretically optimal importance sampling density (PDF) is given by