Linear programming based Lyapunov function computation for differential inclusions

Robert Baier; Lars Grüne; Sigurđur Freyr Hafstein

doi:10.3934/dcdsb.2012.17.33

Article Contents

2012, Volume 17, Issue 1: 33-56. Doi: 10.3934/dcdsb.2012.17.33

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

Linear programming based Lyapunov function computation for differential inclusions

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

Received: May 2010

Revised: December 2010

Published: January 2012

Abstract Related Papers Cited by

Abstract

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:

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

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

Citation:

Related Papers

Cited by

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