Collaborative Research: Adaptive Search in Global Optimization

University Of Washington, Seattle WA

Investigators

Abstract

Global optimization is a rapidly growing field, due to the increased availability of computing power and improvement in methods. A synergy is occurring where the emerging technology is enabling applications to blossom, and the experience with new applications is inspiring better methods. We are developing the capability, not only to describe complex systems, but also to prescribe solutions. The primary objective of this research is to develop theory and algorithms for global optimization problems that may include both discrete and continuous variables, including ill-structured black-box objective functions for which only an estimate (such as a stochastic simulation) is available. The team's approach is based on theoretical insights drawn from the average linear complexity of Pure Adaptive Search, developed by the authors, for global optimization. Adaptive Search attempts to realize this polynomial efficiency by constructing sampling distributions that yield a high likelihood of sampling improving points. A practical implementation hinges on developing an efficient Markov chain Monte Carlo (MCMC) sampler. A key research step is to develop discrete Hit-and-Run as a general MCMC sampler for a discrete domain and embed it within a generalized Adaptive Search framework to support a hoped for polynomial time, on average, algorithm. An attempt to reap the promise offered by the theoretical studies will be applied to practical arenas. Many global optimization heuristic methods, including simulated annealing and genetic algorithms, would be strengthened by rigorous approaches to determining better algorithmic parameters and stopping criteria. The research will develop the theory and methodology to address these issues for a general global optimization problem. The intellectual merit of this work primarily resides in enriching the field of global optimization, but also may shape, as it has in the past, more fundamental work in MCMC samplers. The broad impact of this work lies in the potential of the algorithms developed to optimize complex engineering systems. The prevalence of powerful computer technology is providing an opportunity to accurately model complex systems with software simulations, replacing traditional closed-form mathematical equations. The resulting models require robust optimization techniques that presume little known structure for the underlying models.