Compositional Verification of Large-Scale Nonlinear Systems via Sums-of-Squares Optimization
Shen Shen, Russ Tedrake · 2018
We consider the computationally prohibitive problem of stability and invariance verification of large-scale dynamical systems. We exploit the natural interconnected structure often arising from such systems in practice (i.e., they are interconnections of low-dimensional subsystems), and propose a compositional method. We construct independently for each subsystem a Lyapunov-like function, and guarantee that their sum automatically certifies the original high-dimensional system is stable or invariant. For linear time invariant systems, our method produces block-diagonal Lyapunov matrices without structural assumptions commonly found in the literature. For polynomial system tasks, our formulation results in significantly smaller sum-of-squares programs. Demonstrated on numerical and practical examples, our algorithms can handle problems beyond the reach of direct optimizations, and are orders of magnitude faster than existing compositional methods.