Semidefinite approximations of invariant measures for polynomial systems

Victor Magron; Marcelo Forets; Didier Henrion

doi:10.3934/dcdsb.2019165

Article Contents

2019, Volume 24, Issue 12: 6745-6770. Doi: 10.3934/dcdsb.2019165

This issue Previous Article Remark on exponential decay-in-time of global strong solutions to 3D inhomogeneous incompressible micropolar equations Next Article Remarks on basic reproduction ratios for periodic abstract functional differential equations

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
^* Corresponding author: Victor Magron

Received: August 2018

Revised: March 2019

Early access: July 2019

Published: September 2019

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 / Introduction Full Text(HTML) Figure(5) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

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} $

Download: Full-size image PowerPoint slide

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)

Download: Full-size image PowerPoint slide

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 $

Download: Full-size image PowerPoint slide

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 $

Download: Full-size image PowerPoint slide

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 $

Download: Full-size image PowerPoint slide

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

Related Papers

Cited by

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.