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.