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

协作研究：通过仿真实现大规模离散优化的自适应高斯马尔可夫随机场

基本信息

批准号：
1854659
负责人：
Eunhye Song
金额：
$ 14万
依托单位：
Pennsylvania State Univ University Park
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-07-15 至 2022-11-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1854659&HistoricalAwards=false
关键词：
Collaborative Research Adaptive Gaussian Markov

项目摘要

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.

主要的联邦机构，包括退伍军人事务部，国防部，国土安全部，联邦航空管理局，财政部，国税局部，医疗保险和医疗补助服务中心，卫生与公共服务部，卫生与公共服务部以及其他人，寻求政府和非政府援助，以帮助他们在科学，数据驱动的方法上有效地执行有效地执行他们的关键措施。由于他们的任务通常是大规模，复杂的，并且涉及固有的不确定性，因此计算机模拟通常是以全面的方式来表示问题的唯一工具。私营部门，尤其是在医疗保健，计算机网络，仓库和分销以及运输系统中发生的类似问题。不幸的是，“大规模，复杂且涉及固有的不确定性”是使“优化”模拟系统努力的功能，尤其是当决策是如何分配人员，车辆，车辆和设施等资源的离散单位时。拟议的研究结合了高性能计算，智能数值方法和最先进的统计方法，以显着提高可以优化的模拟系统的大小和复杂性。结果，诸如上面列出的机构将能够使用计算机模拟更加充分地解决其“系统系统”资源分配问题。拟议的研究解决了仅当仅通过执行随机模拟来评估目标函数时，才能解决大规模的随机功能时出现的统计和计算挑战。这种优化问题通常是关于大型解决方案空间中高维，离散价值的决策变量的。模拟的建模灵活性是有代价的：使用数学编程中的工具，可能不会优化任意复杂的随机模拟。结果，当前可以通过具有最佳差距保证的模拟解决的问题的规模是有限的。调查人员建议为大规模离散 - 否定变量的模拟优化创建理论，算法和软件，从而收敛到全局最佳最佳最佳，并在终止时提供最佳的差距推断。所提出的方法基于推论优化，该方法通过高斯Markov随机场（GMRF）建模未知目标函数，这是一种由离散解决方案空间上图定义的高斯过程。研究人员表明，与连续域上定义的高斯过程相比，GMRF为离散问题提供了更好的推论。 GMRF的条件分布提供了选择解决方案以模拟和搜索终止的推断，当时推断的最佳差距很小。但是，数值线性代数的计算成本比可行解决方案的数量更快。为了促进大规模问题的解决方案，提出了三个核心主题：利用高性能计算；创建一个受限制的搜索方案和量身定制的计算线性代数，该代数可大大减少GMRF更新中的计算；并通过自适应多分辨率GMRF和降低维度的预测来攻击维度的限制。该奖项将通过研究为研究生培训提供支持。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响审查标准的评估来支持的。