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

Washington State University, Pullman WA

Investigators

Abstract

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.