Certifying Lyapunov Stability of Black-Box Nonlinear Systems via Counterexample Guided Synthesis (Extended Version)

Chiao Hsieh, Masaki Waga, Kohei Suenaga · 2025

Read Certifying Lyapunov Stability of Black-Box Nonlinear Systems via Counterexample Guided Synthesis (Extended Version) by Chiao Hsieh, Masaki Waga, Kohei Suenaga (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00431.txt.

Introduction

Proving that a control system is stable usually needs a full model of its motion, and a 2025 paper by Chiao Hsieh, Masaki Waga, and Kohei Suenaga removes that need. Their target is black-box systems, whose inner rules are hidden, a growing case as learned controllers spread into safety-critical work.

The method hunts for a Lyapunov function, the energy-like score whose steady fall proves stability. Instead of approximating the unknown dynamics, it approximates the score's rate of change directly, using samples and a smoothness bound. A learner proposes the score, and a verifier hunts for counterexamples that guide where to sample next. Regional checks focus the search, making the final certificate strong rather than statistical.

Catalog record

CREATORChiao Hsieh, Masaki Waga, Kohei Suenaga
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00431

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Certifying Lyapunov Stability of Black-Box Nonlinear Systems via Counterexample Guided Synthesis (Extended Version) Chiao Hsieh, Masaki Waga, Kohei Suenaga Abstract Finding Lyapunov functions to certify the stability of control systems has been an important topic for verifying safety-critical systems. Most existing methods on finding Lyapunov functions require access to the dynamics of the system. Accurately describing the complete dynamics of a control system however remains highly challenging in practice. Latest trend of using learning-enabled control systems further reduces the transparency. Hence, a method for black-box systems would have much wider applications. Our work stems from the recent idea of sampling and exploiting Lipschitz continuity to approximate the unknown dynamics. Given Lipschitz constants, one can derive a non-statistical upper bounds on approximation errors; hence a strong certification on this approximation can certify the unknown dynamics. We significantly improve this idea by directly approximating the Lie derivative of Lyapunov functions instead of the dynamics. We propose a framework based on the learner–verifier architecture from Counterexample-Guided Inductive Synthesis ( CEGIS ). Our insight of combining regional verification conditions and counterexample-guided sampling enables a guided search for samples to prove stability region-by-region. Our CEGIS algorithm further ensures termination. Our numerical experiments suggest that it is possible to prove the stability of 2D and 3D systems with a few thousands of samples. Our visualization also reveals the regions where the stability is difficult to prove. In comparison with the existing black-box approach, our approach at the best case requires less than 0.01% of samples. 1 Introduction Learner ( Section 4 ) Propose V_{\boldsymbol{\uptheta}} compatible with samples S Verifier ( Section 3 ) Check V_{{\boldsymbol{\uptheta}}} w.r.t Conditions ( 2 ) and ( 3 ) Obtain {\bar{\mathbf{y}}}=f({\bar{\mathbf{x}}}) for each {\bar{\mathbf{x}}}\in X_{c} Add samples S\leftarrow S\cup S_{c} Initial S Candidate V_{\boldsymbol{\uptheta}} CEX States X_{c} New Samples S_{c} S Figure 1: Architecture of CEGIS of Lyapunov functions. Lyapunov method is a powerful tool for dynamical system analysis. The existence of a Lyapunov function allows the study of important properties of the system, such as stability or positive invariants [ 25 ] . Even though the well-known Lyapunov theorems were proposed more than a century ago, the importance of Lyapunov method has led to a large amount of research for automated discovery of Lyapunov functions for a given system [ 20 ] . The major limitation of existing methods is that they usually assume the dynamical system is a white-box model, such as ordinary differential equations (ODE). In practice, however, models are rare and often a mixture of ODEs, simulation code, and observed data. A method for black-box systems that uses input, output, or partial information is more viable. Up until recently, Zhou et al. [ 36 ] proposed a data-driven method for stability and Lyapunov-based control for black-box systems. The main idea of their method is to use evenly-spaced samples to construct an approximation and synthesize a Lyapunov function with the approximation. If the black-box system is Lipschitz continuous and the set of the samples is dense enough, then the correctness of the Lyapunov function is formally guaranteed in a non-statistical way. However, their method requires an excessive number of samples to achieve the formal guarantee. Indeed, for example, 9 million samples are used in [ 36 ] for showing the stability of the Van der Pol oscillator, a second-order 2D system. Our goal is to reduce the number of samples and still show the stability under the Lipschitz continuity assumption. Our main insight is as follows: Not every region in the state space requires the same density of samples. We, therefore, aim to lazily sample the state space following the Counterexample-Guide Inductive Synthesis ( CEGIS ) framework [ 32 ] . In the context of Lyapunov function synthesis, the CEGIS framework is a search strategy for finding valid Lyapunov functions. It is formalized as the interaction between a learner and a verifier . The learner proposes a candidate function, and the verifier checks if the candidate is a valid Lyapunov function for the given dynamics. If the candidate is valid, then we found a Lyapunov function certifying the stability. Otherwise, a counterexample falsifying the candidate is generated, and the learner proposes a new candidate accounting for the counterexample. Fig. 1 describes the overall flow of our CEGIS algorithm. The crucial feature and the novelty of our CEGIS is the regional verification condition for our verifier to check the validity of a candidate with respect to a black-box system. Our regional verification condition proves the formal stability through sampling the black-box system, and it supports lazy sampling and avoids the need for evenly-spaced sampling. This enables counterexample-guided sampling to obtain new samples only when necessary. We further establish the theorems to show that lazy sampling can be as powerful as evenly-spaced sampling. We also provide the termination of our CEGIS algorithm: Our CEGIS algorithm either synthesizes or shows the absence of a Lyapunov function in the hypothesis space of candidates. We implemented a prototype of our CEGIS algorithm and evaluated it with benchmarks from the literature [ 1 , 36 ] . Our experiment shows our prototype can synthesize a Lyapunov function with a few thousand of samples for 2D and 3D systems, and it at best uses less than 0.01% of samples compared with [ 36 ] . We summarize our main contributions as follows: 1. We propose a CEGIS -based algorithm to synthesize Lyapunov functions for certifying the stability of black-box systems. Our verifier uses a novel black-box regional verification condition to check the validity of a candidate. 2. We prove that our CEGIS algorithm either synthesizes a Lyapunov function or shows the absence of a true Lyapunov function in the hypothesis space. Our design of the hypothesis space for learning and the analytic center-based learner ensures the termination according to convex optimization theories. 3. We implemented a prototype and evaluated our CEGIS algorithm with existing benchmarks. The result demonstrates the effectiveness of our algorithm; it, at best, uses less than 0.01% of samples compared with the existing work. Paper Organization In Section 2 , we review dynamical systems, Lipschitz continuity, Lyapunov stability criteria, an overview of CEGIS methods, and the convex feasibility problem. In Section 3 , we introduce our regional verification conditions for certifying Lyapunov stability for black-box systems. In Section 4 , we provide our choice of the hypothesis space and the learner design. In Section 5 , we provide our CEGIS algorithm and proof for its termination. We discuss our experiments on nonlinear systems in Section 6 and conclude in Section 7 . 1.1 Related Works Table 1: Comparison on CEGIS of Lyapunov functions: “BB” stands for “Black-Box Systems”, “Term.” stands for “Termination”, and “CS” stands for “Control Synthesis”. Approaches BB Term. CS FOSSIL [ 3 , 2 , 1 ] Chang et al. [ 10 ] ✓ Chen et al. [ 12 , 11 ] ✓ Berger et al. [ 5 , 6 ] ✓ Masti et al. [ 26 ] ✓ ✓ Ravanbakhsh et al. [ 27 , 28 , 29 , 30 ] ✓ ✓ Zhou et al. [ 36 ] ✓ ✓ Ours ✓ ✓ Finding Lyapunov functions for white-box systems has been an active research topic since the

Read the complete text