Annealing adaptive search,cross‐entropy,and stochastic approximation in global optimization |
| |
Authors: | Jiaqiao Hu Ping Hu |
| |
Affiliation: | Department of Applied Mathematics and Statistics, State University of New York at Stony Brook, Stony Brook, New York 11794 |
| |
Abstract: | The Annealing Adaptive Search (AAS) algorithm for global optimization searches the solution space by sampling from a sequence of Boltzmann distributions. For a class of optimization problems, it has been shown that the complexity of AAS increases at most linearly in the problem dimension. However, despite its desirable property, sampling from a Boltzmann distribution at each iteration of the algorithm remains a practical challenge. Prior work to address this issue has focused on embedding Markov chain‐based sampling techniques within the AAS framework. In this article, based on ideas from the recent Cross‐Entropy method and Model Reference Adaptive Search, we propose an algorithm, called Model‐based Annealing Random Search (MARS), that complements prior work by sampling solutions from a sequence of surrogate distributions that iteratively approximate the target Boltzmann distributions. We establish a novel connection between MARS and the well‐known Stochastic Approximation method. By exploiting this connection, we prove the global convergence of MARS and characterize its asymptotic convergence rate behavior. Our empirical results indicate promising performance of the algorithm in comparison with some of the existing methods. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011 |
| |
Keywords: | global optimization annealing adaptive search (AAS) cross‐entropy method (CE) stochastic approximation (SA) |
|
|