Abstract
We present a new and fast method, called the cross-entropy method, for finding the optimal solution of combinatorial and continuous nonconvex optimization problems with convex bounded domains. To find the optimal solution we solve a sequence of simple auxiliary smooth optimization problems based on Kullback-Leibler cross-entropy, importance sampling, Markov chain and Boltzmann distribution. We use importance sampling as an important ingredient for adaptive adjustment of the temperature in the Boltzmann distribution and use Kullback-Leibler cross-entropy to find the optimal solution. In fact, we use the mode of a unimodal importance sampling distribution, like the mode of beta distribution, as an estimate of the optimal solution for continuous optimization and Markov chains approach for combinatorial optimization. In the later case we show almost surely convergence of our algorithm to the optimal solution. Supporting numerical results for both continuous and combinatorial optimization problems are given as well. Our empirical studies suggest that the cross-entropy method has polynomial in the size of the problem running time complexity.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. H. L. Aarts and J. H. M. Korst, Simulated Annealing and Boltzmann Machines, John Wiley & Sons: 1989.
E. H. L. Aarts and J. K. Lenstra, Local Search in Combinatorial Optimization, Wiley: Chichester, 1997.
W. A. T. W. Abdullah, “Seeking Global Minima, ” Journal of Computational Physics vol. 110 p. 320, 1994.
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows Theory, Algorithms and Applications, Prentice Hall: 1993.
S. M. Ali and S. D. Silvey, “A General Class of Coefficients of Divergence of one Distribution from Another” Journal of the Royal Statistical Society, Series B vol. 28, pp. 131–142, 1966.
S. Andradóttir, “A Method for Discrete Stochastic Optimization, ” Management Science vol. 41 pp. 1946–1961, 1995.
S. Andradóttir, “A Global Search Method for Discrete Stochastic Optimization, ” SIAM J. Optimization vol. 6 pp. 513–530, 1996.
S. Asmussen, Applied Probability and Queues, John Wiley & Sons: 1987.
H. Cohn and M. Fielding, “Simulated Annealing Searching for an Optimal Temperature Schedule, ” 1999 (to appear in SIAM journal of optimization).
L. Devroye, Non-Uniform Random Variate Generation, Springer: New York, 1986.
M. Dyer, A. Frieze, and R. Kannan, “A Random Polynomial-Time Algorithm for Approximation the Volume of Convex Bodies” Journal on ACM vol. 38 pp. 1–17, 1991.
B. L. Fox and G. W. Heine, “Probabilistic Search with Overrides, ” Annals of Applied Probability vol. 6 pp. 1087–1094, 1996.
C. J. Geyer and E.A. Thompson, “Annealing Markov Chain Monte-Carlo with Applications to to Ancestral Inference” Journal of the American Statistical Association vol. 90 pp. 909–920, 1995.
W. R. Gilks, S. Richardson, and D. J. Spiegelhalter, Markov Chain Monte Carlo in Practice, Chapman & Hall: 1996.
F. Glover and M. Laguna, “Tabu Search, ” a chapter in Modern Heuristic Techniques for Combinatorial Optimization, 1992.
D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, MA., 1989.
W. B. Gong, Y. C. Ho, and W. Zhai “Stochastic Comparison Algorithm for Discrete Optimization with Estimation, ” Proceedings of the 31st IEEE Conference on Decision and Control, pp. 795–800, 1992.
W. J. Gutjahr and G. Ch. Pflug, “Simulated Annealing for Noisy Cost Functions, ” Journal of Global Optimization vol. 8 pp. 1–13, 1996.
W. K. Hastings, “Monte Carlo Sampling Methods using Markov Chains and their Applications, ” Biometrika vol. 57 pp. 92–109, 1970.
R. Horst, P. M. Pardalos, and N. V. Thoai, Introduction to Global Optimization, Kluwer Academic Publishers: 1996.
M. R. Jerrum and A. J. Sinclair, “Approximating the Permanent, ” SIAM Journal on Computing vol. 18 pp. 1149–1178, 1989.
M. R. Jerrum and A. J. Sinclair, “Polynomial-Time Approximation Algorithms for the Ising Model, ” SIAM Journal on Computing vol. 22 pp. 1087–1116, 1993.
N. L. Johnson and S. Kotz, Urn Models and Their Applications: An Approach to Modern Discrete Probability Theory, John Wiley and Sons, Inc.: 1977.
R. M. Karp and M. Luby, “Monte-Carlo Algorithms for Enumeration and Reliability Problems, ” Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science pp. 56–64, 1983.
J. N. Kapur and H. K. Kesavan, Entropy Optimization Principles with Applications, Academic Press: 1992.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing, ” Science vol. 220 pp. 671–680, 1983.
D. Lieber, Rare Events Estimation Via Cross-Entropy and Importance Sampling, PHD Thesis,William Davidson Faculty of Industrial Engineering and Management, Technion, Haifa, Israel, 1999.
D. Lieber, R. Y. Rubinstein, and D. Elmakis, “Quick Estimation of Rare events in Stochastic Networks, ” IEEE, Transactions on Reliability vol. 46(2) pp. 254–265, 1997.
L. Lovasz, “Randomized Algorithms in Combinatorial Optimization, ” DIMACS Seies in Discrete Mathematics and Theoretical Computer Science vol. 25, pp. 153–179, 1995.
E. Marinari and G. Parisi, “Simulated Tempering: A New Monte Carlo Scheme, ” Europhisics letters vol. 19 pp. 451–458, 1992.
R. Mead and J. A. Nedler, “A Simplex Method for Function Minimization, ” Computer Journal vol. 7 pp. 308–313, 1965.
M. Metropolis, A.W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller “Equations of State Calculations by Fast Computing Machines, ” J. of Chemical Physics vol. 21 pp. 1087–1092, 1953.
W. I. Norkin, G. C. Pflug, and A. Ruszczyński, “A Branch and Bound Method for Stochastic Global Optimization”. Working paper, International Institute for Applied System Analysis, WP-96-065, Laxenburg, Austria, 1996.
I. H. Osman and G. Laporte, “Metaheuristics: A bibliography, ” Annals of Operations Research vol. 63 pp. 513–523, 1996.
J. D. Pinter, Global Optimization in Action, Kluwer Academic Publishers: 1996.
R. G. Parker and R. L. Rardin, Discrete Optimization, Academic Press: San Diego, 1988.
G. Potamianos and J. Goutsias, “Stochastic Approximation Algorithms for Partition Function Estimation of Gibbs Random Fields, ” IEEE Transactions on Information Theory vol. 43(6) pp. 1948–1965, 1997.
V. J. Rayward-Smith, I. H. Osman, C. R. Reeves, and G. D. Smith, Modern Heuristic Search Methods, Wiley: Chichester, 1996.
C. R. Reeves, Modern heuristic techniques, in: Modern Heuristic Search Methods (eds. V. J. Rayward-Smith, I. H. Osman, C. R. Reeves and G. D. Smith), Wiley: Chichester, 1996.
H. E. Romeijn and R. L. Smith, “Simulated Annealing for Constrained Global Optimization, ” Journal of Global Optimization vol. 5 pp. 101–126, 1994.
R. Y. Rubinstein, Simulation and the Monte Carlo Methods, John Wiley and Sons, Inc., 1981.
R. Y. Rubinstein, “Optimization of Computer Simulation Models with Rare Events, ” European Journal of Operations Research vol. 99 pp. 89–112, 1997.
R. Y. Rubinstein and B. Melamed, Efficient Simulation and Modeling, John Wiley & Sons: 1998.
R. Y. Rubinstein and A. Shapiro, Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization via the Score Function Method, John Wiley & Sons: 1993.
L. Shi and S. Olafsson, “Nested Partitioning Method for Global Optimization” Manuscript, Department of Industrial Engineering, University of Wisconsin-Madison.
A. J. Walker, “An Efficient Method for Generating Discrete Random Variables with General Distributions, ” Assoc. Comput. Mach. Trans. Math. Software vol. 3, pp. 253–256, 1977.
Rights and permissions
About this article
Cite this article
Rubinstein, R. The Cross-Entropy Method for Combinatorial and Continuous Optimization. Methodology and Computing in Applied Probability 1, 127–190 (1999). https://doi.org/10.1023/A:1010091220143
Issue Date:
DOI: https://doi.org/10.1023/A:1010091220143