RUI: Robust Feasibility and Robust Optimization using Algebraic Topology and Convex Analysis

在计算数学中，求解方程组和在这样的系统上优化函数是无处不在的。非线性和/或非凸的函数或方程往往使这些任务具有挑战性。此外，问题参数的不确定性增加了问题的复杂性。这类问题普遍存在的现代社会的一个关键部分是电力系统。电力系统运行中的两个核心计算是潮流研究和最优潮流计算。PF研究确保电网状态（即整个网络的电压和流量）将保持在可接受的范围内，尽管有突发事件（例如，发电机或传输线的损失）和其他不确定因素（例如，需求变化或可再生能源，如风能和太阳能）。OPF进一步寻求选择系统中可控制资产的值（例如，发电速率可控制的发电机），以便以最低成本满足需求。这些问题具有固有的非线性和非凸性，使它们难以以自然形式解决。该项目利用代数拓扑和非线性分析的思想来开发有效的鲁棒可行性和鲁棒优化算法。特别是，研究者将开发一个框架，以获得数学上严格的保证，在非线性系统中使用可扩展算法的鲁棒可行性和优化。研究者将使用这些算法来描述电力系统非线性模型中不确定性的影响。研究者还将通过对大规模OPF问题的测试来证明该框架的有效性。风能和太阳能等可再生能源的迅速采用增加了现代电力系统的不确定性。在这个项目中，研究者将采取稳健的不确定性观点：不确定性对可行性和优化问题的最坏影响将被量化。为此，研究者将使用代数拓扑和非线性分析的思想-特别是Borsuk定理（中间值定理的推广）和拓扑度理论-为PF和OPF问题的鲁棒版本开发有效的算法。在计算方面，研究者将开发这些算法的有效实现，能够可扩展地解决PF和OPF问题的大型实例。新的框架将结合严格的保证、高效的算法和处理非线性的能力。这样的框架对于运行具有重大不确定性的现代电力系统至关重要。虽然电力系统被用作主要的应用领域，但所要开发的方法是相当一般的，并且也可以应用于其他领域的问题，例如，气体分配网络。更广泛地说，该项目可能对如何处理复杂和大规模的基础设施系统产生直接影响，特别是在环境造成的不确定性日益增加的情况下。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Solving systems of equations and optimizing a function over such systems are ubiquitous in computational mathematics. The functions or equations being nonlinear and/or nonconvex often make these tasks challenging. Further, uncertainty in problem parameters adds to the problem complexity. A crucial part of modern society where such problems are prevalent is power systems. Two central computations in power systems operations are power flow (PF) studies and optimal power flow (OPF). PF studies ensure the power grid state (i.e., voltages and flows across the network) will remain within acceptable limits in spite of contingencies (e.g., loss of a generator or a transmission line) and other uncertainties (e.g., shifting demand or renewable sources of power such as wind and solar). OPF seeks further to choose values for controllable assets in the system (e.g., generators whose rate of power production could be controlled) so as to meet demand at minimum cost. These problems have inherent nonlinearities and nonconvexities, making them hard to solve in their natural form. This project uses ideas from algebraic topology and nonlinear analysis to develop efficient algorithms for robust feasibility and robust optimization. In particular, the investigator will develop a framework to derive mathematically rigorous guarantees for robust feasibility and optimization in nonlinear systems using scalable algorithms. The investigator will employ these algorithms to characterize the effects of uncertainties in nonlinear models of power systems. The investigator will also demonstrate the efficacy of the framework by testing it on large scale OPF problems.The rapid adoption of renewable energy sources such as wind and solar energy is creating increased uncertainty in modern power systems. In this project, the investigator will take a robust viewpoint of uncertainty: the worst-case impact of the uncertainty on feasibility and optimization problems will be quantified. To this end, the investigator will use ideas from algebraic topology and nonlinear analysis -- specifically Borsuk's theorem (a generalization of the intermediate value theorem) and topological degree theory -- to develop efficient algorithms for robust versions of the PF and OPF problems. On the computational side, the investigator will develop efficient implementations of these algorithms capable of scalably solving large instances of PF and OPF problems. The novel framework will combine rigorous guarantees, efficient algorithms, and the ability to handle nonlinearities. Such a framework is critical for operating modern power systems with significant uncertainty. While power systems are used as the main application area, the methods to be develop are fairly general, and could be applied to problems in other domains as well, e.g., gas distribution networks. More broadly, this project could have a direct impact on how complex and large scale infrastructure systems are handled, especially under increasing uncertainties created by the environment.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.