American Institute of Mathematical Sciences

October  2015, 20(8): 2477-2495. doi: 10.3934/dcdsb.2015.20.2477

Computation of local ISS Lyapunov functions with low gains via linear programming

 1 School of Mathematics and Physics, Chinese University of Geosciences (Wuhan), 430074, Wuhan, China 2 Lehrstuhl für Angewandte Mathematik, Universität Bayreuth, 95440 Bayreuth, Germany, Germany 3 School of Science and Engineering, Reykjavik University, Menntavegi 1, Reykjavik, IS-101 4 Fakultät für Informatik und Mathematik, Universität Passau, 94030 Passau, Germany

Received  June 2014 Revised  March 2015 Published  August 2015

In this paper, we present a numerical algorithm for computing ISS Lyapunov functions for continuous-time systems which are input-to-state stable (ISS) on compact subsets of the state space. The algorithm relies on a linear programming problem and computes a continuous piecewise affine ISS Lyapunov function on a simplicial grid covering the given compact set excluding a small neighborhood of the origin. The objective of the linear programming problem is to minimize the gain. We show that for every ISS system with a locally Lipschitz right-hand side our algorithm is in principle able to deliver an ISS Lyapunov function. For $C^2$ right-hand sides a more efficient algorithm is proposed.
Citation: Huijuan Li, Robert Baier, Lars Grüne, Sigurdur F. Hafstein, Fabian R. Wirth. Computation of local ISS Lyapunov functions with low gains via linear programming. Discrete and Continuous Dynamical Systems - B, 2015, 20 (8) : 2477-2495. doi: 10.3934/dcdsb.2015.20.2477
References:
 [1] M. Abu Hassan and C. Storey, Numerical determination of domains of attraction for electrical power systems using the method of Zubov, Internat. J. Control, 34 (1981), 371-381. doi: 10.1080/00207178108922536. [2] R. Baier, L. Grüne and S. F. Hafstein, Linear programming based Lyapunov function computation for differential inclusions, Discrete Contin. Dyn. Syst. Ser. B, 17 (2012), 33-56. doi: 10.3934/dcdsb.2012.17.33. [3] F. Camilli, L. Grüne and F. Wirth, A regularization of Zubov's equation for robust domains of attraction, in Nonlinear Control in the Year 2000, Volume 1 (eds. A. Isidori, F. Lamnabhi-Lagarrigue and W. Respondek), Lecture Notes in Control and Inform. Sci., 258, NCN, Springer-Verlag, London, 2000, 277-289. doi: 10.1007/BFb0110220. [4] F. Camilli, L. Grüne and F. Wirth, Domains of attraction of interconnected systems: A Zubov method approach, in Proc. European Control Conference (ECC 2009), Budapest, Hungary, 2009, 91-96. [5] F. H. Clarke, Y. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory, Springer-Verlag, Berlin, 1998. [6] S. Dashkovskiy, B. Rüffer and F. Wirth, A small-gain type stability criterion for large scale networks of ISS systems, in Proc. of 44th IEEE Conference on Decision and Control and European Control Conference (ECC 2005), 2005, 5633-5638. doi: 10.1109/CDC.2005.1583060. [7] S. Dashkovskiy, B. Rüffer and F. Wirth, An ISS Lyapunov function for networks of ISS systems, in Proc. 17th Int. Symp. Math. Theory of Networks and Systems (MTNS 2006), Kyoto, Japan, 2006, 77-82. [8] S. Dashkovskiy, B. Rüffer and F. Wirth, An ISS small-gain theorem for general networks, Math. Control Signals Systems, 19 (2007), 93-122. doi: 10.1007/s00498-007-0014-8. [9] S. N. Dashkovskiy, B. S. Rüffer and F. R. Wirth, Small gain theorems for large scale systems and construction of ISS Lyapunov functions, SIAM J. Control Optim., 48 (2010), 4089-4118. doi: 10.1137/090746483. [10] P. Giesl and S. Hafstein, Existence of piecewise linear Lyapunov functions in arbitrary dimensions, Discrete Contin. Dyn. Syst., 32 (2012), 3539-3565. doi: 10.3934/dcds.2012.32.3539. [11] L. Grüne and M. Sigurani, Numerical ISS controller design via a dynamic game approach, in Proc. of the 52nd IEEE Conference on Decision and Control (CDC 2013), 2013, 1732-1737. [12] S. F. Hafstein, A constructive converse Lyapunov theorem on exponential stability, Discrete Contin. Dyn. Syst., 10 (2004), 657-678. doi: 10.3934/dcds.2004.10.657. [13] S. F. Hafstein, A constructive converse Lyapunov theorem on asymptotic stability for nonlinear autonomous ordinary differential equations, Dyn. Syst., 20 (2005), 281-299. doi: 10.1080/14689360500164873. [14] S. F. Hafstein, An Algorithm for Constructing Lyapunov Functions, vol. 8 of Electron. J. Differ. Equ. Monogr., Texas State University-San Marcos, Department of Mathematics, San Marcos, TX, 2007. Available from: http://ejde.math.txstate.edu. [15] S. Huang, M. R. James, D. Nešić and P. M. Dower, A unified approach to controller design for achieving ISS and related properties, IEEE Trans. Automat. Control, 50 (2005), 1681-1697. doi: 10.1109/TAC.2005.858691. [16] Z.-P. Jiang, I. M. Y. Mareels and Y. Wang, A Lyapunov formulation of the nonlinear small-gain theorem for interconnected ISS systems, Automatica J. IFAC, 32 (1996), 1211-1215. doi: 10.1016/0005-1098(96)00051-9. [17] H. Li and F. Wirth, Zubov's method for interconnected systems - a dissipative formulation, in Proc. 20th Int. Symp. Math. Theory of Networks and Systems (MTNS 2012), Melbourne, Australia, 2012, Paper No. 184, 8 pages. [18] S. F. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dyn. Syst., 17 (2002), 137-150. doi: 10.1080/0268111011011847. [19] A. N. Michel, N. R. Sarabudla and R. K. Miller, Stability analysis of complex dynamical systems: Some computational methods, Circuits Systems Signal Process., 1 (1982), 171-202. doi: 10.1007/BF01600051. [20] E. D. Sontag, Smooth stabilization implies coprime factorization, IEEE Trans. Automat. Control, 34 (1989), 435-443. doi: 10.1109/9.28018. [21] E. D. Sontag, Some connections between stabilization and factorization, in Proc. of the 28th IEEE Conference on Decision and Control (CDC 1989), Vol. 1-3 (Tampa, FL, 1989), IEEE, New York, 1989, 990-995. [22] E. D. Sontag, Further facts about input to state stabilization, IEEE Trans. Automat. Control, 35 (1990), 473-476. doi: 10.1109/9.52307. [23] E. D. Sontag and Y. Wang, On characterizations of the input-to-state stability property, Systems Control Lett., 24 (1995), 351-359. doi: 10.1016/0167-6911(94)00050-6. [24] E. D. Sontag and Y. Wang, New characterizations of input-to-state stability, IEEE Trans. Automat. Control, 41 (1996), 1283-1294. doi: 10.1109/9.536498.

