\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Modified refinement algorithm to construct Lyapunov functions using meshless collocation

  • *Corresponding author: Najla Mohammed

    *Corresponding author: Najla Mohammed 
Abstract / Introduction Full Text(HTML) Figure(9) / Table(5) Related Papers Cited by
  • 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.

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

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The Voronoi diagram for a set of sites (green o) with a Voronoi region, Voronoi edge and Voronoi vertex (red *)

    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 $

    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

    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

    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 *)

    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

    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

    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 $

    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

    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
  • [1] C. C. Aggarwal and  C. K. ReddyData 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. LeskovecA. Rajaraman and  J. D. UllmanMining 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.
  • 加载中

Figures(9)

Tables(5)

SHARE

Article Metrics

HTML views(1558) PDF downloads(320) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return