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 and 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.

[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.

[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.

[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.

[5]

F. H. Clarke, Yu. S. Ledyaev and R. J. Stern, Asymptotic stability and smooth Lyapunov functions, J. Differential Equations, 149 (1998), 69-114.

[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.

[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.

[8]

P. Giesl, "Construction of Global Lyapunov Functions Using Radial Basis Functions," Lecture Notes in Math., 1904, Springer, Berlin, 2007.

[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.

[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.

[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, Springer-Verlag, Berlin, 2005.

[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.

[14]

M. Johansson, "Piecewise Linear Control Systems. A Computational Approach," Lecture Notes in Control and Inform. Sci., 284, Springer-Verlag, Berlin, 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-715.

[16]

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

[17]

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

[18]

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

[19]

S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dyn. Syst., 17 (2002), 137-150. 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, Frederick Ungar Publishing Co., New York, 1955.

[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.

[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-328. 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-367 (electronic). doi: 10.1051/cocv:2000113.

[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.

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.

[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.

[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.

[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.

[5]

F. H. Clarke, Yu. S. Ledyaev and R. J. Stern, Asymptotic stability and smooth Lyapunov functions, J. Differential Equations, 149 (1998), 69-114.

[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.

[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.

[8]

P. Giesl, "Construction of Global Lyapunov Functions Using Radial Basis Functions," Lecture Notes in Math., 1904, Springer, Berlin, 2007.

[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.

[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.

[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, Springer-Verlag, Berlin, 2005.

[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.

[14]

M. Johansson, "Piecewise Linear Control Systems. A Computational Approach," Lecture Notes in Control and Inform. Sci., 284, Springer-Verlag, Berlin, 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-715.

[16]

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

[17]

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

[18]

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

[19]

S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dyn. Syst., 17 (2002), 137-150. 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, Frederick Ungar Publishing Co., New York, 1955.

[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.

[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-328. 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-367 (electronic). doi: 10.1051/cocv:2000113.

[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.

[1]

Jianfeng Lv, Yan Gao, Na Zhao. The viability of switched nonlinear systems with piecewise smooth Lyapunov functions. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and Continuous Dynamical Systems, 2013, 33 (7) : 2631-2650. doi: 10.3934/dcds.2013.33.2631
[8]

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

Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete and Continuous Dynamical Systems - B, 2021, 26 (12) : 6027-6046. doi: 10.3934/dcdsb.2020378
[10]

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

Najla Mohammed, Peter Giesl. Grid refinement in the construction of Lyapunov functions using radial basis functions. Discrete and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Continuous Dynamical Systems - B, 2015, 20 (7) : 1971-1981. doi: 10.3934/dcdsb.2015.20.1971

2020 Impact Factor: 1.327

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy