Computation of Lyapunov functions for nonlinear discrete systems by linear programming

Giesl, Peter and Hafstein, Sigurdur (2014) Computation of Lyapunov functions for nonlinear discrete systems by linear programming. Journal of Difference Equations and Applications, 20 (4). pp. 610-640. ISSN 1023-6198

[img] PDF - Accepted Version
Download (2MB)


Given an autonomous discrete time system with an equilibrium at the origin and a hypercube D containing the origin, we state a linear programming problem, of which any feasible solution parameterizes a continuous and piecewise affine (CPA) Lyapunov function V : D -> R for the system. The linear programming problem depends on a triangulation of the hypercube. We prove that if the equilibrium at the origin is exponentially stable, the hypercube is a subset of its basin of attraction, and the triangulation fulfils certain properties, then such a linear programming problem possesses a feasible solution. We present an algorithm that generates such linear programming problems for a system, using more and more refined triangulations of the hypercube. In each step the algorithm checks the feasibility of the linear programming problem. This results in an algorithm that is always able to compute a Lyapunov function for a discrete time system with an exponentially stable equilibrium. The domain of the Lyapunov function is only limited by the size of the equilibrium's basin of attraction. The system is assumed to have a right-hand side, but is otherwise arbitrary. Especially, it is not assumed to be of any specific algebraic type such as linear, piecewise affine and so on. Our approach is a non-trivial adaptation of the CPA method to compute Lyapunov functions for continuous time systems to discrete time systems.

Item Type: Article
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Subjects: Q Science > QA Mathematics
Depositing User: Peter Giesl
Date Deposited: 18 Jul 2014 10:55
Last Modified: 06 Mar 2017 05:10

View download statistics for this item

📧 Request an update