Counterexample-guided computation of polyhedral Lyapunov functions for piecewise linear systems
(2023) Automatica — Vol. 155, n° 111165, p. 1-10 (2023)
Files
1-s20-S0005109823003266-main.pdf
Open Access - Adobe PDF
- 1.12 MB
Details
- Authors
- Abstract
- This paper presents a counterexample-guided iterative algorithm to compute convex, piecewise linear (polyhedral) Lyapunov functions for continuous-time piecewise linear systems. Polyhedral Lyapunov functions provide an alternative to commonly used polynomial Lyapunov functions. Our approach first characterizes intrinsic properties of a polyhedral Lyapunov function including its ``eccentricity'' and ``robustness'' to perturbations. We then derive an algorithm that either computes a polyhedral Lyapunov function proving that the system is asymptotically stable, or concludes that no polyhedral Lyapunov function exists whose eccentricity and robustness parameters satisfy some user-provided limits. Significantly, our approach places no a-priori bound on the number of linear pieces that make up the desired polyhedral Lyapunov function. The algorithm alternates between a learning step and a verification step, always maintaining a finite set of witness states. The learning step solves a linear program to compute a candidate Lyapunov function compatible with a finite set of witness states. In the verification step, our approach verifies whether the candidate Lyapunov function is a valid Lyapunov function for the system. If verification fails, we obtain a new witness. We prove a theoretical bound on the maximum number of iterations needed by our algorithm. We demonstrate the applicability of the algorithm on numerical examples.
- Affiliations
Citations
Berger, G., & Sankaranarayanan, S. (2023). Counterexample-guided computation of polyhedral Lyapunov functions for piecewise linear systems. Automatica, 155(111165), 1-10. https://doi.org/10.1016/j.automatica.2023.111165 (Original work published 2023)