O'Reilly logo

Fast Sequential Monte Carlo Methods for Counting and Optimization by Radislav Vaisman, Ad Ridder, Reuven Y. Rubinstein

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 c03-math-0001 be a continuous function defined on some closed bounded c03-math-0002-dimensional domain c03-math-0003. Assume that c03-math-0004 is a unique minimum point over . The following theorem is due to Pincus [94].

Theorem 3.1
Let be a real-valued continuous function ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required