To understand whether a dynamical system is stable, imagine a ball rolling inside a smooth bowl. No matter where you drop the ball, it eventually slides down and settles at the very bottom. In control theory, this bowl is formalized as a Lyapunov function: a scalar-valued function $V(x)$ that is strictly positive everywhere except at the target equilibrium point ($V(0) = 0$), and whose value strictly decreases along the system's trajectories ($\dot{V}(x) < 0$). Finding such a function provides an absolute mathematical guarantee—a certificate—that the system will safely converge.
However, for complex, nonlinear, or high-dimensional systems, discovering this "bowl" is notoriously difficult. As noted by Giordano Pola et al. in Approximately bisimilar symbolic models for nonlinear control systems and Sven Knüfer et al. in Time-Discounted Incremental Input/Output-to-State Stability, constructing these functions has historically been a manual, trial-and-error process driven by human intuition. When dynamics become highly irregular, non-polynomial, or black-box, human intuition fails, creating a severe bottleneck in verifying critical infrastructure like power grids (Wenqi Cui et al. in Lyapunov-Regularized Reinforcement Learning for Power System Transient Stability).
From Manual Templates to Optimization-Driven Search
To move away from manual guessing, researchers initially turned to structured optimization. If we restrict our candidate Lyapunov function to a specific mathematical form, can a computer find the coefficients for us?
One powerful approach is Sum-of-Squares (SOS) optimization. By framing the Lyapunov conditions as a problem of ensuring certain polynomials are always non-negative, the search can be cast as a Semidefinite Program (SDP) and solved algorithmically. For instance, Aditya Gahlawat et al. applied this to linear partial differential equations in A Semi-Definite Programming Approach to Stability Analysis of Linear Partial Differential Equations, while Reza Kamyar et al. used Handelman's theorem to construct piecewise-polynomial Lyapunov functions in Constructing piecewise-polynomial lyapunov functions for local stability of nonlinear systems using Handelman's theorem. Furthermore, Elias August et al. demonstrated in Finding positively invariant sets and proving exponential stability of limit cycles using Sum-of-Squares decompositions how SOS can automatically isolate trapped regions of state space (positively invariant sets) and prove the stability of complex limit cycles.
Yet, template-based methods have a fundamental limitation: they require the user to guess the degree or structure of the polynomial beforehand. If the true energy landscape of a system is non-polynomial or highly intricate, a simple polynomial template might not exist, leaving the optimization problem infeasible (Sicun Gao et al. in Numerically-Robust Inductive Proof Rules for Continuous Dynamical Systems).
The Modern Paradigm: Learner-Verifier Loops
To break free from rigid templates, the field has shifted toward a machine-learning-driven paradigm: Counterexample-Guided Inductive Synthesis (CEGIS). Instead of guessing a formula, we train a highly flexible parametric model—typically a neural network—to act as the Lyapunov candidate, creating a Lyapunov Neural Network (LNN).
The core mechanism operates as a closed-loop game between two entities:
- The Learner: A neural network proposes a candidate function $V(x)$ by minimizing a loss function that penalizes violations of the Lyapunov conditions (e.g., instances where $V(x) \le 0$ or $\dot{V}(x) \ge 0$).
- The Verifier: A formal verification tool—such as a Satisfiability Modulo Theories (SMT) solver or an SOS verifier—searches the continuous state space to find any point where the candidate fails the strict mathematical requirements.
┌──────────────────────────────────────┐
│ LEARNER │
│ Trains Neural Network V(x) │
└──────────────────┬───────────────────┘
│
Candidate │ Counterexamples
Function │ (Failure Points)
▼
┌──────────────────────────────────────┐
│ VERIFIER │
│ Searches for Lyapunov Violations │
└──────────────────┬───────────────────┘
│
▼ No Violations Found?
[ Formal Proof Achieved ]
If the verifier finds a failure point (a counterexample), it passes this point back to the learner. The learner updates its weights to fix the violation, and the loop repeats until the verifier can prove that absolutely no counterexamples exist.
Why does this work so effectively? It decouples discovery from verification. The neural network leverages its universal approximation power to warp and shape a complex energy landscape around highly nonlinear dynamics (Ryosuke Kojima in Learning Deep Input-Output Stable Dynamics). Meanwhile, the symbolic verifier ensures that despite using a "black-box" neural network, the final certificate is mathematically bulletproof. Tools like FOSSIL, developed by Alessandro Abate et al. in A Software Tool for the Formal Synthesis of Lyapunov Functions and Barrier Certificates using Neural Networks, and frameworks like SynNLF by Hanrui Zhao et al. in Learning-enabled Polynomial Lyapunov Function Synthesis via High-Accuracy Counterexample-Guided Framework have formalized this loop, enabling automated, high-accuracy synthesis for systems that defy manual analysis.
Broadening the Certificate Horizon
The impact of automated synthesis extends far beyond standard stability. The same algorithmic principles are being adapted to discover related certificates across control theory and optimization:
- Control and Safety: When designing controllers, finding a Control Lyapunov Function (CLF) allows for simultaneous controller synthesis and stability verification. Alec Reed demonstrated this by using Neural CLFs for provably stable vehicle path following in Verified Path Following Using Neural Control Lyapunov Functions. When safety constraints are added, these are paired with Control Barrier Functions (CBFs) to guarantee that a system never enters unsafe regions (Chuchu Fan et al. in Fast and Guaranteed Safe Controller Synthesis for Nonlinear Vehicle Models; Pol Mestres et al. in Feasibility and Regularity Analysis of Safe Stabilizing Controllers under Uncertainty). Even when global certificates are impossible, Kehan Long showed in Stabilization of Nonlinear Systems through Control Barrier Functions that weak CLFs can be combined with barrier functions to force systems into local regions of stability.
- Dissipativity and Storage Functions: In economic model predictive control and passivity analysis, researchers look for "storage functions" to prove a system dissipates energy. Arash Bahari Kordabad leveraged Q-learning to evaluate these storage functions for non-polynomial systems in Verification of Dissipativity and Evaluation of Storage Function in Economic Nonlinear MPC using Q-Learning, bypassing analytical intractability.
- Optimization Algorithms: Beyond physical hardware, optimization algorithms themselves can be viewed as discrete dynamical systems. Bin Hu et al. showed in Dissipativity Theory for Nesterov's Accelerated Method that dissipativity theory can automate convergence proofs for accelerated methods like Nesterov's method, reducing what used to be highly complex, ad-hoc algebraic proofs (Ernest K. Ryu et al. in Finding the Forward-Douglas-Rachford-Forward Method) to solvable matrix inequalities.
By shifting from manual mathematical derivation to automated, learner-verifier optimization loops, the synthesis of Lyapunov certificates has evolved from a rare art form into a scalable, rigorous engineering tool.