Moments and sums of squares for nonlinear dynamics on networks – Monet

The ability to optimally control road networks, power grids, canals, gas pipelines, digital networks, and many other networked systems of ever increasing complexity is vital to support our everyday lives. This demands mathematical and computational tools that can handle large-scale network structures as well as nonlinearities in the network’s dynamics. This project will deliver precisely such techniques through a groundbreaking approach based on moment-sum-of-squares (moment-SOS) relaxations. In contrast to standard approaches, we will leverage linear measure-theoretic reformulations of nonlinear network dynamics to recast challenging network analysis and control tasks into computationally tractable semidefinite programs (SDPs). Optimal solutions of these problems can be found efficiently and, crucially, provide certified estimates for the network’s performance. Moreover, the use of measure-theoretic reformulations makes it easy to account for uncertainty in the network dynamics, which is unavoidable in practice. Our approach is promising and realistic: indeed, we have already shown that moment-SOS relaxations outperform classical methods for the analysis and control of ordinary differential equations (ODEs) and hyperbolic partial differential equations (PDEs) with polynomial nonlinearities. We will exploit the network structure to apply moment-SOS relaxations to small subnetworks, leading to sparse SDPs that can be solved efficiently irrespective of the network size. We will investigate the trade-off between the computational savings afforded by subnetwork decomposition and the quality of the performance estimates, identifying in particular network structures for which performance estimates are guaranteed to be sharp. We will also implement our approach in open-source software and illustrate it on an extensive set of examples.