Modified refinement algorithm to construct Lyapunov functions using meshless collocation

Najla Mohammed; Peter Giesl

doi:10.3934/jcd.2022022

Article Contents

2023, Volume 10, Issue 1: 127-151. Doi: 10.3934/jcd.2022022

This issue Previous Article Finding positively invariant sets and proving exponential stability of limit cycles using Sum-of-Squares decompositions Next Article Low-rank kernel approximation of Lyapunov functions using neural networks

Modified refinement algorithm to construct Lyapunov functions using meshless collocation

Najla Mohammed^1, , and
Peter Giesl^2,

1.
Department of Mathematical Sciences, Umm Al-Qura University, Saudi Arabia
2.
Department of Mathematics, University of Sussex, Falmer, BN1 9QH, UK

^*Corresponding author: Najla Mohammed
^*Corresponding author: Najla Mohammed

Received: July 2021

Revised: February 2022

Early access: August 2022

Published: January 2023

Abstract / Introduction Full Text(HTML) Figure(9) / Table(5) Related Papers Cited by

Abstract

Lyapunov functions are functions with negative derivative along solutions of a given ordinary differential equation. Moreover, sublevel sets of a Lyapunov function are subsets of the domain of attraction of the equilibrium. One of the numerical construction methods for Lyapunov functions uses meshless collocation with radial basis functions.

Recently, this method was combined with a grid refinement algorithm (GRA) to reduce the number of collocation points needed to construct Lyapunov functions. However, depending on the choice of the initial set of collocation point, the algorithm can terminate, failing to compute a Lyapunov function. In this paper, we propose a modified grid refinement algorithm (MGRA), which overcomes these shortcomings by adding appropriate collocation points using a clustering algorithm. The modified algorithm is applied to two- and three-dimensional examples.

Keywords:

Mathematics Subject Classification: Primary: 37C75, 37D05, 65M50; Secondary: 37M22, 65P99.

Citation:

FullText(HTML)

Figure 1. The Voronoi diagram for a set of sites (green o) with a Voronoi region, Voronoi edge and Voronoi vertex (red *)

Download: Full-size image PowerPoint slide

Figure 2. Example 7.1, system (17). (a) The points in $ PO_1 $ (green *) lie in the patches where $ v_{9}'(x, y) > 0 $, and the centers to be added to $ X_{9} $ (black *), (b) the level set of $ v_{10}'(x, y) = 0 $, where $ v_{10} $ is the constructed function after adding the 5 centers and the red areas are the patches remaining where $ v_{10}'(x, y) > 0 $

Download: Full-size image PowerPoint slide

Figure 3. Example 7.1, system (17). (a) The level set of $ v_{11}'(x, y) = 0 $ of the constructed function $ v_{11} $ with the set of grid points $ X_{11} $, obtained from the second refinement step. Again, the (red) patches are the areas where $ v_{11}'(x, y) > 0 $, (b) The points in $ PO_2 $ (green *) grouped into 2 clusters, and the cluster centers (black *), calculated by the subtractive clustering method

Download: Full-size image PowerPoint slide

Figure 4. Example 7.1, system (17). (a) The level set of $ v_{13}'(x, y) = 0 $ and the 104 grid points $ X_{13} $ (blue *), as we can see there are no patches remaining at the end, (b) the constructed Lyapunov function $ v_{13}(x, y) $ after the second refinement step

Download: Full-size image PowerPoint slide

Figure 5. Example 7.2, system (18). (a) The level set of $ v_1'(x, y) = 0 $ of the constructed function $ v_1 $ after the last refinement step, started with 48 points and ended up with 60 points, where the (red) patches are the areas where $ v_1'(x, y) > 0 $. (b) The points in $ PO_1 $ (green *) grouped into 8 clusters, and the centers to be added to $ X_1 $ (black *)

Download: Full-size image PowerPoint slide

Figure 6. Example 7.2, system (18). (a) The level set of $ v_5'(x, y) = 0 $ of the constructed function $ v_5 $ with the set $ X_5 $ of grid points obtained from the second refinement step. Again, the (red) patches are the areas where $ v_5'(x, y)>0 $, (b) The points in $ PO_2 $ (green *) grouped into 4 clusters, and the cluster centers (black *), calculated by the subtractive clustering method

Download: Full-size image PowerPoint slide

Figure 7. Example 7.2, system (18). (a) The level set of $ v_7'(x, y) = 0 $ and the grid points $ X_7 = 96 $ (blue *): no patches remain, (b) the constructed Lyapunov function $ v_7(x, y) $ with the MGRA

Download: Full-size image PowerPoint slide

Figure 8. Example 7.3, system (19). (a) The level set of $ v_{{2}}'(x, y, z) = 0 $ (green area) and the 13,908 points in $ PO_1 $ where $ v_{{2}}'(x, y, z)>0 $ (red *); we can see some of the cluster centers as (black *), (b) the level set of $ v_{{3}}'(x, y, z) = 0 $ after adding the 36 cluster centers to the grid points; the green patches denote the points where $ v_{{3}}'(x, y, z)>0 $

Download: Full-size image PowerPoint slide

Figure 9. Example 7.3, system (19). (a) The points in $ PO_4 $, (red *), lie inside the patches where $ v_{{6}}'(x, y, z)>0 $ and some of the cluster centers, which will be added to the grid, are shown as (black *), (b) the level set $ v_{{7}}'(x, y, z) = 0 $ of the orbital derivative calculated with $ X_{{7}} = 462 $ grid points, after adding the 12 centers obtained from the final extension step; no patches remain at the end

Download: Full-size image PowerPoint slide

Table 1. Example 7.1, system (17). The steps of the MGRA performed in sequence, with the number of points added after each step as well as the total number of grid points $ N $ and the functions $ v_i $ in each step. The table also shows the time required, split into the time for computing the coefficients of the function (solving the linear system of size $ N $) and the time to check whether the function $ v_n' $ is negative on the test grid $ X_{test} $

		points		constructed	Time	Time
	Steps	added	$ N $	functions	(computing)	(checking)
1A	refinement	77	93	$ v_0 $–$ v_9 $	0.30 sec.	8.8 sec.
1B	extension	5	98	$ v_{10} $	4.6 sec.	9.4 sec.
2A	refinement	2	100	$ v_{11} $	0.06 sec.	9.5 sec.
2B	extension	2	102	$ v_{12} $	5 sec.	9.7 sec.
3A	refinement	2	104	$ v_{13} $	0.07 sec.	9.9 sec.
					total=10.03 sec.	total= 47.3 sec.

| Show Table

DownLoad: CSV

Table 2. Example 7.2, system (18). The steps of the MGRA performed in sequence, with the number of points added after each step as well as the total number of grid points $ N $ and the functions $ v_i $ in each step. The table also shows the time required, split into the time for computing the coefficients of the function (solving the linear system of size $ N $) and the time to check whether the function $ v_n' $ is negative on the test grid $ X_{test} $

		points		constructed	Time	Time
	Steps	added	$ N $	functions	(computing)	(checking)
1A	refinement	12	60	$ v_0 $–$ v_1 $	0.05 sec.	4.2 sec.
1B	extension	8	68	$ v_2 $	2.2 sec.	4.6 sec.
2A	refinement	20	88	$ v_3 $–$ v_5 $	0.11 sec.	6.0 sec.
2B	extension	4	92	$ v_6 $	3.1 sec.	6.3 sec.
3A	refinement	4	96	$ v_7 $	0.04 sec.	6.7 sec.
					total=5.5 sec.	total=27.8 sec.

| Show Table

DownLoad: CSV

Table 3. Example 7.3, system (19). The steps of the MGRA performed in sequence, with the number of points added after each step as well as the total number of grid points $ N $ and the functions $ v_i $ in each step. The table also shows the time required, split into the time for computing the coefficients of the function (solving the linear system of size $ N $) and the time to check whether the function $ v_n' $ is negative on the test grid $ X_{test} $

		points		constructed	Time	Time
	Steps	added	$ N $	functions	(computing)	(checking)
1A	refinement	56	180	$ v_0 $–$ v_2 $	0.28 sec.	5 min. 48 sec.
1B	extension	36	216	$ v_3 $	1 min. 20 sec.	6 min. 55 sec.
2A	refinement	0	216	–	0.4 sec.	–
2B	extension	22	238	$ v_4 $	1 min. 34 sec.	7 min. 38 sec.
3A	refinement	0	238	–	0.53 sec.	–
3B	extension	44	282	$ v_5 $	1 min. 44 sec.	9 min. 0 sec.
4A	refinement	168	450	$ v_6 $	1.1 sec.	14 min. 38 sec.
4B	extension	12	462	$ v_{7} $	3 min. 20 sec.	15 min. 0 sec.
					total=8 min.	total=59 min.

| Show Table

DownLoad: CSV

Table 4. A comparison of the three algorithms, using basic refinement (1), GRA (2) and MGRA (3). Starting with the same initial grid, we list the final number of points, the overall computation time, including the checking on $ X_{test} $, and separately the time to check the final Lyapunov function on the finer grid $ X_{check} $ with $ h_{check} = 10^{-2} $. The checking time is proportional to the number of collocation points as the checking requires a large number of evaluations of the function

System			Time	Time
starting grid		Final number	entire	final
($ h $, number of points)	Algorithm	of points	algorithm	checking
(17), $ h=1 $, $ N_0=8 $	1	1088	146 sec.	105 sec.
	2	88	9 sec.	8 sec.
	3	88	9 sec.	8 sec.
(17), $ h=2/3 $, $ N_0=16 $	1	624	84 sec.	61 sec.
	2	624	102 sec.	61 sec.
	3	104	57 sec.	10 sec.
(18), $ h=0.6 $, $ N_0=16 $	1	168	16 sec.	11 sec.
	2	168	25 sec.	11 sec.
	3	105	70 sec.	7 sec.

| Show Table

DownLoad: CSV

Table 5. The number of initial grid points $ N_0 $ and the value of $ h $, which we have used to construct Lyapunov functions for Example 7.1, system (17) with GRA. In more detail, the collocation points are $ \{(x, y)\in \mathbb R^2 \mid x, y\in \{-1, -1+h, -1+2h, \ldots, 1-h, 1\}\setminus [-0.1, 0.1]\} $. The last column shows the final number of points after the termination of GRA. "Patches" means that after termination of GRA there are still areas with positive orbital derivative remaining, so no Lyapunov function was constructed

$ h $	$ N_{{0}} $	$ N_{final} $
2/3	16	93 (patches)
1/2	24	88
2/5	36	104 (patches)
1/3	48	94 (patches)
1/4	80	86 (patches)
1/5	120	124 (patches)
1/6	168	168 (patches)
1/7	224	224 (patches)
1/8	288	288 (patches)
1/9	360	360

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	C. C. Aggarwal and C. K. Reddy, Data Clustering: Algorithms and Applications, CRC Press, Boca Raton, 2014. doi: 10.1201/b15410.
[2]	M. de Berg, O. Cheong, M. van Kerveld and M. Overmars, Computational geometry: Algorithms and Applications, Springer-Verlag, Berlin, 2008. doi: 10.1007/978-3-540-77974-2.
[3]	M. D. Buhmann, Radial Basis Functions: Theory and Implementations, volume 12 of Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, Cambridge, 2003. doi: 10.1017/CBO9780511543241.
[4]	S. L. Chiu, Fuzzy model identification based on cluster estimation, Journal of Intelligent & Fuzzy Systems, 2 (1994), 267-278. doi: 10.3233/IFS-1994-2306.
[5]	P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions, Lecture Notes in Math. 1904, Springer, 2007.
[6]	P. Giesl, Construction of a local and global Lyapunov function using radial basis functions, IMA J. Appl. Math., 73 (2008), 782-802. doi: 10.1093/imamat/hxn018.
[7]	P. Giesl and S. Hafstein, Review on computational methods for Lyapunov functions, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2291-2331. doi: 10.3934/dcdsb.2015.20.2291.
[8]	P. Giesl and N. Mohammed, Combination of refinement and verification for the construction of Lyapunov functions using radial basis functions, In Proceedings of the 15th International Conference on Informatics in Control, Automation and Robotics (ICINCO), IEEE, 2018,569-578. doi: 10.5220/0006944405690578.
[9]	P. Giesl and N. Mohammed, Verification estimates for the construction of Lyapunov functions using meshfree collocation, Discrete Contin. Dyn. Syst. Ser. B, 24 (2019), 4955-4981. doi: 10.3934/dcdsb.2019040.
[10]	P. Giesl and H. Wendland, Meshless collocation: Error estimates with application to Dynamical Systems, SIAM J. Numer. Anal., 45 (2007), 1723-1741. doi: 10.1137/060658813.
[11]	S. F. Hafstein, A constructive converse Lyapunov theorem on exponential stability, Discrete and Continuous Dynamical Systems - Series A, 10 (2004), 657-678. doi: 10.3934/dcds.2004.10.657.
[12]	K. Hammouda and F Karray, A comparative study on data clustering techniques, University of Waterloo, Ontario, Canada, 2000.
[13]	S. S. Iyengar, K. G. Boroojeni and N. Balakrishnan, Mathematical Theories of Distributed Sensor Networks, Springer, New York, 2014. doi: 10.1007/978-1-4419-8420-3.
[14]	T. A. Johansen, Computation of Lyapunov functions for smooth, nonlinear systems using convex optimization, Automatica, 36 (2000), 1617-1626. doi: 10.1016/S0005-1098(00)00088-1.
[15]	C. M. Kellett, Classical converse theorems in Lyapunov's second method, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2333-2360. doi: 10.3934/dcdsb.2015.20.2333.
[16]	R. Klein, Concrete and Abstract Voronoi Diagrams, Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1989. doi: 10.1007/3-540-52055-4.
[17]	J. Leskovec, A. Rajaraman and J. D. Ullman, Mining of Massive DataSets, Cambridge University Press, Cambridge, 2014. doi: 10.1017/CBO9781139924801.
[18]	J. L. Massera, On Liapounoff's conditions of stability, Ann. of Math., 50 (1949), 705-721. doi: 10.2307/1969558.
[19]	V. Moertini, Introduction to five data clustering algorithms, INTEGRAL, 7 (2002).
[20]	N. Mohammed, Grid Refinement and Verification Estimates for the RBF Construction Method of Lyapunov Functions, Doctoral thesis (PhD), University of Sussex, 2016.
[21]	N. Mohammed and P. Giesl, Grid refinement in the construction of Lyapunov functions using radial basis functions, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2453-2476. doi: 10.3934/dcdsb.2015.20.2453.
[22]	P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimiza, PhD thesis: California Institute of Technology Pasadena, California, 2000.
[23]	P. K. Pisharady, P. Vadakkepat and L. A. Poh, Computational Intelligence in Multi-feature Visual Pattern Recognition. Hand Posture and Face Recognition using Biological Inspired Approaches, Springer Science+Business Media, Singapore, 2014. doi: 10.1007/978-981-287-056-8.
[24]	M. J. D. Powell, The theory of radial basis function approximation in 1990, In Advances in Numerical Analysis, Vol. II (Lancaster, 1990), Oxford Sci. Publ., Oxford Univ. Press, New York, 1992,105-210.
[25]	F. P. Preparata and M. I. Shamos, Computational Geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. doi: 10.1007/978-1-4612-1098-6.
[26]	R. Schaback and H. Wendland, Kernel techniques: From machine learning to meshless methods, Acta Numer., 15 (2006), 543-639. doi: 10.1017/S0962492906270016.
[27]	V. Torra, Information Fusion in Data Mining, Springer-Verlag, Berlin, 2003. doi: 10.1007/978-3-540-36519-8.
[28]	H. Wendland, Error estimates for interpolation by compactly supported Radial Basis Functions of minimal degree, J. Approx. Theory, 93 (1998), 258-272. doi: 10.1006/jath.1997.3137.
[29]	H. Wendland, Scattered Data Approximation, volume 17 of Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, Cambridge, 2005.
[30]	R. R. Yager and D. P. Filev, Generation of fuzzy rules by mountain clustering, Journal of Intelligent & Fuzzy Systems, 2 (1993), 209-219. doi: 10.3233/IFS-1994-2301.