state number of iterations figure typical states generated by the simulated annealing algorithm cross-entropy cross-entropy method the cross-entropy (cemethod [ is simple monte carlo algorithm that can be used for both optimization and estimation the basic idea of the ce method for minimizing function on set is to define parametric family of probability densities ( ) von and to iteratively update the parameter so that (vplaces more mass on states that have smaller values than on the previous iteration in particularthe ce algorithm has two basic phasessamplingsamples are drawn independently according to (vthe objective function is evaluated at these points elite sample rarity parameter smoothing parameter updatinga new parameter is selected on the basis of those xi for which (xi for some level these {xi form the elite sample sete at each iteration the level parameter is chosen as the worst of the elite : %ne best performing sampleswhere ( is the rarity parameter -typically or the parameter is updated as smoothed average av +( - )vwhere ( is the smoothing parameter and :argmax ln ( ( vv xe the updating rule ( is the result of minimizing the kullback-leibler divergence between the conditional density of ( vgiven ( gand (xv)see [ note that ( yields the maximum likelihood estimator (mleof based on the elite samples hencefor many specific families of distributionsexplicit solutions can be found an important example is where (udiag( ))that isx has independent gaussian