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

主要联邦机构，包括退伍军人事务部、国防部、国土安全部、联邦航空管理局、财政部、国税局、医疗保险和医疗补助服务中心、卫生与公众服务部等，寻求政府和非政府援助，应用科学的、数据驱动的方法，帮助他们有效地执行关键任务。由于他们的任务通常是大规模、复杂的，并且涉及固有的不确定性，因此计算机模拟通常是以全面的方式表示他们的问题的唯一工具。类似的问题也出现在私营部门，特别是在医疗保健服务、计算机网络、仓储和配送以及运输系统方面。不幸的是，“大规模、复杂且涉及固有的不确定性”是使“优化”模拟系统变得困难的特征，特别是当决策是如何分配离散的资源单元（例如人员、车辆和设施）时。拟议的研究将高性能计算、智能数值方法和最先进的统计方法结合起来，显着增加可优化的模拟系统的规模和复杂性。因此，上述机构将能够使用计算机模拟更全面地解决其“系统的系统”资源分配问题。所提出的研究解决了在解决大规模随机优化问题时出现的统计和计算挑战，而目标函数只能通过执行随机模拟来评估。此类优化问题通常涉及大解空间中的高维、离散值决策变量。仿真的建模灵活性是有代价的：任意复杂的随机仿真可能无法使用数学编程工具进行优化。因此，目前通过具有最优性差距保证的模拟可以解决的问题规模是有限的。研究人员建议创建用于大规模离散决策变量模拟优化的理论、算法和软件，渐进地收敛到全局最优，并在终止时提供最优性差距推理。所提出的方法基于推理优化，通过高斯马尔可夫随机场（GMRF）对未知目标函数进行建模，GMRF 是一种由离散解空间上的图定义的高斯过程；研究人员表明，与在连续域上定义的高斯过程相比，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.