American Institute of Mathematical Sciences

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

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-376 (electronic). 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 "Nonlinear Control in the Year 2000, Vol. 1," Lecture Notes in Control and Inform. Sci., 258, Springer, London, (2001), 277-289.  Google Scholar

[3]

G. Chesi, Estimating the domain of attraction for uncertain polynomial systems, Automatica J. IFAC, 40 (2004), 1981-1986. 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, Inc., New York, 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-114.  Google Scholar

[6]

T. Donchev, V. Ríos and P. Wolenski, Strong invariance and one-sided Lipschitz multifunctions, Nonlinear Anal., 60 (2005), 849-862. doi: 10.1016/j.na.2004.09.050.  Google Scholar

[7]

A. F. Filippov, "Differential Equations with Discontinuous Righthand Sides," Translated from the Russian, Mathematics and its Applications (Soviet Series), 18, Kluwer Academic Publishers Group, Dordrecht, 1988.  Google Scholar

[8]

P. Giesl, "Construction of Global Lyapunov Functions Using Radial Basis Functions," Lecture Notes in Math., 1904, Springer, Berlin, 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-248. 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, Vieweg+Teubner, Wiesbaden, 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, Springer-Verlag, Berlin, 2005.  Google Scholar

[13]

T. A. Johansen, Computation of Lyapunov functions for smooth nonlinear systems using convex optimization, Automatica J. IFAC, 36 (2000), 1617-1626. 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, Springer-Verlag, Berlin, 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-715.  Google Scholar

[16]

B. Kummer, Newton's method for nondifferentiable functions, in "Advances in Mathematical Optimization," Math. Res., 45, Akademie-Verlag, Berlin, (1988), 114-125.  Google Scholar

[17]

G. Leoni, "A First Course in Sobolev Spaces," Graduate Studies in Mathematics, 105, American Mathematical Society, Providence, RI, 2009.  Google Scholar

[18]

D. Liberzon, "Switching in Systems and Control," Systems & Control: Foundations & Applications, Birkhäuser Boston, Inc., Boston, MA, 2003.  Google Scholar

[19]

S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dyn. Syst., 17 (2002), 137-150. 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, Frederick Ungar Publishing Co., New York, 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-980 (electronic). 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-328. 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-367 (electronic). 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-89. 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-376 (electronic). 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 "Nonlinear Control in the Year 2000, Vol. 1," Lecture Notes in Control and Inform. Sci., 258, Springer, London, (2001), 277-289.  Google Scholar

[3]

G. Chesi, Estimating the domain of attraction for uncertain polynomial systems, Automatica J. IFAC, 40 (2004), 1981-1986. 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, Inc., New York, 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-114.  Google Scholar

[6]

T. Donchev, V. Ríos and P. Wolenski, Strong invariance and one-sided Lipschitz multifunctions, Nonlinear Anal., 60 (2005), 849-862. doi: 10.1016/j.na.2004.09.050.  Google Scholar

[7]

A. F. Filippov, "Differential Equations with Discontinuous Righthand Sides," Translated from the Russian, Mathematics and its Applications (Soviet Series), 18, Kluwer Academic Publishers Group, Dordrecht, 1988.  Google Scholar

[8]

P. Giesl, "Construction of Global Lyapunov Functions Using Radial Basis Functions," Lecture Notes in Math., 1904, Springer, Berlin, 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-248. 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, Vieweg+Teubner, Wiesbaden, 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, Springer-Verlag, Berlin, 2005.  Google Scholar

[13]

T. A. Johansen, Computation of Lyapunov functions for smooth nonlinear systems using convex optimization, Automatica J. IFAC, 36 (2000), 1617-1626. 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, Springer-Verlag, Berlin, 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-715.  Google Scholar

[16]

B. Kummer, Newton's method for nondifferentiable functions, in "Advances in Mathematical Optimization," Math. Res., 45, Akademie-Verlag, Berlin, (1988), 114-125.  Google Scholar

[17]

G. Leoni, "A First Course in Sobolev Spaces," Graduate Studies in Mathematics, 105, American Mathematical Society, Providence, RI, 2009.  Google Scholar

[18]

D. Liberzon, "Switching in Systems and Control," Systems & Control: Foundations & Applications, Birkhäuser Boston, Inc., Boston, MA, 2003.  Google Scholar

[19]

S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dyn. Syst., 17 (2002), 137-150. 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, Frederick Ungar Publishing Co., New York, 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-980 (electronic). 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-328. 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-367 (electronic). 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-89. doi: 10.1090/S0002-9947-1934-1501735-3.  Google Scholar

[1]

Jianfeng Lv, Yan Gao, Na Zhao. The viability of switched nonlinear systems with piecewise smooth Lyapunov functions. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1825-1843. doi: 10.3934/jimo.2020048
[2]

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
[3]

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
[4]

Michael Schönlein. Asymptotic stability and smooth Lyapunov functions for a class of abstract dynamical systems. Discrete & Continuous Dynamical Systems, 2017, 37 (7) : 4053-4069. doi: 10.3934/dcds.2017172
[5]

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
[6]

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, 2015, 35 (9) : 4019-4039. doi: 10.3934/dcds.2015.35.4019
[7]

Luis Barreira, Claudia Valls. Stability of nonautonomous equations and Lyapunov functions. Discrete & Continuous Dynamical Systems, 2013, 33 (7) : 2631-2650. doi: 10.3934/dcds.2013.33.2631
[8]

Peter Giesl, Sigurdur Hafstein. Existence of piecewise linear Lyapunov functions in arbitrary dimensions. Discrete & Continuous Dynamical Systems, 2012, 32 (10) : 3539-3565. doi: 10.3934/dcds.2012.32.3539
[9]

Tomoharu Suda. Construction of Lyapunov functions using Helmholtz–Hodge decomposition. Discrete & Continuous Dynamical Systems, 2019, 39 (5) : 2437-2454. doi: 10.3934/dcds.2019103
[10]

Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378
[11]

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
[12]

Huijuan Li, Junxia Wang. Input-to-state stability of continuous-time systems via finite-time Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 841-857. doi: 10.3934/dcdsb.2019192
[13]

Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331
[14]

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
[15]

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
[16]

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
[17]

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
[18]

Renato C. Calleja, Alessandra Celletti, Rafael de la Llave. Construction of response functions in forced strongly dissipative systems. Discrete & Continuous Dynamical Systems, 2013, 33 (10) : 4411-4433. doi: 10.3934/dcds.2013.33.4411
[19]

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
[20]

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

2019 Impact Factor: 1.27

Tools

Metrics

  • PDF downloads (100)
  • HTML views (0)
  • Cited by (26)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences