Algorithms and Complexity for Global Optimization

该补助金为数值算法的开发提供资金，用于近似具有许多局部最优值的性能指标的全局最优值。该方法是基于建模的未知性能指标作为一个随机函数，然后开发确定性算法，最大限度地减少平均近似误差。这项研究将包括两个主要部分。第一个组成部分将是为不同类型的可用信息和不同类别的目标函数，包括具有各种阶次可微性的连续函数，构建算法。信息的类型将包括：精确函数求值、导数求值和被随机噪声破坏的函数求值。研究的第二部分将是确定复杂性界限。对于给定的问题设置，例如具有精确函数求值的连续函数，研究者将建立任何算法可以达到的最小平均误差的界限。如果成功，本项目中开发的算法将对两种主要类型的问题有用。第一个应用是对具有连续参数的复杂系统的优化，其中系统性能可以精确地评估，并且不需要诸如性能度量的单峰性或凸性之类的假设。这些问题包括优化地下水污染处理方案和分子几何优化。第二类问题是系统的优化，其中性能只能被随机噪声破坏。例如，当所研究的系统的性能只能使用随机离散事件模拟来估计时，就会出现这种情况。在这两种情况下，复杂性界限将指示问题是否易于处理，并提供关于给定算法接近最优程度的指导。

This grant provides funding for the development of numerical algorithms for approximating the global optimum of performance measures that can have many local optima. The approach is based on modeling the unknown performance measure as a random function, and then developing deterministic algorithms that minimize the average approximation error. The research will comprise two main components. The first component will be to construct algorithms for different types of available information and different classes of objective functions, including continuous functions with various orders of differentiability. The types of information will include: exact function evaluations, derivative evaluations, and function evaluations corrupted by random noise. The second part of the research will be to determine complexity bounds. For a given problem setting, for example continuous functions with exact function evaluations, the investigator will establish bounds on the smallest average error that can be attained with any algorithm.If successful, the algorithms developed in this project will be useful for two main types of problems. The first application is to the optimization of complex systems with continuous parameters where the system performance can be evaluated exactly and assumptions such as unimodality or convexity of the performance measure are not warranted. Such problems include optimizing groundwater contamination treatment plans and molecular geometry optimization. The second class of problems is the optimization of systems where the performance can only be observed corrupted by random noise. Such situations arise, for example, when the performance of the system being studied can only be estimated using a stochastic discrete-event simulation. In both cases the complexity bounds will indicate if a problem is tractable and provide guidance on how near to optimal a given algorithm is.