Use of Probability in Global Optimization

Abstract:  Complex systems are often modeled with black-box functions that are ill-structured and are available only through computer programs.  Random search algorithms (e.g., simulated annealing, cross-entropy) have been shown to be very effective at making use of probability distributions to focus samples on “good” regions.  We analyze an idealized adaptive random search algorithm as a marked Poisson process, and use it to motivate sampling distributions.  Then we apply a Markov chain Monte Carlo sampler, namely Hit-and-Run, to approximate the sampling distribution.  Recent work extends the analysis to noisy functions, and motivates a partition-based random search optimization algorithm.