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

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

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.