Collaborative research: polynomial optimization and its application to power systems

Operators of electric power systems face the difficult task of continuously balancing the supply and demand of power by managing the outputs of thousands of generators and the power flows through tens of thousands of transmission lines. To maintain a reliable and low-cost power supply, system operators rely on algorithms from the field of mathematical optimization. To obtain more tractable mathematical formulations, existing industry practices linearly approximate the nonlinear models which best represent the physics of electric power systems. Optimization problems that use these linear approximations provide operating points which inherently suffer from approximation errors, thus reducing the reliability and efficiency of power system operations. Recent advancements in optimization theory hold significant promise for avoiding these approximation errors by directly solving nonlinear optimization problems. For instance, the Department of Energy and the Federal Energy Regulatory Commission estimate that improved optimization algorithms could save billions of dollars annually in the US electricity markets alone. Modeling power networks as systems of polynomial equations, our preliminary work demonstrated that polynomial optimization theory can reliably provide solutions to challenging nonlinear problems. Building on our preliminary work, this project will develop and analyze new optimization algorithms that provide significant computational speed improvements and additional modeling flexibility. These algorithms and their associated rigorous guarantees on convergence and solution quality are key enabling tools for reliably operating power systems, especially during heavily stressed conditions.

This project aims to develop new semi-algebraic techniques for solving large-scale polynomial optimization problems arising from the operation of electric power systems. Given the increasing complexity of power systems, operational decision-making tools crucially require innovative solutions in the coming years. To achieve this, we propose to design tractable and rigorous algorithms using a powerful tool from polynomial optimization theory known as the moment/sum-of-squares hierarchy. Contrary to local search algorithms, the moment/sum-of-squares hierarchy has global convergence guarantees and cannot get stuck in undesired local minima or saddle points. However, making this hierarchy tractable for practical large-scale problems is a major challenge. We thus propose new semi-algebraic techniques for globally solving an important and generic instance of large-scale polynomial optimization, namely the so-called optimal power flow problem. This problem seeks the minimum cost operating point for an electric power system while satisfying engineering limits on the line flows, voltage magnitudes, etc. as well as the power flow equations which model the network physics. In addition to being an important problem in its own right, optimal power flow is a key building block of more complex problems, including bilevel optimization problems used to model competitive electricity markets and to identify critical power system components. Our preliminary results show that moment/sum-of-squares relaxations can solve practical optimal power flow test cases coming from industry on an unprecedented scale, with thousands of variables and tens of thousands of non-convex constraints. We plan to design new ways to exploit power system specific characteristics (particular symmetries and sparsity) to enable large-scale computations, as well as new hierarchies for solving polynomial optimization problems. Our specific objectives for this project include 1) substantially improving the computational speed of the moment/sum-of-squares hierarchies using recently proposed Lagrange multiplier expressions that systematically strengthen the relaxations, 2) developing methods for quickly checking whether a candidate local solution is, in fact, globally optimal, thus leveraging decades of research in local search algorithms, 3) applying polynomial optimization tools to industrially relevant bilevel optimization problems, where the relaxations global optimality certificates are essential to ensuring feasibility of the overall bilevel problem, and 4) creating new relaxation hierarchies that are tailored to power system specific characteristics while simultaneously exploiting the efficiency of computational methods developed for machine learning applications.

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.