American Institute of Mathematical Sciences

• Previous Article
Remarks on basic reproduction ratios for periodic abstract functional differential equations
• DCDS-B Home
• This Issue
• Next Article
Remark on exponential decay-in-time of global strong solutions to 3D inhomogeneous incompressible micropolar equations
December  2019, 24(12): 6745-6770. doi: 10.3934/dcdsb.2019165

Semidefinite approximations of invariant measures for polynomial systems

 1 CNRS; LAAS; Université de Toulouse, 7 avenue du colonel Roche, F-31400 Toulouse, France 2 Universidad de la República, CURE, Maldonado, Uruguay 3 Faculty of Electrical Engineering, Czech Technical University in Prague, Technická 4, CZ-16206 Prague, Czechia

* Corresponding author: Victor Magron

Received  August 2018 Revised  March 2019 Published  December 2019 Early access  July 2019

Fund Project: 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).

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.

Citation: Victor Magron, Marcelo Forets, Didier Henrion. Semidefinite approximations of invariant measures for polynomial systems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (12) : 6745-6770. doi: 10.3934/dcdsb.2019165
References:
 [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. Ambrosio, N. Fusco and D. Pallara, Functions 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. Arneodo, P. H. Coullet, E. 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. Dellnitz, A. Hohmann, O. 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. Dellnitz, S. 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. Henrion, J. 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. Henrion, J. -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. Henrion, J. -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. Lasserre, Moments, 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.

show all references

References:
 [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. Ambrosio, N. Fusco and D. Pallara, Functions 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. Arneodo, P. H. Coullet, E. 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. Dellnitz, A. Hohmann, O. 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. Dellnitz, S. 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. Henrion, J. 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. Henrion, J. -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. Henrion, J. -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. Lasserre, Moments, 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.
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}$
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)
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$
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$
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$
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
 relaxation order $r$ 4 6 8 moments 70 168 330 variables 245 1035 3199 time (s) 0.89 1.05 1.37
 [1] Ivan Werner. Equilibrium states and invariant measures for random dynamical systems. Discrete and Continuous Dynamical Systems, 2015, 35 (3) : 1285-1326. doi: 10.3934/dcds.2015.35.1285 [2] Oliver Jenkinson. Optimization and majorization of invariant measures. Electronic Research Announcements, 2007, 13: 1-12. [3] Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 [4] Xin Li, Wenxian Shen, Chunyou Sun. Invariant measures for complex-valued dissipative dynamical systems and applications. Discrete and Continuous Dynamical Systems - B, 2017, 22 (6) : 2427-2446. doi: 10.3934/dcdsb.2017124 [5] Grzegorz Łukaszewicz, James C. Robinson. Invariant measures for non-autonomous dissipative dynamical systems. Discrete and Continuous Dynamical Systems, 2014, 34 (10) : 4211-4222. doi: 10.3934/dcds.2014.34.4211 [6] Reza Kamyar, Matthew M. Peet. Polynomial optimization with applications to stability analysis and control - Alternatives to sum of squares. Discrete and Continuous Dynamical Systems - B, 2015, 20 (8) : 2383-2417. doi: 10.3934/dcdsb.2015.20.2383 [7] Zhiming Li, Lin Shu. The metric entropy of random dynamical systems in a Hilbert space: Characterization of invariant measures satisfying Pesin's entropy formula. Discrete and Continuous Dynamical Systems, 2013, 33 (9) : 4123-4155. doi: 10.3934/dcds.2013.33.4123 [8] Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881 [9] Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030 [10] Ji Li, Kening Lu, Peter W. Bates. Invariant foliations for random dynamical systems. Discrete and Continuous Dynamical Systems, 2014, 34 (9) : 3639-3666. doi: 10.3934/dcds.2014.34.3639 [11] Zhang Chen, Xiliang Li, Bixiang Wang. Invariant measures of stochastic delay lattice systems. Discrete and Continuous Dynamical Systems - B, 2021, 26 (6) : 3235-3269. doi: 10.3934/dcdsb.2020226 [12] Fanni M. Sélley. A self-consistent dynamical system with multiple absolutely continuous invariant measures. Journal of Computational Dynamics, 2021, 8 (1) : 9-32. doi: 10.3934/jcd.2021002 [13] Sho Matsumoto, Jonathan Novak. A moment method for invariant ensembles. Electronic Research Announcements, 2018, 25: 60-71. doi: 10.3934/era.2018.25.007 [14] Henri Schurz. Moment attractivity, stability and contractivity exponents of stochastic dynamical systems. Discrete and Continuous Dynamical Systems, 2001, 7 (3) : 487-515. doi: 10.3934/dcds.2001.7.487 [15] Sergey Shemyakov, Roman Chernov, Dzmitry Rumiantsau, Dierk Schleicher, Simon Schmitt, Anton Shemyakov. Finding polynomial roots by dynamical systems – A case study. Discrete and Continuous Dynamical Systems, 2020, 40 (12) : 6945-6965. doi: 10.3934/dcds.2020261 [16] Elena Goncharova, Maxim Staritsyn. Optimal control of dynamical systems with polynomial impulses. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4367-4384. doi: 10.3934/dcds.2015.35.4367 [17] Valery A. Gaiko. The geometry of limit cycle bifurcations in polynomial dynamical systems. Conference Publications, 2011, 2011 (Special) : 447-456. doi: 10.3934/proc.2011.2011.447 [18] Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015 [19] Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034 [20] Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187

2020 Impact Factor: 1.327