Linear programming based Lyapunov function computation for differential inclusions

Previous Article
Homogenization of a one-dimensional spectral problem for a singularly perturbed elliptic operator with Neumann boundary conditions
DCDS-B Home
This Issue
Next Article
Exponential decay in non-uniform porous-thermo-elasticity model of Lord-Shulman type

January 2012, 17(1): 33-56. doi: 10.3934/dcdsb.2012.17.33

Linear programming based Lyapunov function computation for differential inclusions

Robert Baier ^1, , Lars Grüne ^1, and Sigurđur Freyr Hafstein ^2,

1.	Chair of Applied Mathematics, University of Bayreuth, 95440 Bayreuth, Germany, Germany
2.	School of Science and Engineering, Reykjavík University, Menntavegur 1, 101 Reykjavík, Iceland

Received May 2010 Revised December 2010 Published October 2011

Abstract
Related Papers

We present a numerical algorithm for computing Lyapunov functions for a class of strongly asymptotically stable nonlinear differential inclusions which includes spatially switched systems and systems with uncertain parameters. The method relies on techniques from nonsmooth analysis and linear programming and constructs a piecewise affine Lyapunov function. We provide necessary background material from nonsmooth analysis and a thorough analysis of the method which in particular shows that whenever a Lyapunov function exists then the algorithm is in principle able to compute it. Two numerical examples illustrate our method.

Keywords: switched systems, stability of nonlinear systems, piecewise affine functions., invariance principle, Lyapunov functions, numerical construction of Lyapunov functions, differential inclusions.

Mathematics Subject Classification: Primary: 93D30, 93D20; Secondary: 34D20, 34A60, 34A3.

Citation: 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

References:

