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

Previous Article
Separable Lyapunov functions for monotone systems: Constructions and limitations
DCDS-B Home
This Issue
Next Article
Grid refinement in the construction of Lyapunov functions using radial basis functions

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

Huijuan Li ^1, , Robert Baier ^2, , Lars Grüne ^2, , Sigurdur F. Hafstein ^3, and Fabian R. Wirth ^4,

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

Abstract
Related Papers

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.

Keywords: Nonlinear systems, linear programming., local ISS Lyapunov function, local input-to-state stability, robust Lyapunov function.

Mathematics Subject Classification: Primary: 37B25, 93D09, 93D30; Secondary: 34D20, 90C0.

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.

2020 Impact Factor: 1.327

Tools

Metrics

Other articles
by authors

on AIMS
Huijuan Li Robert Baier Lars Grüne Sigurdur F. Hafstein Fabian R. Wirth
on Google Scholar
Huijuan Li Robert Baier Lars Grüne Sigurdur F. Hafstein Fabian R. Wirth

[Back to Top]