Fast Sequential Monte Carlo Methods for Counting and Optimization

Chapter 3

Minimum Cross-Entropy Method

This chapter deals with the minimum cross-entropy method, also known as the MinxEnt method for combinatorial optimization problems and rare-event probability estimation. The main idea of MinxEnt is to associate with each original optimization problem an auxiliary single-constrained convex optimization program in terms of probability density functions. The beauty is that this auxiliary program has a closed-form solution, which becomes the optimal zero variance solution, provided the “temperature” parameter is set to minus infinity. In addition, the associated pdf based on the product of marginals obtained from the joint optimal zero variance pdf coincide with the parametric pdf of the cross-entropy (CE) method. Thus, we obtain a strong connection between CE and MinxEnt, providing solid mathematical foundations.

3.1 Introduction

Let be a continuous function defined on some closed bounded -dimensional domain . Assume that is a unique minimum point over . The following theorem is due to Pincus [94].

Theorem 3.1

Let be a real-valued continuous function ...