Advanced Search
Article Contents
Article Contents

Semidefinite approximations of invariant measures for polynomial systems

  • * Corresponding author: Victor Magron

    * Corresponding author: Victor Magron 

The first author benefited from the support of the FMJH Program PGMO (EPICS project) and EDF, Thales, Orange et Criteo, as well as from the Tremplin ERC Stg Grant ANR-18-ERC2-0004-01 (T-COPS project). The research of the third author was funded by the European Research Council (ERC) under the European's Union Horizon 2020 research and innovation program (grant agreement 666981 TAMING project)

Abstract Full Text(HTML) Figure(5) / Table(1) Related Papers Cited by
  • We consider the problem of approximating numerically the moments and the supports of measures which are invariant with respect to the dynamics of continuous- and discrete-time polynomial systems, under semialgebraic set constraints. First, we address the problem of approximating the density and hence the support of an invariant measure which is absolutely continuous with respect to the Lebesgue measure. Then, we focus on the approximation of the support of an invariant measure which is singular with respect to the Lebesgue measure.

    Each problem is handled through an appropriate reformulation into a conic optimization problem over measures, solved in practice with two hierarchies of finite-dimensional semidefinite moment-sum-of-square relaxations, also called Lasserre hierarchies.

    Under specific assumptions, the first Lasserre hierarchy allows to approximate the moments of an absolutely continuous invariant measure as close as desired and to extract a sequence of polynomials converging weakly to the density of this measure.

    The second Lasserre hierarchy allows to approximate as close as desired in the Hausdorff metric the support of a singular invariant measure with the level sets of the Christoffel polynomials associated to the moment matrices of this measure.

    We also present some application examples together with numerical results for several dynamical systems admitting either absolutely continuous or singular invariant measures.

    Mathematics Subject Classification: 90C22, 37L40, 93C55.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Approximate invariant density for the dynamics from (29) with corresponding approximations $ h_2^r $ (solid curve) of the exact density $ h^\star $ (dashed curve) for $ r \in \{4,6,8\} $ and $ w = \frac{\sqrt{99}}{10} $

    Figure 2.  Approximate invariant density for the piecewise systems defined respectively in (31), (32) and (33) with corresponding approximations $ h_\infty^r $ (solid curve) of the exact density $ h^\star $ (dashed curve)

    Figure 3.  Hénon attractor (blue) and approximations $ {\bf{S}}^r $ (light gray) for the support of the invariant measure w.r.t. the map from Example 5.2.1 for $ r \in \{4,6,8\} $, $ a = 1.4 $ and $ b = 0.3 $

    Figure 4.  Van der Pol attractor (blue) and approximations $ {\bf{S}}^r $ (light gray) for the support of the invariant measure w.r.t. the map from Example 5.2.2 for $ r \in \{4,6,8\} $ and $ a = 0.5 $

    Figure 5.  Arneodo-Coullet attractor (blue) and approximations $ {\bf{S}}^4 $ (red) for the support of the invariant measure w.r.t. the map from Example 5.2.3 for $ a = -5.5 $, $ b = 3.5 $ and $ c = -1 $

    Table 1.  Comparison of timing results for the dynamics from (29)

    relaxation order $ r $ 4 6 8
    moments 70 168 330
    variables 245 1035 3199
    time (s) 0.89 1.05 1.37
     | Show Table
    DownLoad: CSV
  • [1] M. R. Abdalmoaty, D. Henrion and L. Rodrigues, Measures and LMIs for Optimal Control of Piecewise-affine Systems, Proceedings of the European Control Conference (ECC), 2013. doi: 10.23919/ECC.2013.6669627.
    [2] L. AmbrosioN. Fusco and  D. PallaraFunctions of Bounded Variation and Free Discontinuity Problems, Clarendon Press, 2000. 
    [3] E. D. Andersen and K. D. Andersen, The mosek interior point optimizer for linear programming: An implementation of the homogeneous algorithm, High Performance Optimization, Appl. Optim., Kluwer Acad. Publ., Dordrecht, 33 (2000), 197-232. doi: 10.1007/978-1-4757-3216-0_8.
    [4] A. ArneodoP. H. CoulletE. A. Spiegel and C. Tresser, Asymptotic chaos, Physica D Nonlinear Phenomena, 14 (1985), 327-347.  doi: 10.1016/0167-2789(85)90093-4.
    [5] P. Astod and O. Junge, Computing the invariant measure and the Lyapunov exponent for one-dimensional maps using a measure-preserving polynomial basis, Mathematics of Computation, 83 (2014), 1869-1902.  doi: 10.1090/S0025-5718-2013-02811-6.
    [6] A. Barvinok, A Course in Convexity, American Mathematical Society, 2002. doi: 10.1090/gsm/054.
    [7] M. Dellnitz, G. Froyland and O. Junge, The algorithms behind GAIOSet oriented numerical methods for dynamical systems, In Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems, Springer, (2001), 145-174, 805-807.
    [8] M. DellnitzA. HohmannO. Junge and M. Rumpf, Exploring invariant sets and invariant measures, CHAOS: An Interdisciplinary Journal of Nonlinear Science, 7 (1997), 221-228.  doi: 10.1063/1.166223.
    [9] M. DellnitzS. Klus and A. Ziessler, A set-oriented numerical approach for dynamical systems with parameter uncertainty, SIAM Journal on Applied Dynamical Systems, 16 (2017), 120-138.  doi: 10.1137/16M1072735.
    [10] M. Hénon, A two-dimensional mapping with a strange attractor, Communications in Mathematical Physics, 50 (1976), 69-77.  doi: 10.1007/BF01608556.
    [11] D. Henrio, Semidefinite characterisation of invariant measures for one-dimensional discrete dynamical systems, Kybernetika, 48 (2012), 1089-1099. 
    [12] D. Henrion and M. Korda, Convex computation of the region of attraction of polynomial control systems, IEEE Transactions on Automatic Control, 59 (2014), 297-312.  doi: 10.1109/TAC.2013.2283095.
    [13] D. HenrionJ. B. Lasserre and C. Savorgnan, Approximate volume and integration for basic semialgebraic sets, SIAM Review, 51 (2009), 722-743.  doi: 10.1137/080730287.
    [14] D. Henrion and J. -B. Lasserre, Detecting global optimality and extracting solutions in gloptiPoly, In Positive Polynomials in Control, Springer, 312 (2005), 293-310. doi: 10.1007/10997703_15.
    [15] D. HenrionJ. -B. Lasserre and J. Löfberg, GloptiPoly 3: Moments, optimization and semidefinite programming, Optimization Methods and Software, 24 (2009), 761-779.  doi: 10.1080/10556780802699201.
    [16] D. HenrionJ. -B. Lasserre and M. Mevissen, Mean squared error minimization for inverse moment problems, Applied Mathematics & Optimization, 70 (2014), 83-110.  doi: 10.1007/s00245-013-9235-z.
    [17] T. Kohda and K. Murao, Piecewise polynomial Galerkin approximation to invariant densities of one-dimensional difference equations, Electronics and Communications in Japan (Part Ⅰ: Communications), 65 (1982), 1-11.  doi: 10.1002/ecja.4410650602.
    [18] M. Korda, D. Henrion and C. N. Jones, Convex computation of the maximum controlled invariant set for discrete-time polynomial control systems, In SIAM J. Control Optim., 52 (2014), 2944-2969. doi: 10.1137/130914565.
    [19] M. Korda, D. Henrion and I. Mezić, Convex Computation of Extremal Invariant Measures of Nonlinear Dynamical Systems and Markov Processes, 2018, arXiv: 1807.08956, https://arXiv.org/abs/1807.08956.
    [20] N. Kryloff and N. Bogoliouboff, La théorie générale de la mesure dans son application á l'étude des systémes dynamiques de la mécanique non linéaire, Annals of Mathematics, 38 (1937), 65-113.  doi: 10.2307/1968511.
    [21] A. Lasota, and M. C. Mackey, Chaos, Fractals, and Noise: Stochastic Aspects of Dynamics, Springer, 1994. doi: 10.1007/978-1-4612-4286-4.
    [22] J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on Optimization, 11 (2000), 796-817.  doi: 10.1137/S1052623400366802.
    [23] J. B. LasserreMoments, Positive Polynomials and Their Applications, Imperial College Press, 2010. 
    [24] J. B. Lasserre, Borel measures with a density on a compact semi-algebraic set, Archiv der Mathematik, 101 (2013), 361-371.  doi: 10.1007/s00013-013-0557-5.
    [25] J. B. Lasserre, Lebesgue decomposition in action via semidefinite relaxations, Advances in Computational Mathematics, 42 (2016), 1129-1148.  doi: 10.1007/s10444-016-9456-1.
    [26] J. B. Lasserre and T. Netzer, SOS approximations of nonnegative polynomials via simple high degree perturbations, Math. Z., 256 (2007), 99-112.  doi: 10.1007/s00209-006-0061-8.
    [27] J. -B. Lasserre an E. Pauwels, The Empirical Christoffel Function in Statistics and Machine Learning, 2017, arXiv: 1701.02886, https://arXiv.org/abs/1701.02886.
    [28] E. H. Lieb and M. Loss, Analysis, Second Edition, Graduate Studies in Mathematics, 14. American Mathematical Society, Providence, RI, 2001. doi: 10.1090/gsm/014.
    [29] D. G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, 1968.
    [30] J. Lfberg, YALMIP: A Toolbox for Modeling and Optimization in MATLAB, In Proceedings of the IEEE CACSD Symposium, 2004. doi: 10.1109/CACSD.2004.1393890.
    [31] V. Magron, P. -L. Garoche, D. Henrion and X. Thirioux, Semidefinite Approximations of Reachable Sets for Discrete-time Polynomial Systems, arXiv: 1703.05085, 2019.
    [32] H. L. Royden and P. Fitzpatrick, Real Analysis, Prentice Hall, 2010.
    [33] M. Trnovská, Strong duality conditions in semidefinite programming, Journal of Electrical Engineering, 56 (2005), 1-5. 
    [34] S. M. Ulam and J. von Neumann, On combinations of stochastic and deterministic processes, Bull. Amer. Math. Soc., 53 (1947), 1120. 
    [35] B. Van der Pol, On relaxation oscillations, The London, Edinburgh and Dublin Phil. Mag. & J. of Sci., 2 (1926), 978-992. 
    [36] H. Weyl, Über die Gibbs'sche Erscheinung und Verwandte KonvergenzphÄnomene, Rendiconti del Circolo Matematico di Palermo, 30 (1910), 377-407.  doi: 10.1007/BF03014883.
    [37] K. Yosida, Functional Analysis, Springer-Verlag, Berlin-New York, 1980.
    [38] K. Yosida and E. Hewitt, Finitely additive measures, Transactions of the American Mathematical Society, 72 (1952), 46-66.  doi: 10.1090/S0002-9947-1952-0045194-X.
  • 加载中




Article Metrics

HTML views(614) PDF downloads(126) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint