AF: Small: Incremental and Asynchronous Projective Splitting Methods for Mathematical Programming

AF：小：数学规划的增量和异步投影分裂方法

• 批准号: 1617617
• 负责人: Jonathan Eckstein
• 金额: $ 45.71万
• 依托单位: Rutgers University Newark
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1617617&HistoricalAwards=false
• 关键词: AF; Small; Incremental; Asynchronous; Projective

A key to solving large computational and mathematical problems, such as analyzing large datasets or planning for the operation of an electrical power grid or any other complicated systems with an uncertain future demands and supplies, is decomposing into smaller solvable subproblems or subsystems, then coordinating and integrating their results, and decomposing again into adjusted subproblems. Properly designed decomposition methods repeat a decomposition - coordination cycle that converge to the solution of the entire original, non-decomposed problem. The PI is working with Sandia National Laboratories and has particular interest in problems that arise in operating electrical power grids with high penetration of renewable generation sources, like solar and wind, where weather has unplanned affects the supply. This project studies a new way to perform decomposition, called "incremental projective operator splitting" (IPOS) or "block-iterative splitting." It is related to a popular decomposition method called the alternating direction method of multipliers (ADMM) but is far more flexible. While essentially all prior decomposition methods follow a rigid cycle of decomposition and coordination steps, with every decomposition step encompassing all the subsystems, the new method has much greater flexibility: only a subset of subsystems need to be considered between coordination steps, and decomposition and coordination calculations can overlap asynchronously. This flexibility should allow more efficient use of parallel computers by eliminating rigid synchronization points. This property is important because most future growth in computer performance is anticipated to result from larger numbers of parallel processing units, and only parallel computers will be able to manipulate the large datasets and decision problems we hope to analyze. Because the new IPOS methods are so flexible, there are numerous ways in which they could be used on the same class of problems. The main goal of this project is to develop and experimentally evaluate strategies for applying IPOS on parallel computers. It will focus on two common problem classes, large-scale data analysis and planning under uncertainty, using real-world input data to the maximum practical extent. Other research topics include sharpening the mathematical theory of IPOS, and extending this theory to cover a broader range of problems, and development and release of software based on this new theory.

解决大型计算和数学问题的关键，例如分析大型数据集或规划电网或具有不确定未来需求和供应的任何其他复杂系统的操作，是分解成较小的可解子问题或子系统，然后协调和整合它们的结果，并再次分解成调整的子问题。 正确设计的分解方法重复分解-协调循环，收敛到整个原始未分解问题的解决方案。 PI正在与桑迪亚国家实验室合作，并对可再生能源（如太阳能和风能）高度渗透的电网运行中出现的问题特别感兴趣，其中天气会对供应产生计划外影响。 本计画研究一种新的分解方法，称为“增量投影算子分裂”（IPOS）或“区块迭代分裂”。“它与一种流行的分解方法有关，称为交替方向乘法器（ADMM），但更灵活。 虽然基本上所有先前的分解方法都遵循分解和协调步骤的刚性循环，每个分解步骤都包含所有子系统，但新方法具有更大的灵活性：在协调步骤之间只需要考虑子系统的子集，并且分解和协调计算可以异步重叠。 这种灵活性应该允许通过消除刚性同步点来更有效地使用并行计算机。 这一特性很重要，因为预计未来计算机性能的大部分增长将来自大量的并行处理单元，只有并行计算机才能够处理我们希望分析的大型数据集和决策问题。由于新的IPOS方法是如此灵活，有许多方法可以用于同一类问题。 这个项目的主要目标是开发和实验评估的策略应用IPOS并行计算机。 它将集中在两个常见的问题类，大规模数据分析和规划下的不确定性，使用真实世界的输入数据，以最大的实用程度。 其他研究课题包括锐化IPOS的数学理论，并将此理论扩展到更广泛的问题，以及基于此新理论的软件开发和发布。