A Model Reference Adaptive Search Method for Stochastic Global Optimization

We propose a randomized search method called Stochastic Model Reference Adaptive Search (SMRAS) for solving stochastic optimization problems in situations where the objective functions cannot be evaluated exactly, but can be estimated with some noise (or uncertainty), e.g., via simulation. The method generalizes the recently proposed Model Reference Adaptive Search (MRAS) for deterministic optimization, which is motivated by the well-known Cross-Entropy (CE) method. We prove global convergence of SMRAS in a general stochastic setting, and carry out numerical studies to illustrate its performance. An emphasis of this paper is on the application of SMRAS for solving static stochastic optimization problems; its various applications for solving dynamic decision making problems can be found in H. S. Chang, M. C. Fu, J. Hu, and S. I. Marcus, Simulation-based Algorithms for Markov Decision Processes, Springer-Verlag, London, 2007.

Keywords

Stochastic optimization, global optimization, combinatorial optimization

Full Text (PDF format)

Published 1 January 2008