Computation of Lyapunov functions for nonlinear discrete time systems by linear programming. (English) Zbl 1319.39010
Summary: Given an autonomous discrete time system with an equilibrium at the origin and a hypercube \(\mathcal 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:\mathcal D\to \mathbb 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 \(C^2\) 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.
MSC:
| 39A30 | Stability theory for difference equations |
| 90C90 | Applications of mathematical programming |
| 90C05 | Linear programming |
References:
| [1] | R.Agarwal, Difference Equations and Inequalities: Theory, Methods, and Applications, 2nd ed., Marcal Dekker, Inc., New York, 2000. · Zbl 0952.39001 |
| [2] | R.Baier, L.Grüne, and S.Hafstein, Computing Lyapunov functions for strongly asymptotically stable differential inclusions, in Proceedings of the 8th IFAC Symposium on Nonlinear Control, Bologna, Italy, 2010. · doi:10.3182/20100901-3-IT-2016.00132 |
| [3] | DOI: 10.3934/dcdsb.2012.17.33 · Zbl 1235.93222 · doi:10.3934/dcdsb.2012.17.33 |
| [4] | DOI: 10.1115/1.2338651 · doi:10.1115/1.2338651 |
| [5] | DOI: 10.1080/00207177808922369 · Zbl 0379.65018 · doi:10.1080/00207177808922369 |
| [6] | DOI: 10.1145/361573.361582 · Zbl 1372.65121 · doi:10.1145/361573.361582 |
| [7] | DOI: 10.1017/CBO9780511543241 · Zbl 1038.41001 · doi:10.1017/CBO9780511543241 |
| [8] | C.Conley, Isolated invariant sets and the Morse index, in CBMS, Vol. 38, American Mathematical Society, Providence, R.I., 1978. · Zbl 0397.34056 |
| [9] | DOI: 10.1109/TAC.2002.800666 · Zbl 1364.93563 · doi:10.1109/TAC.2002.800666 |
| [10] | DOI: 10.1080/10236190601135209 · Zbl 1120.39018 · doi:10.1080/10236190601135209 |
| [11] | DOI: 10.1016/j.jat.2008.01.007 · Zbl 1162.39006 · doi:10.1016/j.jat.2008.01.007 |
| [12] | DOI: 10.1016/j.jmaa.2010.05.009 · Zbl 1205.34064 · doi:10.1016/j.jmaa.2010.05.009 |
| [13] | DOI: 10.1016/j.jmaa.2011.10.047 · Zbl 1248.34083 · doi:10.1016/j.jmaa.2011.10.047 |
| [14] | DOI: 10.3934/dcds.2012.32.3539 · Zbl 1266.37010 · doi:10.3934/dcds.2012.32.3539 |
| [15] | Giesl P., J. Math. Anal. Appl. |
| [16] | DOI: 10.3934/dcds.2004.10.657 · Zbl 1070.93044 · doi:10.3934/dcds.2004.10.657 |
| [17] | DOI: 10.1080/14689360500164873 · Zbl 1102.34038 · doi:10.1080/14689360500164873 |
| [18] | Hafstein S., Electron. J. Differ. Equ. Monogr. 8 (2007) |
| [19] | DOI: 10.1016/S0167-6911(01)00164-5 · Zbl 0987.93072 · doi:10.1016/S0167-6911(01)00164-5 |
| [20] | P. Julian, A high level canonical piecewise linear representation: Theory and applications, Ph.D. thesis, Universidad Nacional del Sur, Bahia Blanca, Argentina (1999) |
| [21] | DOI: 10.1080/002071799220876 · Zbl 0963.93036 · doi:10.1080/002071799220876 |
| [22] | DOI: 10.1007/s10208-004-0163-9 · Zbl 1099.37010 · doi:10.1007/s10208-004-0163-9 |
| [23] | C. Kellett, Advances in converse and control Lyapunov functions, Ph.D. thesis, University of California, Santa Barbara, USA (2002) |
| [24] | C.Kellett and A.Teel, Results on converse Lyapunov theorems for difference inclusions, in Proceedings of the 42st IEEE Conference on Decision and Control, Maui, H.I. Vol. 4, 2003, pp. 3627–3632. |
| [25] | DOI: 10.1016/j.sysconle.2004.02.015 · Zbl 1157.93470 · doi:10.1016/j.sysconle.2004.02.015 |
| [26] | DOI: 10.1137/S0363012903435862 · Zbl 1096.39008 · doi:10.1137/S0363012903435862 |
| [27] | DOI: 10.1007/s00498-007-0016-6 · Zbl 1158.93025 · doi:10.1007/s00498-007-0016-6 |
| [28] | DOI: 10.1137/S0363012903435862 · Zbl 1096.39008 · doi:10.1137/S0363012903435862 |
| [29] | DOI: 10.1080/00207177708922266 · Zbl 0364.65025 · doi:10.1080/00207177708922266 |
| [30] | M.Lazar and A.Jokic, On infinity norms as Lyapunov functions for piecewise affine systems, in Proceedings of Hybrid Systems: Computation and Control Conference, Stockholm, Sweden, 2010, pp. 131–141. · Zbl 1360.93554 |
| [31] | S. Marinosson, Stability analysis of nonlinear systems with linear cprogramming: A Lyapunov functions based approach, Ph.D. thesis, Gerhard-Mercator-University, Duisburg, Germany (2002) |
| [32] | DOI: 10.1080/0268111011011847 · Zbl 1013.34051 · doi:10.1080/0268111011011847 |
| [33] | DOI: 10.1016/S0005-1098(02)00193-0 · Zbl 1010.93091 · doi:10.1016/S0005-1098(02)00193-0 |
| [34] | Norton D., Comment. Math. Univ. Carolin. 36 (3) pp 585– (1995) |
| [35] | DOI: 10.1007/978-1-4612-0577-7 · doi:10.1007/978-1-4612-0577-7 |
| [36] | L.Tu, An Introduction to Manifolds, Springer, New York, 2008. · Zbl 1144.58001 |
| [37] | DOI: 10.1017/CBO9780511617539 · doi:10.1017/CBO9780511617539 |
| [38] | V.Zubov, Methods of A.M. Lyapunov and their Application, P. Noordhoff, Groningen, 1964. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