show all references

References:
 [1] M. Abu Hassan and C. Storey, Numerical determination of domains of attraction for electrical power systems using the method of Zubov, Internat. J. Control, 34 (1981), 371-381. doi: 10.1080/00207178108922536. [2] R. Baier, L. Grüne and S. F. Hafstein, Linear programming based Lyapunov function computation for differential inclusions, Discrete Contin. Dyn. Syst. Ser. B, 17 (2012), 33-56. doi: 10.3934/dcdsb.2012.17.33. [3] F. Camilli, L. Grüne and F. Wirth, A regularization of Zubov's equation for robust domains of attraction, in Nonlinear Control in the Year 2000, Volume 1 (eds. A. Isidori, F. Lamnabhi-Lagarrigue and W. Respondek), Lecture Notes in Control and Inform. Sci., 258, NCN, Springer-Verlag, London, 2000, 277-289. doi: 10.1007/BFb0110220. [4] F. Camilli, L. Grüne and F. Wirth, Domains of attraction of interconnected systems: A Zubov method approach, in Proc. European Control Conference (ECC 2009), Budapest, Hungary, 2009, 91-96. [5] F. H. Clarke, Y. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory, Springer-Verlag, Berlin, 1998. [6] S. Dashkovskiy, B. Rüffer and F. Wirth, A small-gain type stability criterion for large scale networks of ISS systems, in Proc. of 44th IEEE Conference on Decision and Control and European Control Conference (ECC 2005), 2005, 5633-5638. doi: 10.1109/CDC.2005.1583060. [7] S. Dashkovskiy, B. Rüffer and F. Wirth, An ISS Lyapunov function for networks of ISS systems, in Proc. 17th Int. Symp. Math. Theory of Networks and Systems (MTNS 2006), Kyoto, Japan, 2006, 77-82. [8] S. Dashkovskiy, B. Rüffer and F. Wirth, An ISS small-gain theorem for general networks, Math. Control Signals Systems, 19 (2007), 93-122. doi: 10.1007/s00498-007-0014-8. [9] S. N. Dashkovskiy, B. S. Rüffer and F. R. Wirth, Small gain theorems for large scale systems and construction of ISS Lyapunov functions, SIAM J. Control Optim., 48 (2010), 4089-4118. doi: 10.1137/090746483. [10] P. Giesl and S. Hafstein, Existence of piecewise linear Lyapunov functions in arbitrary dimensions, Discrete Contin. Dyn. Syst., 32 (2012), 3539-3565. doi: 10.3934/dcds.2012.32.3539. [11] L. Grüne and M. Sigurani, Numerical ISS controller design via a dynamic game approach, in Proc. of the 52nd IEEE Conference on Decision and Control (CDC 2013), 2013, 1732-1737. [12] S. F. Hafstein, A constructive converse Lyapunov theorem on exponential stability, Discrete Contin. Dyn. Syst., 10 (2004), 657-678. doi: 10.3934/dcds.2004.10.657. [13] S. F. Hafstein, A constructive converse Lyapunov theorem on asymptotic stability for nonlinear autonomous ordinary differential equations, Dyn. Syst., 20 (2005), 281-299. doi: 10.1080/14689360500164873. [14] S. F. Hafstein, An Algorithm for Constructing Lyapunov Functions, vol. 8 of Electron. J. Differ. Equ. Monogr., Texas State University-San Marcos, Department of Mathematics, San Marcos, TX, 2007. Available from: http://ejde.math.txstate.edu. [15] S. Huang, M. R. James, D. Nešić and P. M. Dower, A unified approach to controller design for achieving ISS and related properties, IEEE Trans. Automat. Control, 50 (2005), 1681-1697. doi: 10.1109/TAC.2005.858691. [16] Z.-P. Jiang, I. M. Y. Mareels and Y. Wang, A Lyapunov formulation of the nonlinear small-gain theorem for interconnected ISS systems, Automatica J. IFAC, 32 (1996), 1211-1215. doi: 10.1016/0005-1098(96)00051-9. [17] H. Li and F. Wirth, Zubov's method for interconnected systems - a dissipative formulation, in Proc. 20th Int. Symp. Math. Theory of Networks and Systems (MTNS 2012), Melbourne, Australia, 2012, Paper No. 184, 8 pages. [18] S. F. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dyn. Syst., 17 (2002), 137-150. doi: 10.1080/0268111011011847. [19] A. N. Michel, N. R. Sarabudla and R. K. Miller, Stability analysis of complex dynamical systems: Some computational methods, Circuits Systems Signal Process., 1 (1982), 171-202. doi: 10.1007/BF01600051. [20] E. D. Sontag, Smooth stabilization implies coprime factorization, IEEE Trans. Automat. Control, 34 (1989), 435-443. doi: 10.1109/9.28018. [21] E. D. Sontag, Some connections between stabilization and factorization, in Proc. of the 28th IEEE Conference on Decision and Control (CDC 1989), Vol. 1-3 (Tampa, FL, 1989), IEEE, New York, 1989, 990-995. [22] E. D. Sontag, Further facts about input to state stabilization, IEEE Trans. Automat. Control, 35 (1990), 473-476. doi: 10.1109/9.52307. [23] E. D. Sontag and Y. Wang, On characterizations of the input-to-state stability property, Systems Control Lett., 24 (1995), 351-359. doi: 10.1016/0167-6911(94)00050-6. [24] E. D. Sontag and Y. Wang, New characterizations of input-to-state stability, IEEE Trans. Automat. Control, 41 (1996), 1283-1294. doi: 10.1109/9.536498.
 [1] Huijuan Li, Junxia Wang. Input-to-state stability of continuous-time systems via finite-time Lyapunov functions. Discrete and Continuous Dynamical Systems - B, 2020, 25 (3) : 841-857. doi: 10.3934/dcdsb.2019192 [2] Pengfei Wang, Mengyi Zhang, Huan Su. Input-to-state stability of infinite-dimensional stochastic nonlinear systems. Discrete and Continuous Dynamical Systems - B, 2022, 27 (2) : 821-836. doi: 10.3934/dcdsb.2021066 [3] Hiroshi Ito. Input-to-state stability and Lyapunov functions with explicit domains for SIR model of infectious diseases. Discrete and Continuous Dynamical Systems - B, 2021, 26 (9) : 5171-5196. doi: 10.3934/dcdsb.2020338 [4] Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete and Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33 [5] Andrii Mironchenko, Hiroshi Ito. Characterizations of integral input-to-state stability for bilinear systems in infinite dimensions. Mathematical Control and Related Fields, 2016, 6 (3) : 447-466. doi: 10.3934/mcrf.2016011 [6] Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete and Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049 [7] Jóhann Björnsson, Peter Giesl, Sigurdur F. Hafstein, Christopher M. Kellett. Computation of Lyapunov functions for systems with multiple local attractors. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4019-4039. doi: 10.3934/dcds.2015.35.4019 [8] Andrei Korobeinikov, Philip K. Maini. A Lyapunov function and global properties for SIR and SEIR epidemiological models with nonlinear incidence. Mathematical Biosciences & Engineering, 2004, 1 (1) : 57-60. doi: 10.3934/mbe.2004.1.57 [9] Martin Gugat, Günter Leugering, Ke Wang. Neumann boundary feedback stabilization for a nonlinear wave equation: A strict $H^2$-lyapunov function. Mathematical Control and Related Fields, 2017, 7 (3) : 419-448. doi: 10.3934/mcrf.2017015 [10] Jonathan DeWitt. Local Lyapunov spectrum rigidity of nilmanifold automorphisms. Journal of Modern Dynamics, 2021, 17: 65-109. doi: 10.3934/jmd.2021003 [11] Sibel Senan, Eylem Yucel, Zeynep Orman, Ruya Samli, Sabri Arik. A Novel Lyapunov functional with application to stability analysis of neutral systems with nonlinear disturbances. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1415-1428. doi: 10.3934/dcdss.2020358 [12] Ruofeng Rao, Shouming Zhong. Input-to-state stability and no-inputs stabilization of delayed feedback chaotic financial system involved in open and closed economy. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1375-1393. doi: 10.3934/dcdss.2020280 [13] Peter Giesl. Construction of a global Lyapunov function using radial basis functions with a single operator. Discrete and Continuous Dynamical Systems - B, 2007, 7 (1) : 101-124. doi: 10.3934/dcdsb.2007.7.101 [14] Łukasz Struski, Jacek Tabor. Expansivity implies existence of Hölder continuous Lyapunov function. Discrete and Continuous Dynamical Systems - B, 2017, 22 (9) : 3575-3589. doi: 10.3934/dcdsb.2017180 [15] Hjörtur Björnsson, Sigurdur Hafstein, Peter Giesl, Enrico Scalas, Skuli Gudmundsson. Computation of the stochastic basin of attraction by rigorous construction of a Lyapunov function. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 4247-4269. doi: 10.3934/dcdsb.2019080 [16] Peter Giesl. Construction of a finite-time Lyapunov function by meshless collocation. Discrete and Continuous Dynamical Systems - B, 2012, 17 (7) : 2387-2412. doi: 10.3934/dcdsb.2012.17.2387 [17] Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353 [18] Paul L. Salceanu. Robust uniform persistence in discrete and continuous dynamical systems using Lyapunov exponents. Mathematical Biosciences & Engineering, 2011, 8 (3) : 807-825. doi: 10.3934/mbe.2011.8.807 [19] Jifeng Chu, Jinzhi Lei, Meirong Zhang. Lyapunov stability for conservative systems with lower degrees of freedom. Discrete and Continuous Dynamical Systems - B, 2011, 16 (2) : 423-443. doi: 10.3934/dcdsb.2011.16.423 [20] Dmitry Jakobson and Iosif Polterovich. Lower bounds for the spectral function and for the remainder in local Weyl's law on manifolds. Electronic Research Announcements, 2005, 11: 71-77.

2021 Impact Factor: 1.497