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.