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.