# American Institute of Mathematical Sciences

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 & 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. 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. 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, (2000), 277. 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), (2009), 91. [5] F. H. Clarke, Y. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory,, Springer-Verlag, (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. 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), (2006), 77. [8] S. Dashkovskiy, B. Rüffer and F. Wirth, An ISS small-gain theorem for general networks,, Math. Control Signals Systems, 19 (2007), 93. 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. 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. 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. [12] S. F. Hafstein, A constructive converse Lyapunov theorem on exponential stability,, Discrete Contin. Dyn. Syst., 10 (2004), 657. 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. 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, (2007). [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. 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. 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), (2012). [18] S. F. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming,, Dyn. Syst., 17 (2002), 137. 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. doi: 10.1007/BF01600051. [20] E. D. Sontag, Smooth stabilization implies coprime factorization,, IEEE Trans. Automat. Control, 34 (1989), 435. 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), (1989), 1. [22] E. D. Sontag, Further facts about input to state stabilization,, IEEE Trans. Automat. Control, 35 (1990), 473. 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. 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. 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. 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. 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, (2000), 277. 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), (2009), 91. [5] F. H. Clarke, Y. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory,, Springer-Verlag, (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. 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), (2006), 77. [8] S. Dashkovskiy, B. Rüffer and F. Wirth, An ISS small-gain theorem for general networks,, Math. Control Signals Systems, 19 (2007), 93. 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. 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. 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. [12] S. F. Hafstein, A constructive converse Lyapunov theorem on exponential stability,, Discrete Contin. Dyn. Syst., 10 (2004), 657. 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. 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, (2007). [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. 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. 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), (2012). [18] S. F. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming,, Dyn. Syst., 17 (2002), 137. 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. doi: 10.1007/BF01600051. [20] E. D. Sontag, Smooth stabilization implies coprime factorization,, IEEE Trans. Automat. Control, 34 (1989), 435. 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), (1989), 1. [22] E. D. Sontag, Further facts about input to state stabilization,, IEEE Trans. Automat. Control, 35 (1990), 473. 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. 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. doi: 10.1109/9.536498.
 [1] Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33 [2] Andrii Mironchenko, Hiroshi Ito. Characterizations of integral input-to-state stability for bilinear systems in infinite dimensions. Mathematical Control & Related Fields, 2016, 6 (3) : 447-466. doi: 10.3934/mcrf.2016011 [3] Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049 [4] Jóhann Björnsson, Peter Giesl, Sigurdur F. Hafstein, Christopher M. Kellett. Computation of Lyapunov functions for systems with multiple local attractors. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4019-4039. doi: 10.3934/dcds.2015.35.4019 [5] 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 [6] Martin Gugat, Günter Leugering, Ke Wang. Neumann boundary feedback stabilization for a nonlinear wave equation: A strict $H^2$-lyapunov function. Mathematical Control & Related Fields, 2017, 7 (3) : 419-448. doi: 10.3934/mcrf.2017015 [7] Peter Giesl. Construction of a global Lyapunov function using radial basis functions with a single operator. Discrete & Continuous Dynamical Systems - B, 2007, 7 (1) : 101-124. doi: 10.3934/dcdsb.2007.7.101 [8] Łukasz Struski, Jacek Tabor. Expansivity implies existence of Hölder continuous Lyapunov function. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3575-3589. doi: 10.3934/dcdsb.2017180 [9] Peter Giesl. Construction of a finite-time Lyapunov function by meshless collocation. Discrete & Continuous Dynamical Systems - B, 2012, 17 (7) : 2387-2412. doi: 10.3934/dcdsb.2012.17.2387 [10] 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 & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-23. doi: 10.3934/dcdsb.2019080 [11] Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353 [12] 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 [13] Jifeng Chu, Jinzhi Lei, Meirong Zhang. Lyapunov stability for conservative systems with lower degrees of freedom. Discrete & Continuous Dynamical Systems - B, 2011, 16 (2) : 423-443. doi: 10.3934/dcdsb.2011.16.423 [14] 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. [15] Hans Rullgård, Eric Todd Quinto. Local Sobolev estimates of a function by means of its Radon transform. Inverse Problems & Imaging, 2010, 4 (4) : 721-734. doi: 10.3934/ipi.2010.4.721 [16] Qinghua Ma, Zuoliang Xu, Liping Wang. Recovery of the local volatility function using regularization and a gradient projection method. Journal of Industrial & Management Optimization, 2015, 11 (2) : 421-437. doi: 10.3934/jimo.2015.11.421 [17] Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585 [18] Zhiyou Wu, Fusheng Bai, Guoquan Li, Yongjian Yang. A new auxiliary function method for systems of nonlinear equations. Journal of Industrial & Management Optimization, 2015, 11 (2) : 345-364. doi: 10.3934/jimo.2015.11.345 [19] Markus Dick, Martin Gugat, Günter Leugering. A strict $H^1$-Lyapunov function and feedback stabilization for the isothermal Euler equations with friction. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 225-244. doi: 10.3934/naco.2011.1.225 [20] Wacław Marzantowicz, Justyna Signerska. Firing map of an almost periodic input function. Conference Publications, 2011, 2011 (Special) : 1032-1041. doi: 10.3934/proc.2011.2011.1032

2017 Impact Factor: 0.972