×

Semidefinite approximations of reachable sets for discrete-time polynomial systems. (English) Zbl 1421.90110

Summary: We consider the problem of approximating the reachable set of a discrete-time polynomial system from a semialgebraic set of initial conditions under general semialgebraic set constraints. Assuming inclusion in a given simple set like a box or an ellipsoid, we provide a method to compute certified outer approximations of the reachable set. The proposed method consists of building a hierarchy of relaxations for an infinite-dimensional moment problem. Under certain assumptions, the optimal value of this problem is the volume of the reachable set and the optimum solution is the restriction of the Lebesgue measure on this set. Then, one can outer approximate the reachable set as closely as desired with a hierarchy of super level sets of increasing degree polynomials. For each fixed degree, finding the coefficients of the polynomial boils down to computing the optimal solution of a convex semidefinite program. When the degree of the polynomial approximation tends to infinity, we provide strong convergence guarantees of the super level sets to the reachable set. We also present some application examples together with numerical results.

MSC:

90C22 Semidefinite programming
93C55 Discrete-time control/observation systems
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] L. Ambrosio, N. Fusco, and D. Pallara, Functions of Bounded Variation and Free Discontinuity Problems, Oxford Mathematical Monographs, Clarendon Press, Oxford University Press, New York, 2000. · Zbl 0957.49001
[2] 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. 33, H. Frenk, K. Roos, T. Terlaky, and S. Zhang, eds., Kluwer Academic Publishers, Dordrecht, 2000, pp. 197-232. · Zbl 1028.90022
[3] R. B. Ash, Real Analysis and Probability, Academic Press, New York, 1972. · Zbl 1381.28001
[4] A. Barvinok, A Course in Convexity, Grad. Stud. Math. 54, American Mathematical Society, Providence, RI, 2002. · Zbl 1014.52001
[5] M. A. Ben Sassi, S. Sankaranarayanan, X. Chen, and E. Ábrahám, Linear relaxations of polynomial positivity for polynomial Lyapunov function synthesis, IMA J. Math. Control Inform., 33 (2016), pp. 723-756. · Zbl 1397.93189
[6] M. A. Ben Sassi, R. Testylier, T. Dang, and A. Girard, Reachability analysis of polynomial systems using linear programming relaxations, International Symposium on Automated Technology for Verification and Analysis (ATVA), Lecture Notes in Comput. Sci. 7561. Springer, Berlin, Heidelberg, 2012, pp. 137-151. · Zbl 1375.68077
[7] O. Bernard and J.-L. Gouzé, Global qualitative description of a class of nonlinear dynamical systems, Artificial Intelligence, 136 (2002), pp. 29-59. · Zbl 0984.68186
[8] D. Bertsekas, Infinite time reachability of state-space regions by using feedback control, IEEE Trans. Automatic Control, AC-17 (1972), pp. 604-613. · Zbl 0264.93011
[9] F. Blanchini, Set invariance in control, Automatica J. IFAC, 35 (1999), pp. 1747-1767. · Zbl 0935.93005
[10] F. Blanchini and S. Miani, Set-Theoretic Methods in Control, Systems & Control: Foundations & Applications, Birkhäuser Boston, Boston, 2007. · Zbl 1131.93018
[11] G. Chesi, Domain of Attraction. Analysis and Control via SOS Programming, Lect. Notes Control Inf. Sci. 415, Springer-Verlag, Berlin, 2011. · Zbl 1242.93099
[12] A. Donzé, Breach, A Toolbox for Verification and Parameter Synthesis of Hybrid Systems, Computer Aided Verification (CAV), Lecture Notes in Comput. Sci. 6174. Springer, Berlin, Heidelberg, 2010, pp. 167-170.
[13] T. Dreossi, Sapo: Reachability Computation and Parameter Synthesis of Polynomial Dynamical Systems, IN Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control (HSCC), 2017, ACM, New York, pp. 29-34. · Zbl 1369.68257
[14] R. FitzHugh, Impulses and physiological states in theoretical models of nerve membrane, Biophys J., 1 (1961), pp. 445-466.
[15] S. M. Harwood and P. I. Barton, Efficient polyhedral enclosures for the reachable set of nonlinear control systems, Math. Control Signals Systems, 28 (2016), 8. · Zbl 1338.93064
[16] D. Henrion and M. Korda, Convex Computation of the Region of Attraction of Polynomial Control Systems, IEEE Trans. Automat. Control, 59 (2014), pp. 297-312. · Zbl 1360.93601
[17] D. Henrion and J. B. Lasserre, Inner approximations for polynomial matrix inequalities and robust stability regions, IEEE Trans. Automat. Control, 57 (2012), pp. 1456-1467. · Zbl 1369.93460
[18] D. Henrion, J. B. Lasserre, and C. Savorgnan, Approximate volume and integration for basic semialgebraic sets, SIAM Rev., 51 (2009), pp. 722-743, https://doi.org/10.1137/080730287. · Zbl 1179.14037
[19] V. A. Jakubovič, S-procedure in nonlinear control theory, Vestnik Leningrad. Univ., 1 (1971), pp. 62-77. · Zbl 0232.93010
[20] M. Korda, D. Henrion, and C. N. Jones, Inner approximations of the region of attraction for polynomial dynamical systems, in Proceedings of the 9th IFAC Symposium on Nonlinear Control Systems (NOLCOS), 2013, pp. 534-539.
[21] M. Korda, D. Henrion, and C. N. Jones, Convex computation of the maximum controlled invariant set for discrete-time polynomial control systems, in Proceedings of the 52nd IEEE Conference on Decision and Control, 2013, pp. 7107-7112.
[22] M. Korda, D. Henrion, and I. Mezić, Convex computation of extremal invariant measures of nonlinear dynamical systems and Markov processes, submitted, http://www.optimization-online.org/DB_FILE/2018/07/6717.pdf, 2018. · Zbl 1467.37080
[23] J.-B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796-817, https://doi.org/10.1137/S1052623400366802. · Zbl 1010.90061
[24] J.-B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press Optimization Series, Imperial College Press, London, 2010. · Zbl 1211.90007
[25] J.-B. Lasserre, Tractable approximations of sets defined with quantifiers, Math. Program., 151 (2015), pp. 507-527. · Zbl 1328.90100
[26] E. H. Lieb and M. Loss, Analysis, Grad. Stud. Math. 14, American Mathematical Society, Providence, RI, 2001. · Zbl 0966.26002
[27] D. G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, New York, 1969. · Zbl 0176.12701
[28] J. Löfberg, Yalmip: A toolbox for modeling and optimization in MATLAB, in Proceedings of the 2004 IEEE International Symposium on Computer Aided Control Systems Design (CACSD), 2004, pp. 284-289.
[29] V. Magron, X. Allamigeon, S. Gaubert, and B. Werner, Formal proofs for Nonlinear Optimization, J. Formaliz. Reason., 8 (2015), pp. 1-24. · Zbl 1451.90131
[30] V. Magron, M. Forets, and D. Henrion, Semidefinite Approximations of Invariant Measures for Polynomial Systems, accepted for publication in Discrete and Continuous Dynamical Systems Series B, preprint, https://arxiv.org/abs/1807.00754, 2018.
[31] V. Magron, D. Henrion, and J.-B. Lasserre, Semidefinite approximations of projections and polynomial images of semialgebraic sets, SIAM J. Optim., 25 (2015), pp. 2143-2164, https://doi.org/10.1137/140992047. · Zbl 1327.14241
[32] C. Mira, A. Barugola, J.-C. Cathala, and L. Gardini, Chaotic Dynamics in Two-Dimensional Noninvertible Maps, World Sci. Ser. Nonlinear Sci. Ser. A Monogr. Treatises 20, World Scientific, River Edge, NJ, 1996. · Zbl 0906.58027
[33] S. Prajna and A. Jadbabaie, Safety Verification of Hybrid Systems Using Barrier Certificates, Hybrid Systems: Computation and Control (HSCC), Lecture Notes in Comput. Sci. 2993, Alurands Pappas, eds., Springer, Berlin, Heidelberg, 2004, pp. 477-492. · Zbl 1135.93317
[34] H. L. Royden and P. Fitzpatrick, Real Analysis, Featured Titles for Real Analysis Series, Prentice Hall, New York, 2010, pp. 1499-1506. · Zbl 1191.26002
[35] V. Shia, R. Vasuvedan, R. Bajcsy, and R. Tedrake, Convex computation of the reachable set for controlled polynomial hybrid systems, IEEE Conference on Decision and Control (CDC), 2014.
[36] E. D. Sontag, Mathematical Control Theory: Deterministic Finite Dimensional Systems, Texts Appl. Math. 6, Springer-Verlag, New York, 1990. · Zbl 0703.93001
[37] M. H. Stone, The generalized Weierstrass approximation theorem, Math. Mag., 21 (1948), pp. 167-184.
[38] M. Trnovská, Strong duality conditions in semidefinite programming, J. Electr. Eng., 56 (2005), pp. 1-5. · Zbl 1105.90057
[39] A. Vannelli and M. Vidyasagar, Maximal Lyapunov functions and domains of attraction for autonomous nonlinear systems, Automatica J. IFAC, 21 (1985), pp. 69-80. · Zbl 0559.34052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.