Automated Synthesis of Lyapunov Functions for Stability Verification

199 concepts177 papers2 proposals

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).

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:

  1. 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$).
  2. 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:

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.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 174 papers
  2. Version 1 · 2026-10-04 · 315 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_lyapunov_function_synthesis_f20deb7b,
  title = {Lyapunov function synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lyapunov-function-synthesis/rdr_f20deb7b4265496780ba677de44dfcd2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_lyapunov_function_synthesis_f20deb7b_v2,
  title = {Lyapunov function synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lyapunov-function-synthesis/rdr_f20deb7b4265496780ba677de44dfcd2/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake