American Institute of Mathematical Sciences

Advanced
October  2015, 20(8): 2477-2495. doi: 10.3934/dcdsb.2015.20.2477

Computation of local ISS Lyapunov functions with low gains via linear programming

Huijuan Li 1, , Robert Baier 2, , Lars Grüne 2, , Sigurdur F. Hafstein 3, and  Fabian R. Wirth 4,

1. 

School of Mathematics and Physics, Chinese University of Geosciences (Wuhan), 430074, Wuhan, China
2. 

Lehrstuhl für Angewandte Mathematik, Universität Bayreuth, 95440 Bayreuth, Germany, Germany
3. 

School of Science and Engineering, Reykjavik University, Menntavegi 1, Reykjavik, IS-101
4. 

Fakultät für Informatik und Mathematik, Universität Passau, 94030 Passau, Germany

Received  June 2014 Revised  March 2015 Published  August 2015

In this paper, we present a numerical algorithm for computing ISS Lyapunov functions for continuous-time systems which are input-to-state stable (ISS) on compact subsets of the state space. The algorithm relies on a linear programming problem and computes a continuous piecewise affine ISS Lyapunov function on a simplicial grid covering the given compact set excluding a small neighborhood of the origin. The objective of the linear programming problem is to minimize the gain. We show that for every ISS system with a locally Lipschitz right-hand side our algorithm is in principle able to deliver an ISS Lyapunov function. For $C^2$ right-hand sides a more efficient algorithm is proposed.
Keywords: Nonlinear systems, linear programming., local ISS Lyapunov function, local input-to-state stability, robust Lyapunov function.
Mathematics Subject Classification: Primary: 37B25, 93D09, 93D30; Secondary: 34D20, 90C0.
Citation: Huijuan Li, Robert Baier, Lars Grüne, Sigurdur F. Hafstein, Fabian R. Wirth. Computation of local ISS Lyapunov functions with low gains via linear programming. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2477-2495. doi: 10.3934/dcdsb.2015.20.2477
References:
[1]

M. Abu Hassan and C. Storey, Numerical determination of domains of attraction for electrical power systems using the method of Zubov,, Internat. J. Control, 34 (1981), 371.  doi: 10.1080/00207178108922536.  Google Scholar

[2]

R. Baier, L. Grüne and S. F. Hafstein, Linear programming based Lyapunov function computation for differential inclusions,, Discrete Contin. Dyn. Syst. Ser. B, 17 (2012), 33.  doi: 10.3934/dcdsb.2012.17.33.  Google Scholar

[3]

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, (2000), 277.  doi: 10.1007/BFb0110220.  Google Scholar

[4]

F. Camilli, L. Grüne and F. Wirth, Domains of attraction of interconnected systems: A Zubov method approach,, in Proc. European Control Conference (ECC 2009), (2009), 91.   Google Scholar

[5]

F. H. Clarke, Y. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory,, Springer-Verlag, (1998).   Google Scholar

[6]

S. Dashkovskiy, B. Rüffer and F. Wirth, A small-gain type stability criterion for large scale networks of ISS systems,, in Proc. of 44th IEEE Conference on Decision and Control and European Control Conference (ECC 2005), (2005), 5633.  doi: 10.1109/CDC.2005.1583060.  Google Scholar

[7]

S. Dashkovskiy, B. Rüffer and F. Wirth, An ISS Lyapunov function for networks of ISS systems,, in Proc. 17th Int. Symp. Math. Theory of Networks and Systems (MTNS 2006), (2006), 77.   Google Scholar

[8]

S. Dashkovskiy, B. Rüffer and F. Wirth, An ISS small-gain theorem for general networks,, Math. Control Signals Systems, 19 (2007), 93.  doi: 10.1007/s00498-007-0014-8.  Google Scholar

[9]

S. N. Dashkovskiy, B. S. Rüffer and F. R. Wirth, Small gain theorems for large scale systems and construction of ISS Lyapunov functions,, SIAM J. Control Optim., 48 (2010), 4089.  doi: 10.1137/090746483.  Google Scholar

[10]

P. Giesl and S. Hafstein, Existence of piecewise linear Lyapunov functions in arbitrary dimensions,, Discrete Contin. Dyn. Syst., 32 (2012), 3539.  doi: 10.3934/dcds.2012.32.3539.  Google Scholar

[11]

L. Grüne and M. Sigurani, Numerical ISS controller design via a dynamic game approach,, in Proc. of the 52nd IEEE Conference on Decision and Control (CDC 2013), (2013), 1732.   Google Scholar

[12]

S. F. Hafstein, A constructive converse Lyapunov theorem on exponential stability,, Discrete Contin. Dyn. Syst., 10 (2004), 657.  doi: 10.3934/dcds.2004.10.657.  Google Scholar

[13]

S. F. Hafstein, A constructive converse Lyapunov theorem on asymptotic stability for nonlinear autonomous ordinary differential equations,, Dyn. Syst., 20 (2005), 281.  doi: 10.1080/14689360500164873.  Google Scholar

[14]

S. F. Hafstein, An Algorithm for Constructing Lyapunov Functions, vol. 8 of Electron. J. Differ. Equ. Monogr.,, Texas State University-San Marcos, (2007).   Google Scholar

[15]

S. Huang, M. R. James, D. Nešić and P. M. Dower, A unified approach to controller design for achieving ISS and related properties,, IEEE Trans. Automat. Control, 50 (2005), 1681.  doi: 10.1109/TAC.2005.858691.  Google Scholar

[16]

Z.-P. Jiang, I. M. Y. Mareels and Y. Wang, A Lyapunov formulation of the nonlinear small-gain theorem for interconnected ISS systems,, Automatica J. IFAC, 32 (1996), 1211.  doi: 10.1016/0005-1098(96)00051-9.  Google Scholar

[17]

H. Li and F. Wirth, Zubov's method for interconnected systems - a dissipative formulation,, in Proc. 20th Int. Symp. Math. Theory of Networks and Systems (MTNS 2012), (2012).   Google Scholar

[18]

S. F. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming,, Dyn. Syst., 17 (2002), 137.  doi: 10.1080/0268111011011847.  Google Scholar

[19]

A. N. Michel, N. R. Sarabudla and R. K. Miller, Stability analysis of complex dynamical systems: Some computational methods,, Circuits Systems Signal Process., 1 (1982), 171.  doi: 10.1007/BF01600051.  Google Scholar

[20]

E. D. Sontag, Smooth stabilization implies coprime factorization,, IEEE Trans. Automat. Control, 34 (1989), 435.  doi: 10.1109/9.28018.  Google Scholar

[21]

E. D. Sontag, Some connections between stabilization and factorization,, in Proc. of the 28th IEEE Conference on Decision and Control (CDC 1989), (1989), 1.   Google Scholar

[22]

E. D. Sontag, Further facts about input to state stabilization,, IEEE Trans. Automat. Control, 35 (1990), 473.  doi: 10.1109/9.52307.  Google Scholar

[23]

E. D. Sontag and Y. Wang, On characterizations of the input-to-state stability property,, Systems Control Lett., 24 (1995), 351.  doi: 10.1016/0167-6911(94)00050-6.  Google Scholar

[24]

E. D. Sontag and Y. Wang, New characterizations of input-to-state stability,, IEEE Trans. Automat. Control, 41 (1996), 1283.  doi: 10.1109/9.536498.  Google Scholar

show all references

References:
[1]

M. Abu Hassan and C. Storey, Numerical determination of domains of attraction for electrical power systems using the method of Zubov,, Internat. J. Control, 34 (1981), 371.  doi: 10.1080/00207178108922536.  Google Scholar

[2]

R. Baier, L. Grüne and S. F. Hafstein, Linear programming based Lyapunov function computation for differential inclusions,, Discrete Contin. Dyn. Syst. Ser. B, 17 (2012), 33.  doi: 10.3934/dcdsb.2012.17.33.  Google Scholar

[3]

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, (2000), 277.  doi: 10.1007/BFb0110220.  Google Scholar

[4]

F. Camilli, L. Grüne and F. Wirth, Domains of attraction of interconnected systems: A Zubov method approach,, in Proc. European Control Conference (ECC 2009), (2009), 91.   Google Scholar

[5]

F. H. Clarke, Y. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory,, Springer-Verlag, (1998).   Google Scholar

[6]

S. Dashkovskiy, B. Rüffer and F. Wirth, A small-gain type stability criterion for large scale networks of ISS systems,, in Proc. of 44th IEEE Conference on Decision and Control and European Control Conference (ECC 2005), (2005), 5633.  doi: 10.1109/CDC.2005.1583060.  Google Scholar

[7]

S. Dashkovskiy, B. Rüffer and F. Wirth, An ISS Lyapunov function for networks of ISS systems,, in Proc. 17th Int. Symp. Math. Theory of Networks and Systems (MTNS 2006), (2006), 77.   Google Scholar

[8]

S. Dashkovskiy, B. Rüffer and F. Wirth, An ISS small-gain theorem for general networks,, Math. Control Signals Systems, 19 (2007), 93.  doi: 10.1007/s00498-007-0014-8.  Google Scholar

[9]

S. N. Dashkovskiy, B. S. Rüffer and F. R. Wirth, Small gain theorems for large scale systems and construction of ISS Lyapunov functions,, SIAM J. Control Optim., 48 (2010), 4089.  doi: 10.1137/090746483.  Google Scholar

[10]

P. Giesl and S. Hafstein, Existence of piecewise linear Lyapunov functions in arbitrary dimensions,, Discrete Contin. Dyn. Syst., 32 (2012), 3539.  doi: 10.3934/dcds.2012.32.3539.  Google Scholar

[11]

L. Grüne and M. Sigurani, Numerical ISS controller design via a dynamic game approach,, in Proc. of the 52nd IEEE Conference on Decision and Control (CDC 2013), (2013), 1732.   Google Scholar

[12]

S. F. Hafstein, A constructive converse Lyapunov theorem on exponential stability,, Discrete Contin. Dyn. Syst., 10 (2004), 657.  doi: 10.3934/dcds.2004.10.657.  Google Scholar

[13]

S. F. Hafstein, A constructive converse Lyapunov theorem on asymptotic stability for nonlinear autonomous ordinary differential equations,, Dyn. Syst., 20 (2005), 281.  doi: 10.1080/14689360500164873.  Google Scholar

[14]

S. F. Hafstein, An Algorithm for Constructing Lyapunov Functions, vol. 8 of Electron. J. Differ. Equ. Monogr.,, Texas State University-San Marcos, (2007).   Google Scholar

[15]

S. Huang, M. R. James, D. Nešić and P. M. Dower, A unified approach to controller design for achieving ISS and related properties,, IEEE Trans. Automat. Control, 50 (2005), 1681.  doi: 10.1109/TAC.2005.858691.  Google Scholar

[16]

Z.-P. Jiang, I. M. Y. Mareels and Y. Wang, A Lyapunov formulation of the nonlinear small-gain theorem for interconnected ISS systems,, Automatica J. IFAC, 32 (1996), 1211.  doi: 10.1016/0005-1098(96)00051-9.  Google Scholar

[17]

H. Li and F. Wirth, Zubov's method for interconnected systems - a dissipative formulation,, in Proc. 20th Int. Symp. Math. Theory of Networks and Systems (MTNS 2012), (2012).   Google Scholar

[18]

S. F. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming,, Dyn. Syst., 17 (2002), 137.  doi: 10.1080/0268111011011847.  Google Scholar

[19]

A. N. Michel, N. R. Sarabudla and R. K. Miller, Stability analysis of complex dynamical systems: Some computational methods,, Circuits Systems Signal Process., 1 (1982), 171.  doi: 10.1007/BF01600051.  Google Scholar

[20]

E. D. Sontag, Smooth stabilization implies coprime factorization,, IEEE Trans. Automat. Control, 34 (1989), 435.  doi: 10.1109/9.28018.  Google Scholar

[21]

E. D. Sontag, Some connections between stabilization and factorization,, in Proc. of the 28th IEEE Conference on Decision and Control (CDC 1989), (1989), 1.   Google Scholar

[22]

E. D. Sontag, Further facts about input to state stabilization,, IEEE Trans. Automat. Control, 35 (1990), 473.  doi: 10.1109/9.52307.  Google Scholar

[23]

E. D. Sontag and Y. Wang, On characterizations of the input-to-state stability property,, Systems Control Lett., 24 (1995), 351.  doi: 10.1016/0167-6911(94)00050-6.  Google Scholar

[24]

E. D. Sontag and Y. Wang, New characterizations of input-to-state stability,, IEEE Trans. Automat. Control, 41 (1996), 1283.  doi: 10.1109/9.536498.  Google Scholar

[1]

Jon Aaronson, Dalia Terhesiu. Local limit theorems for suspended semiflows. Discrete & Continuous Dynamical Systems - A, 2020, 40 (12) : 6575-6609. doi: 10.3934/dcds.2020294
[2]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[3]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018
[4]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034
[5]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[6]

Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020027
[7]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[8]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825
[9]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[10]

Guirong Jiang, Qishao Lu. The dynamics of a Prey-Predator model with impulsive state feedback control. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1301-1320. doi: 10.3934/dcdsb.2006.6.1301
[11]

Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931
[12]

Daoyuan Fang, Ting Zhang. Compressible Navier-Stokes equations with vacuum state in one dimension. Communications on Pure & Applied Analysis, 2004, 3 (4) : 675-694. doi: 10.3934/cpaa.2004.3.675
[13]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[14]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[15]

Michael Grinfeld, Amy Novick-Cohen. Some remarks on stability for a phase field model with memory. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1089-1117. doi: 10.3934/dcds.2006.15.1089
[16]

Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267
[17]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[18]

Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933
[19]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[20]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

2019 Impact Factor: 1.27

Tools

Metrics

  • PDF downloads (44)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences