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

点击翻译按钮获取中文摘要

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.