Collaborative Research: Adaptive Search for Global Optimization

由于计算能力的提高和方法的改进，全局优化是一个快速增长的领域。 当新兴技术使应用程序能够开花时，协同作用正在发生，而新应用程序的经验正在激发更好的方法。 我们正在开发的能力，不仅要描述复杂的系统，而且要规定解决方案。本研究的主要目标是开发全局优化问题的理论和算法，这些问题可能包括离散和连续变量，包括结构不良的黑箱目标函数，只有一个估计（如随机模拟）。 该团队的方法是基于作者开发的纯自适应搜索的平均线性复杂度的理论见解，用于全局优化。 自适应搜索试图通过构造采样分布来实现这种多项式效率，该采样分布产生采样改进点的高可能性。 一个实际的实现取决于开发一个有效的马尔可夫链蒙特卡罗（MCMC）采样器。 一个关键的研究步骤是开发离散打了就跑作为一个通用的MCMC采样器的离散域，并将其嵌入到一个广义的自适应搜索框架，以支持希望的多项式时间，平均算法。 许多全局优化的启发式方法，包括模拟退火和遗传算法，将通过严格的方法来确定更好的算法参数和停止准则来加强。 这项研究将发展理论和方法来解决这些问题的一般全局优化问题。 这项工作的智力价值主要在于丰富了全局优化领域，但也可能塑造，因为它在过去，更基本的工作MCMC采样器。这项工作的广泛影响在于为优化复杂工程系统而开发的算法的潜力。 强大的计算机技术的普及提供了一个机会，用软件模拟来准确地模拟复杂的系统，取代传统的封闭形式的数学方程。 由此产生的模型需要强大的优化技术，假设鲜为人知的结构的基础模型。

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.