American Institute of Mathematical Sciences

• 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

 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.
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] 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 [2] 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 [3] Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006 [4] Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015 [5] Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055 [6] Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069 [7] Andreas Koutsogiannis. Multiple ergodic averages for tempered functions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1177-1205. doi: 10.3934/dcds.2020314 [8] Isabeau Birindelli, Françoise Demengel, Fabiana Leoni. Boundary asymptotics of the ergodic functions associated with fully nonlinear operators through a Liouville type theorem. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020395 [9] Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169 [10] Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098 [11] Andrew Comech, Scipio Cuccagna. On asymptotic stability of ground states of some systems of nonlinear Schrödinger equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1225-1270. doi: 10.3934/dcds.2020316 [12] Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $(n, m)$-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117 [13] Tahir Aliyev Azeroğlu, Bülent Nafi Örnek, Timur Düzenli. Some results on the behaviour of transfer functions at the right half plane. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020106 [14] Meenakshi Rana, Shruti Sharma. Combinatorics of some fifth and sixth order mock theta functions. Electronic Research Archive, 2021, 29 (1) : 1803-1818. doi: 10.3934/era.2020092 [15] Kalikinkar Mandal, Guang Gong. On ideal $t$-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020125 [16] Tomasz Szostok. Inequalities of Hermite-Hadamard type for higher order convex functions, revisited. Communications on Pure & Applied Analysis, 2021, 20 (2) : 903-914. doi: 10.3934/cpaa.2020296 [17] Meilan Cai, Maoan Han. Limit cycle bifurcations in a class of piecewise smooth cubic systems with multiple parameters. Communications on Pure & Applied Analysis, 2021, 20 (1) : 55-75. doi: 10.3934/cpaa.2020257 [18] Jonathan J. Wylie, Robert M. Miura, Huaxiong Huang. Systems of coupled diffusion equations with degenerate nonlinear source terms: Linear stability and traveling waves. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 561-569. doi: 10.3934/dcds.2009.23.561 [19] Arthur Fleig, Lars Grüne. Strict dissipativity analysis for classes of optimal control problems involving probability density functions. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020053 [20] Chunming Tang, Maozhi Xu, Yanfeng Qi, Mingshuo Zhou. A new class of $p$-ary regular bent functions. Advances in Mathematics of Communications, 2021, 15 (1) : 55-64. doi: 10.3934/amc.2020042

2019 Impact Factor: 1.27