Optimization Algorithms for Decision Problems with Many Variables

多变量决策问题的优化算法

• 批准号: 1562466
• 负责人: James Calvin
• 金额: $ 27.88万
• 依托单位: New Jersey Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-08-15 至 2020-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1562466&HistoricalAwards=false
• 关键词: Optimization; Algorithms; Decision; Problems; Many

Decision-makers often strive to minimize the cost or maximize the performance of a system that depends on many decision variables. If the decision-maker can quantify the cost as a function of the decision variables, then computational methods can be used to obtain or approximate the optimal decision. For complicated cost functions arising in practice it may not be possible to know for sure that a proposed solution is optimal and one must settle for an approximate solution. Typical examples of such problems include choosing well sites and pumping rates for ground water pollution remediation, aligning medical images taken at different times, and determining the configuration of a collection of atoms that minimizes the potential energy. This award supports research into methods for solving such optimization problems and characterizing their inherent difficulty as the number of decision variables increases. These methods will be applicable to a broad range of problems in engineering, science, and industry.The optimization problems described above are called global optimization problems. It is well-known that global optimization is intractable in high dimensions in the worst-case complexity setting. The investigator will determine if continuous optimization is tractable in an asymptotic or average-case setting by establishing both upper and lower complexity bounds. The investigator will obtain upper complexity bounds by devising new optimization algorithms and proving their convergence rates. The project will use two approaches to algorithm design. One approach is to subdivide the domain into polytopes, and choose new function evaluation points within the polytope that maximize a criterion based on the size of the polytope and the observed function values at its vertices. The other approach is to use randomized point selection schemes that aim to obtain comparable results to the first approach, on average, but without the computational cost of maintaining the polyhedral subdivisions. The lower complexity bounds will establish the smallest error that can be obtained with any algorithm that uses a given average number of function evaluations. A key question that this research will attempt to answer is whether the lower complexity bounds grow exponentially with the dimension.

决策者往往努力使系统的成本最小化或性能最大化，这取决于许多决策变量。如果决策者能够将成本量化为决策变量的函数，则可以使用计算方法来获得或近似最优决策。对于在实践中出现的复杂的成本函数，可能不可能确定地知道所提出的解决方案是最优的，并且必须满足于近似解决方案。此类问题的典型例子包括选择地下水污染修复的井址和抽水率、对齐不同时间拍摄的医学图像以及确定使势能最小化的原子集合的配置。该奖项支持研究解决此类优化问题的方法，并随着决策变量数量的增加，描述其固有的难度。这些方法将适用于工程、科学和工业中的广泛问题。上述优化问题称为全局优化问题。众所周知，在最坏情况复杂度设置下，全局优化在高维中是难以处理的。研究者将通过建立复杂性的上界和下界来确定连续优化在渐近或平均情况下是否易于处理。研究人员将通过设计新的优化算法并证明其收敛速度来获得复杂性上限。该项目将使用两种算法设计方法。一种方法是将域细分为多面体，并在多面体内选择新的函数求值点，该新的函数求值点基于多面体的大小和在其顶点处观察到的函数值来最大化准则。另一种方法是使用随机点选择方案，其目的是获得与第一种方法相当的结果，平均而言，但没有维持多面体细分的计算成本。较低的复杂性界限将建立使用给定平均函数求值数的任何算法可以获得的最小误差。这项研究将试图回答的一个关键问题是，较低的复杂性界限是否随维度呈指数增长。