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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Lyapunov Certification as Max-Plus Inference: Exact Decomposition, Scalable Synthesis, and Rigorous Region-of-Attraction Certificates for Large Nonlinear Networks

Yuan Shen
Zenodo (CERN European Organization for Nuclear Research)
Formal Methods in Verification
preprint

Lyapunov Certification as Max-Plus Inference: Exact Decomposition, Scalable Synthesis, and Rigorous Region-of-Attraction Certificates for Large Nonlinear Networks

Yuan Shen
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
University of British Columbia, Okanagan Campus (CA)
Formal Methods in Verification
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon