Algorithms and Complexity for Global Optimization

全局优化的算法和复杂性

• 批准号: 0825381
• 负责人: James Calvin
• 金额: $ 26万
• 依托单位: New Jersey Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0825381&HistoricalAwards=false
• 关键词: Algorithms; Complexity; 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.

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