Stability and Performance Verification of Dynamical Systems Controlled by Neural Networks: Algorithms and Complexity

This letter makes several contributions on stability and performance verification of nonlinear dynamical systems controlled by neural networks. First, we show that the stability and performance of a polynomial dynamical system controlled by a neural network with semialgebraically representable activation functions (e.g., ReLU) can be certified by convex semidefinite programming. The result is based on the fact that the semialgebraic representation of the activation functions and polynomial dynamics allows one to search for a Lyapunov function using polynomial sum-of-squares methods. Second, we remark that even in the case of a linear system controlled by a neural network with ReLU activation functions, the problem of verifying asymptotic stability is undecidable. Finally, under additional assumptions, we establish a converse result on the existence of a polynomial Lyapunov function for this class of systems. Numerical results with code available online on examples of state-space dimension up to 50 and neural networks with several hundred neurons and up to 30 layers demonstrate the method.

I. Introduction

The recent wide-spread success and adoption of neural networks in machine learning naturally lead to their applications in safety-critical domains such aerospace or automotive, thereby raising questions of safety. This letter addresses this question in the setting of nonlinear dynamical systems controlled by neural network controllers (see Figure 1). We present a method to certify stability of this closed-loop interconnection using convex semidefinite programming (SDP), under the assumption that the dynamics is polynomial and the activation functions in the neural network are semialgebraically representable (e.g., ReLU). Similarly, we derive SDPs that yield bounds on performance in terms of the nonlinear gain or assess robustness and input-to-state stability. Fig. 1.

Nonlinear dynamical system controlled by a neural network.