Collaborative Research: Adaptive Gaussian Markov Random Fields for Large-scale Discrete Optimization via Simulation

包括退伍军人事务部、国防部、国土安全部、联邦航空管理局、财政部、国税局、医疗保险和医疗补助服务中心、卫生与公众服务部等在内的主要联邦机构通过应用科学的、数据驱动的方法寻求政府和非政府机构的帮助，以帮助他们有效地执行关键任务。由于他们的任务通常是大规模的、复杂的，并且涉及内在的不确定性，计算机模拟往往是唯一全面地表现他们的问题的工具。类似的问题也出现在私营部门，特别是在医疗保健提供、计算机网络、仓储和配送以及运输系统方面。不幸的是，“大规模、复杂且涉及内在不确定性”的特征使得“优化”模拟系统变得困难，特别是当决策是如何分配离散的资源单元时，例如人员、车辆和设施。拟议的研究结合了高性能计算、智能数值方法和最先进的统计方法，以显著增加可优化的模拟系统的规模和复杂性。因此，上述机构将能够更充分地利用计算机模拟来解决他们的系统系统资源分配问题。所提出的研究解决了当目标函数只能通过执行随机模拟来评估时，在解决大规模随机优化问题时出现的统计和计算挑战。这样的优化问题通常是关于大的解空间中的高维、离散值的决策变量。模拟的建模灵活性是有代价的：任意复杂的随机模拟可能无法使用数学规划中的工具进行优化。因此，目前可以通过模拟在最优差距保证下解决的问题的规模是有限的。研究人员建议建立大规模离散决策变量仿真优化的理论、算法和软件，使其渐近收敛于全局最优，并在终止时提供最优缺口推理。所提出的方法是基于推理优化的，它用高斯马尔可夫随机场(GMRF)对未知目标函数进行建模，高斯马尔可夫随机场是由离散解空间上的图定义的一种高斯过程；研究人员已经证明，高斯马尔可夫随机场比定义在连续区域上的高斯过程对离散问题提供了更好的推理。GMRF的条件分布为选择要模拟的解和当推断的最优间隔较小时用于搜索终止提供了推理。然而，数值线性代数的计算代价比可行解的数目增加得更快。为了促进大规模问题的解决，提出了三个核心主题：利用高性能计算；创建受限搜索方案和定制的计算线性代数，显著减少GMRF更新中的计算量；通过自适应多分辨率GMRF和向低维的投影来攻击维度限制。这一奖项将通过研究为研究生培养提供支持。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Major federal agencies, including the Department of Veterans Affairs, Department of Defense, Department of Homeland Security, Federal Aviation Administration, Department of the Treasury, Internal Revenue Service, Centers for Medicare and Medicaid Services, Department of Health and Human Services, and others, seek government and non-government assistance with the application of scientific, data-driven methods to help them execute effectively on their critical missions. Because their mandate is typically large-scale, complex, and involves inherent uncertainty, computer simulation is often the only tool for representing their problems in a comprehensive way. Similar problems occur in the private sector, especially in health care delivery, computer networks, warehousing and distribution, and transportation systems. Unfortunately, "large-scale, complex, and involving inherent uncertainty" are the features that make "optimizing" a simulated system hard, particularly when the decisions are how to allocate discrete units of resources such as personnel, vehicles and facilities. The proposed research marries high-performance computing, smart numerical methods, and state-of-the-art statistical methodology to significantly increase the size and complexity of simulated systems that can be optimized. As a result, agencies such as those listed above will be able to more fully solve their "system of systems" resource-allocation problems using computer simulation.The proposed research tackles statistical and computational challenges that arise in solving large-scale stochastic optimization problems when the objective function may only be evaluated by executing a stochastic simulation. Such optimization problems are often with respect to a high-dimensional, discrete-valued decision variable in a large solution space. The modeling flexibility of simulation comes at a cost: arbitrarily complex stochastic simulations may not be optimized using tools from mathematical programming. As a result, the scale of problems that can currently be solved by simulation with an optimality gap guarantee is limited. The investigators propose to create theory, algorithms and software for large-scale discrete-decision-variable simulation optimization that converge to the global optimum asymptotically, and provide optimality-gap inference when terminated. The proposed methods are based on inferential optimization, which models the unknown objective function by a Gaussian Markov Random Field (GMRF), a type of Gaussian Process defined by a graph on the discrete solution space; the investigators have shown that GMRFs provide better inference for a discrete problems than Gaussian processes defined on a continuous domain. The conditional distribution of a GMRF provides inference for selecting solutions to simulate and for search termination when the inferred optimality gap is small. However, the computational cost of numerical linear algebra increases faster than the number of feasible solutions. To facilitate the solution of large-scale problems, three core topics are proposed: exploiting high-performance computing; creating a restricted search scheme and tailored computational linear algebra that significantly reduces the computations in GMRF updates; and attacking limits on dimensionality via an adaptive multi-resolution GMRF and projections to lower dimensions. This award will provide support of graduate student training through research.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.