Lyapunov Certification as Max-Plus Inference: Exact Decomposition, Scalable Synthesis, and Rigorous Region-of-Attraction Certificates for Large Nonlinear Networks
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. Preprint (submitted manuscript, not peer reviewed) of a paper submitted to IEEE Transactions on Automatic Control. The second file is its Supplementary Material. The code and the complete result files are archived in a separate record (see Related works). The use of AI in this work is declared in the Acknowledgment. Abstract: Verified region-of-attraction (ROA) certificates for nonlinear networks scale poorly with the state dimension, and compositional ones are only sufficient. For Lyapunov candidates that are sums of local terms, the global Lyapunov inequalities are equivalent to local inequalities coupled through messages, functions on the separators of a junction tree: verifying them is a max-plus inference problem. This exactness is classical in nonserial dynamic programming and sparse polynomial optimization. We use it for non-polynomial Lyapunov inequalities, show that polynomial messages suffice despite the degenerate zero at equilibrium, extend it to domains cut by bag-local constraints (line-angle limits), and recover the chordal (Agler) decomposition at the quadratic level. We build a pipeline whose cost per iteration is linear in the number of subsystems: a sound bag-local verifier (outward-rounded interval Taylor bounds), a closing check that needs only a Krawczyk enclosure of the equilibrium, a structured interior-point synthesis whose Newton systems inherit the junction-tree sparsity, and a rigorous ROA ball by max-plus dynamic programming. On lossy power networks with bulk-grid ties at every bus, we certify first-order chains with up to 3·10⁴ buses in 71 minutes, second-order (virtual-synchronous-machine) chains with up to 10³ buses, current-limited inverter networks with up to 10³ (first order) and 300 (second order) buses, the IEEE 123-bus (radial and looped) and 8500-node feeder topologies, and rings of up to 10³ buses. The certified regions are conservative for second-order dynamics, and weaker ties cost more iterations. Certificates of up to 3·10⁴ buses pass independent re-verification.
Authors
- Yuan Shen
Institutions
- University of British Columbia, Okanagan Campus (CA)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24331674
- Primary Topic
- Formal Methods in Verification
- Type
- preprint