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.
[2]	F. Camilli, L. Grüne and F. Wirth, A regularization of Zubov's equation for robust domains of attraction,, in, 258 (2001), 277.
[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.
[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).
[5]	F. H. Clarke, Yu. S. Ledyaev and R. J. Stern, Asymptotic stability and smooth Lyapunov functions,, J. Differential Equations, 149 (1998), 69.
[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.
[7]	A. F. Filippov, "Differential Equations with Discontinuous Righthand Sides,", Translated from the Russian, 18 (1988).
[8]	P. Giesl, "Construction of Global Lyapunov Functions Using Radial Basis Functions,", Lecture Notes in Math., 1904 (2007).
[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.
[10]	L. Grüne and O. Junge, "Gewöhnliche Differentialgleichungen. Eine Einführung aus der Perspektive der dynamischen Systeme. Bachelorkurs Mathematik,", Vieweg Studium, (2009).
[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}., ().
[12]	D. Hinrichsen and A. J. Pritchard, "Mathematical Systems Theory I. Modelling, State Space Analysis, Stability and Robustness,", Texts in Applied Mathematics, 48 (2005).
[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.
[14]	M. Johansson, "Piecewise Linear Control Systems. A Computational Approach,", Lecture Notes in Control and Inform. Sci., 284 (2003).
[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.
[16]	B. Kummer, Newton's method for nondifferentiable functions,, in, 45 (1988), 114.
[17]	G. Leoni, "A First Course in Sobolev Spaces,", Graduate Studies in Mathematics, 105 (2009).
[18]	D. Liberzon, "Switching in Systems and Control,", Systems & Control: Foundations & Applications, (2003).
[19]	S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming,, Dyn. Syst., 17 (2002), 137. doi: 10.1080/0268111011011847.
[20]	I. P. Natanson, "Theory of Functions of a Real Variable,", Translated by L. F. Boron with the collaboration of E. Hewitt, (1955).
[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.
[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., ().
[23]	D. Stewart, A high accuracy method for solving ODEs with discontinuous right-hand side,, Numer. Math., 58 (1990), 299. doi: 10.1007/BF01385627.
[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.
[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.

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.
[2]	F. Camilli, L. Grüne and F. Wirth, A regularization of Zubov's equation for robust domains of attraction,, in, 258 (2001), 277.
[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.
[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).
[5]	F. H. Clarke, Yu. S. Ledyaev and R. J. Stern, Asymptotic stability and smooth Lyapunov functions,, J. Differential Equations, 149 (1998), 69.
[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.
[7]	A. F. Filippov, "Differential Equations with Discontinuous Righthand Sides,", Translated from the Russian, 18 (1988).
[8]	P. Giesl, "Construction of Global Lyapunov Functions Using Radial Basis Functions,", Lecture Notes in Math., 1904 (2007).
[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.
[10]	L. Grüne and O. Junge, "Gewöhnliche Differentialgleichungen. Eine Einführung aus der Perspektive der dynamischen Systeme. Bachelorkurs Mathematik,", Vieweg Studium, (2009).
[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}., ().
[12]	D. Hinrichsen and A. J. Pritchard, "Mathematical Systems Theory I. Modelling, State Space Analysis, Stability and Robustness,", Texts in Applied Mathematics, 48 (2005).
[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.
[14]	M. Johansson, "Piecewise Linear Control Systems. A Computational Approach,", Lecture Notes in Control and Inform. Sci., 284 (2003).
[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.
[16]	B. Kummer, Newton's method for nondifferentiable functions,, in, 45 (1988), 114.
[17]	G. Leoni, "A First Course in Sobolev Spaces,", Graduate Studies in Mathematics, 105 (2009).
[18]	D. Liberzon, "Switching in Systems and Control,", Systems & Control: Foundations & Applications, (2003).
[19]	S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming,, Dyn. Syst., 17 (2002), 137. doi: 10.1080/0268111011011847.
[20]	I. P. Natanson, "Theory of Functions of a Real Variable,", Translated by L. F. Boron with the collaboration of E. Hewitt, (1955).
[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.
[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., ().
[23]	D. Stewart, A high accuracy method for solving ODEs with discontinuous right-hand side,, Numer. Math., 58 (1990), 299. doi: 10.1007/BF01385627.
[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.
[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.

[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, 2017, 22 (11) : 1-27. 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

2017 Impact Factor: 0.972

American Institute of Mathematical Sciences