Optimization Algorithms for Decision Problems with Many Variables

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

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.