[1]	A. Bacciotti and F. Ceragioli, Stability and stabilization of discontinuous systems and nonsmooth Lyapunov functions,, ESAIM Control Optim. Calc. Var., 4 (1999), 361. doi: 10.1051/cocv:1999113. Google Scholar
[2]	F. Camilli, L. Grüne and F. Wirth, A regularization of Zubov's equation for robust domains of attraction,, in, 258 (2001), 277. Google Scholar
[3]	G. Chesi, Estimating the domain of attraction for uncertain polynomial systems,, Automatica J. IFAC, 40 (2004), 1981. doi: 10.1016/j.automatica.2004.06.014. Google Scholar
[4]	F. H. Clarke, "Optimization and Nonsmooth Analysis," Second edition, Classics in Applied Mathematics, 5, SIAM, Philadelphia, PA, 1990,, First edition published in John Wiley & Sons, (1983). Google Scholar
[5]	F. H. Clarke, Yu. S. Ledyaev and R. J. Stern, Asymptotic stability and smooth Lyapunov functions,, J. Differential Equations, 149 (1998), 69. Google Scholar
[6]	T. Donchev, V. Ríos and P. Wolenski, Strong invariance and one-sided Lipschitz multifunctions,, Nonlinear Anal., 60 (2005), 849. doi: 10.1016/j.na.2004.09.050. Google Scholar
[7]	A. F. Filippov, "Differential Equations with Discontinuous Righthand Sides,", Translated from the Russian, 18 (1988). Google Scholar
[8]	P. Giesl, "Construction of Global Lyapunov Functions Using Radial Basis Functions,", Lecture Notes in Math., 1904 (2007). Google Scholar
[9]	P. Giesl and S. F. Hafstein, Existence of piecewise affine Lyapunov functions in two dimensions,, J. Math. Anal. Appl., 371 (2010), 233. doi: 10.1016/j.jmaa.2010.05.009. Google Scholar
[10]	L. Grüne and O. Junge, "Gewöhnliche Differentialgleichungen. Eine Einführung aus der Perspektive der dynamischen Systeme. Bachelorkurs Mathematik,", Vieweg Studium, (2009). Google Scholar
[11]	S. F. Hafstein, "An Algorithm for Constructing Lyapunov Functions,", Electron. J. Differential Equ. Monogr., 8, Texas State Univ., Dep. of Mathematics, San Marcos, TX, 2007., Available from: \url{http://ejde.math.txstate.edu}., (). Google Scholar
[12]	D. Hinrichsen and A. J. Pritchard, "Mathematical Systems Theory I. Modelling, State Space Analysis, Stability and Robustness,", Texts in Applied Mathematics, 48 (2005). Google Scholar
[13]	T. A. Johansen, Computation of Lyapunov functions for smooth nonlinear systems using convex optimization,, Automatica J. IFAC, 36 (2000), 1617. doi: 10.1016/S0005-1098(00)00088-1. Google Scholar
[14]	M. Johansson, "Piecewise Linear Control Systems. A Computational Approach,", Lecture Notes in Control and Inform. Sci., 284 (2003). Google Scholar
[15]	P. Julián, J. Guivant and A. Desages, A parametrization of piecewise linear Lyapunov functions via linear programming. Multiple model approaches to modelling and control,, Internat. J. Control, 72 (1999), 702. Google Scholar
[16]	B. Kummer, Newton's method for nondifferentiable functions,, in, 45 (1988), 114. Google Scholar
[17]	G. Leoni, "A First Course in Sobolev Spaces,", Graduate Studies in Mathematics, 105 (2009). Google Scholar
[18]	D. Liberzon, "Switching in Systems and Control,", Systems & Control: Foundations & Applications, (2003). Google Scholar
[19]	S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming,, Dyn. Syst., 17 (2002), 137. doi: 10.1080/0268111011011847. Google Scholar
[20]	I. P. Natanson, "Theory of Functions of a Real Variable,", Translated by L. F. Boron with the collaboration of E. Hewitt, (1955). Google Scholar
[21]	E. P. Ryan, An integral invariance principle for differential inclusions with applications in adaptive control,, SIAM J. Control Optim., 36 (1998), 960. doi: 10.1137/S0363012996301701. Google Scholar
[22]	S. Scholtes, "Introduction to Piecewise Differentiable Equations," habilitation thesis, Universität Karlsruhe, Institut für Statistik und Mathematische Wirtschaftstheorie, Karlsruhe, Germany, May, 1994., Preprint no. 53/1994., (). Google Scholar
[23]	D. Stewart, A high accuracy method for solving ODEs with discontinuous right-hand side,, Numer. Math., 58 (1990), 299. doi: 10.1007/BF01385627. Google Scholar
[24]	A. R. Teel and L. Praly, A smooth Lyapunov function from a class-$\mathcal{KL}$ estimate involving two positive semidefinite functions,, ESAIM Control Optim. Calc. Var., 5 (2000), 313. doi: 10.1051/cocv:2000113. Google Scholar
[25]	H. Whitney, Analytic extensions of differentiable functions defined in closed sets,, Trans. Amer. Math. Soc., 36 (1934), 63. doi: 10.1090/S0002-9947-1934-1501735-3. Google Scholar

show all references

References:

[1]	A. Bacciotti and F. Ceragioli, Stability and stabilization of discontinuous systems and nonsmooth Lyapunov functions,, ESAIM Control Optim. Calc. Var., 4 (1999), 361. doi: 10.1051/cocv:1999113. Google Scholar
[2]	F. Camilli, L. Grüne and F. Wirth, A regularization of Zubov's equation for robust domains of attraction,, in, 258 (2001), 277. Google Scholar
[3]	G. Chesi, Estimating the domain of attraction for uncertain polynomial systems,, Automatica J. IFAC, 40 (2004), 1981. doi: 10.1016/j.automatica.2004.06.014. Google Scholar
[4]	F. H. Clarke, "Optimization and Nonsmooth Analysis," Second edition, Classics in Applied Mathematics, 5, SIAM, Philadelphia, PA, 1990,, First edition published in John Wiley & Sons, (1983). Google Scholar
[5]	F. H. Clarke, Yu. S. Ledyaev and R. J. Stern, Asymptotic stability and smooth Lyapunov functions,, J. Differential Equations, 149 (1998), 69. Google Scholar
[6]	T. Donchev, V. Ríos and P. Wolenski, Strong invariance and one-sided Lipschitz multifunctions,, Nonlinear Anal., 60 (2005), 849. doi: 10.1016/j.na.2004.09.050. Google Scholar
[7]	A. F. Filippov, "Differential Equations with Discontinuous Righthand Sides,", Translated from the Russian, 18 (1988). Google Scholar
[8]	P. Giesl, "Construction of Global Lyapunov Functions Using Radial Basis Functions,", Lecture Notes in Math., 1904 (2007). Google Scholar
[9]	P. Giesl and S. F. Hafstein, Existence of piecewise affine Lyapunov functions in two dimensions,, J. Math. Anal. Appl., 371 (2010), 233. doi: 10.1016/j.jmaa.2010.05.009. Google Scholar
[10]	L. Grüne and O. Junge, "Gewöhnliche Differentialgleichungen. Eine Einführung aus der Perspektive der dynamischen Systeme. Bachelorkurs Mathematik,", Vieweg Studium, (2009). Google Scholar
[11]	S. F. Hafstein, "An Algorithm for Constructing Lyapunov Functions,", Electron. J. Differential Equ. Monogr., 8, Texas State Univ., Dep. of Mathematics, San Marcos, TX, 2007., Available from: \url{http://ejde.math.txstate.edu}., (). Google Scholar
[12]	D. Hinrichsen and A. J. Pritchard, "Mathematical Systems Theory I. Modelling, State Space Analysis, Stability and Robustness,", Texts in Applied Mathematics, 48 (2005). Google Scholar
[13]	T. A. Johansen, Computation of Lyapunov functions for smooth nonlinear systems using convex optimization,, Automatica J. IFAC, 36 (2000), 1617. doi: 10.1016/S0005-1098(00)00088-1. Google Scholar
[14]	M. Johansson, "Piecewise Linear Control Systems. A Computational Approach,", Lecture Notes in Control and Inform. Sci., 284 (2003). Google Scholar
[15]	P. Julián, J. Guivant and A. Desages, A parametrization of piecewise linear Lyapunov functions via linear programming. Multiple model approaches to modelling and control,, Internat. J. Control, 72 (1999), 702. Google Scholar
[16]	B. Kummer, Newton's method for nondifferentiable functions,, in, 45 (1988), 114. Google Scholar
[17]	G. Leoni, "A First Course in Sobolev Spaces,", Graduate Studies in Mathematics, 105 (2009). Google Scholar
[18]	D. Liberzon, "Switching in Systems and Control,", Systems & Control: Foundations & Applications, (2003). Google Scholar
[19]	S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming,, Dyn. Syst., 17 (2002), 137. doi: 10.1080/0268111011011847. Google Scholar
[20]	I. P. Natanson, "Theory of Functions of a Real Variable,", Translated by L. F. Boron with the collaboration of E. Hewitt, (1955). Google Scholar
[21]	E. P. Ryan, An integral invariance principle for differential inclusions with applications in adaptive control,, SIAM J. Control Optim., 36 (1998), 960. doi: 10.1137/S0363012996301701. Google Scholar
[22]	S. Scholtes, "Introduction to Piecewise Differentiable Equations," habilitation thesis, Universität Karlsruhe, Institut für Statistik und Mathematische Wirtschaftstheorie, Karlsruhe, Germany, May, 1994., Preprint no. 53/1994., (). Google Scholar
[23]	D. Stewart, A high accuracy method for solving ODEs with discontinuous right-hand side,, Numer. Math., 58 (1990), 299. doi: 10.1007/BF01385627. Google Scholar
[24]	A. R. Teel and L. Praly, A smooth Lyapunov function from a class-$\mathcal{KL}$ estimate involving two positive semidefinite functions,, ESAIM Control Optim. Calc. Var., 5 (2000), 313. doi: 10.1051/cocv:2000113. Google Scholar
[25]	H. Whitney, Analytic extensions of differentiable functions defined in closed sets,, Trans. Amer. Math. Soc., 36 (1934), 63. doi: 10.1090/S0002-9947-1934-1501735-3. Google Scholar

[1]	Sigurdur F. Hafstein, Christopher M. Kellett, Huijuan Li. Computing continuous and piecewise affine lyapunov functions for nonlinear systems. Journal of Computational Dynamics, 2015, 2 (2) : 227-246. doi: 10.3934/jcd.2015004
[2]	Volodymyr Pichkur. On practical stability of differential inclusions using Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (5) : 1977-1986. doi: 10.3934/dcdsb.2017116
[3]	Michael Schönlein. Asymptotic stability and smooth Lyapunov functions for a class of abstract dynamical systems. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 4053-4069. doi: 10.3934/dcds.2017172
[4]	Gunther Dirr, Hiroshi Ito, Anders Rantzer, Björn S. Rüffer. Separable Lyapunov functions for monotone systems: Constructions and limitations. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2497-2526. doi: 10.3934/dcdsb.2015.20.2497
[5]	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
[6]	Luis Barreira, Claudia Valls. Stability of nonautonomous equations and Lyapunov functions. Discrete & Continuous Dynamical Systems - A, 2013, 33 (7) : 2631-2650. doi: 10.3934/dcds.2013.33.2631
[7]	Tomoharu Suda. Construction of Lyapunov functions using Helmholtz–Hodge decomposition. Discrete & Continuous Dynamical Systems - A, 2019, 39 (5) : 2437-2454. doi: 10.3934/dcds.2019103
[8]	Peter Giesl, Sigurdur Hafstein. Existence of piecewise linear Lyapunov functions in arbitrary dimensions. Discrete & Continuous Dynamical Systems - A, 2012, 32 (10) : 3539-3565. doi: 10.3934/dcds.2012.32.3539
[9]	Najla Mohammed, Peter Giesl. Grid refinement in the construction of Lyapunov functions using radial basis functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2453-2476. doi: 10.3934/dcdsb.2015.20.2453
[10]	Peter Giesl, Sigurdur Hafstein. Computational methods for Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : i-ii. doi: 10.3934/dcdsb.2015.20.8i
[11]	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
[12]	Peter Giesl, Najla Mohammed. Verification estimates for the construction of Lyapunov functions using meshfree collocation. Discrete & Continuous Dynamical Systems - B, 2019, 24 (9) : 4955-4981. doi: 10.3934/dcdsb.2019040
[13]	Peter Giesl, Sigurdur Hafstein. Review on computational methods for Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2291-2331. doi: 10.3934/dcdsb.2015.20.2291
[14]	Renato C. Calleja, Alessandra Celletti, Rafael de la Llave. Construction of response functions in forced strongly dissipative systems. Discrete & Continuous Dynamical Systems - A, 2013, 33 (10) : 4411-4433. doi: 10.3934/dcds.2013.33.4411
[15]	Frédéric Mazenc, Christophe Prieur. Strict Lyapunov functions for semilinear parabolic partial differential equations. Mathematical Control & Related Fields, 2011, 1 (2) : 231-250. doi: 10.3934/mcrf.2011.1.231
[16]	Deqiong Ding, Wendi Qin, Xiaohua Ding. Lyapunov functions and global stability for a discretized multigroup SIR epidemic model. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 1971-1981. doi: 10.3934/dcdsb.2015.20.1971
[17]	Guoshan Zhang, Shiwei Wang, Yiming Wang, Wanquan Liu. LS-SVM approximate solution for affine nonlinear systems with partially unknown functions. Journal of Industrial & Management Optimization, 2014, 10 (2) : 621-636. doi: 10.3934/jimo.2014.10.621
[18]	Tsuyoshi Kajiwara, Toru Sasaki, Yasuhiro Takeuchi. Construction of Lyapunov functions for some models of infectious diseases in vivo: From simple models to complex models. Mathematical Biosciences & Engineering, 2015, 12 (1) : 117-133. doi: 10.3934/mbe.2015.12.117
[19]	Ezzeddine Zahrouni. On the Lyapunov functions for the solutions of the generalized Burgers equation. Communications on Pure & Applied Analysis, 2003, 2 (3) : 391-410. doi: 10.3934/cpaa.2003.2.391
[20]	C. Connell Mccluskey. Lyapunov functions for tuberculosis models with fast and slow progression. Mathematical Biosciences & Engineering, 2006, 3 (4) : 603-614. doi: 10.3934/mbe.2006.3.603

2018 Impact Factor: 1.008

American Institute of Mathematical Sciences