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

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