{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:32:19Z","timestamp":1787319139791,"version":"build-2736575974"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Control Optim."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>In this paper, we present a method for computing a basin of attraction to a target region for polynomial ordinary differential equations. This basin of attraction is ensured by a Lyapunov-like polynomial function that we compute using an interval based branch-and-relax algorithm. This algorithm relaxes the necessary conditions on the coefficients of the Lyapunov-like function to a system of linear interval inequalities that can then be solved exactly. It iteratively refines these relaxations in order to ensure that, whenever a nondegenerate solution exists, it will eventually be found by the algorithm. Application of an implementation to a range of benchmark problems shows the usefulness of the approach.<\/jats:p>","DOI":"10.1137\/090749955","type":"journal-article","created":{"date-parts":[[2010,7,1]],"date-time":"2010-07-01T18:03:28Z","timestamp":1278007408000},"page":"4377-4394","source":"Crossref","is-referenced-by-count":107,"title":["Providing a Basin of Attraction to a Target Region of Polynomial Systems by Computation of Lyapunov-Like Functions"],"prefix":"10.1137","volume":"48","author":[{"given":"Stefan","family":"Ratschan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhikun","family":"She","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,7,1]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"R. Alur and G. J. Pappas, eds.\n                      Hybrid Systems: Computation and Control (HSCC\n                      '04), Lecture Notes in Comput. Sci. 2993, Springer, Berlin, Heidelberg, 2004.","DOI":"10.1007\/b96398"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"F. Benhamou and L. Granvilliers,\n                      Continuous and interval constraints\n                      , in Handbook of Constraint Programming, F. Rossi, P. van Beek, and T. Walsh, eds., Elsevier, Amsterdam, 2006, pp. 571\u2013603.","DOI":"10.1016\/S1574-6526(06)80020-9"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(99)00113-2"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/980175.980185"},{"key":"R5","unstructured":"H. Burchardt, J. Oehlerking, and O. Theel,\n                      The role of state-space partitioning in automated verification of affine hybrid system stability\n                      , in Proceedings of the 3rd International Conference on Computing, Communications, and Control Technologies, Vol. 1, International Institute of Informatics and Systemics, Winter Garden, FL, 2005, pp. 187\u2013192."},{"key":"R6","unstructured":"H. Burchardt and S. Ratschan,\n                      Estimating the region of attraction of ordinary differential equations by quantified constraint solving\n                      , in Proceedings of the 3rd WSEAS International Conference on Dynamical Systems and Control (CONTROL'07), WSEAS Press, Stevens Point, WI, 2007, pp. 241\u2013246."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"B. F. Caviness and J. R. Johnson, eds.\n                      Quantifier Elimination and Cylindrical Algebraic Decomposition\n                      , Springer, Vienna, 1998.","DOI":"10.1007\/978-3-7091-9459-1"},{"key":"R8","first-page":"225","volume":"8","author":"Csendes T.","year":"2000","journal-title":"CEJOR Cent. Eur. J. Oper. Res."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142995281528"},{"key":"R10","unstructured":"N. Delanoue, L. Jaulin, and B. Cottenceau,\n                      Stability analysis of a nonlinear system using interval analysis\n                      , submitted."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/261320.261324"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"K. Forsman,\n                      Construction of Lyapunov functions using Gr\u00f6bner bases\n                      , in Proceedings of the 30th IEEE Conference on Decision and Control, IEEE, Piscataway, NJ, 1991, pp. 798\u2013799.","DOI":"10.1109\/CDC.1991.261424"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1985.1104057"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"P. Giesl,\n                      Construction of Global Lyapunov Functions Using Radial Basis Functions\n                      , Lecture Notes in Math. 1904, Springer, Berlin, Heidelberg, 2007.","DOI":"10.1007\/978-3-540-69909-5"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.3934\/dcds.2004.10.657"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"W. Hahn,\n                      Stability of Motion\n                      , Springer-Verlag, New York, 1967.","DOI":"10.1007\/978-3-642-50085-5"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402416839"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(00)00088-1"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"V. Lakshmikantham, S. Leela, and A. A. Martynyuk,\n                      Practical Stability of Nonlinear Systems\n                      , World Scientific, Singapore, 1990.","DOI":"10.1142\/1192"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580772"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"M. Morari and L. Thiele, eds.\n                      Hybrid Systems: Computation and Control (HSCC'$05$)\n                      , Lecture Notes in Comput. Sci. 3414, Springer, Berlin, Heidelberg, 2005.","DOI":"10.1007\/b106766"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.05.004"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0433-3"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/81.232578"},{"key":"R25","unstructured":"Y. Ohta and M. Onishi,\n                      Stability analysis by using piecewise linear Lyapunov functions\n                      , in Proceedings of the IFAC World Congress, Beijing, 1999, pp. 515\u2013520."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"A. Papachristodoulou and S. Prajna,\n                      On the construction of Lyapunov functions using the sum of squares decomposition\n                      , in Proceedings of the 41st IEEE Conference on Decision and Control, IEEE, Piscataway, NJ, 2002, pp. 3482\u20133487.","DOI":"10.1109\/CDC.2002.1184414"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.3166\/ejc.9.307-321"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"A. Podelski and S. Wagner,\n                      Model checking of hybrid systems: From reachability towards stability\n                      , in Hybrid Systems: Computation and Control (HSCC'06), Lecture Notes in Comput. Sci. 3927, J. Hespanha and A. Tiwari, eds., Springer, Berlin, Heidelberg, 2006, pp. 507\u2013521.","DOI":"10.1007\/11730637_38"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"S. Prajna and A. Jadbabaie,\n                      Safety verification of hybrid systems using barrier certificates\n                      , in Hybrid Systems: Computation and Control (HSCC'04), Lecture Notes in Comput. Sci. 2993, R. Alur and G. J. Pappas, eds., Springer, Berlin, 2004, pp. 171\u2013174.","DOI":"10.1007\/978-3-540-24743-2_32"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"S. Prajna and A. Rantzer,\n                      Primal-dual tests for safety and reachability\n                      , in Hybrid Systems: Computation and Control (HSCC'$05$), Lecture Notes in Comput. Sci. 3414, M. Morari and L. Thiele, eds., Springer, Berlin, Heidelberg, 2005, pp. 542\u2013556.","DOI":"10.1007\/978-3-540-31954-2_35"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"M. O. Rabin,\n                      Decidable theories\n                      , in Handbook of Mathematical Logic, J. Barwise, ed., North-Holland, Amsterdam, 1977, pp. 595\u2013629.","DOI":"10.1016\/S0049-237X(08)71116-9"},{"key":"R32","unstructured":"S. Ratschan,\n                      Continuous first-order constraint satisfaction\n                      , in Artificial Intelligence, Automated Reasoning, and Symbolic Computation, Lecture Notes in Comput. Sci. 2385, J. Calmet, B. Benhamou, O. Caprotti, L. Henocque, and V. Sorge, eds., Springer, Berlin, Heidelberg, 2002, pp. 181\u2013195."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2001.0519"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016246616462"},{"key":"R35","unstructured":"S. Ratschan, RSolver, http:\/\/rsolver.sourceforge.net (2004)."},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1145\/1183278.1183282"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"S. Ratschan and Z. She,\n                      Providing a basin of attraction to a target region by computation of Lyapunov-like functions\n                      , in Proceedings of the IEEE International Conference on Computational Cybernetics, IEEE, Piscataway, NJ, 2006, pp. 1\u20135.","DOI":"10.1109\/ICCCYB.2006.305705"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"E. Rodriguez-Carbonell and D. Kapur,\n                      Automatic generation of polynomial loop invariants: Algebraic foundations\n                      , in Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation (ISSAC), ACM, New York, 2004, pp. 266\u2013273.","DOI":"10.1145\/1005285.1005324"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"E. Rodriguez-Carbonell and A. Tiwari,\n                      Generating polynomial invariants for hybrid systems\n                      , in Hybrid Systems: Computation and Control (HSCC'05), Lecture Notes in Comput. Sci. 3414, M. Morari and L. Thiele, eds., Springer, Berlin, Heidelberg, 2005, pp. 590\u2013605.","DOI":"10.1007\/978-3-540-31954-2_38"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1080\/03081089508818341"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"S. Sankaranarayanan, H. Sipma, and Z. Manna,\n                      Constructing invariants for hybrid systems\n                      , in Hybrid Systems: Computation and Control (HSCC'04), Lecture Notes in Comput. Sci. 2993, R. Alur and G. J. Pappas, eds., Springer, Berlin, Heidelberg, 2004, pp. 69\u201377.","DOI":"10.1007\/978-3-540-24743-2_36"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1080\/00207177508922012"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-07-02022-4"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"A. Tarski,\n                      A Decision Method for Elementary Algebra and Geometry\n                      , University of California Press, Berkeley, 1951.","DOI":"10.1525\/9780520348097"}],"container-title":["SIAM Journal on Control and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090749955","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:45:39Z","timestamp":1787316339000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090749955"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":44,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090749955"],"URL":"https:\/\/doi.org\/10.1137\/090749955","relation":{},"ISSN":["0363-0129","1095-7138"],"issn-type":[{"value":"0363-0129","type":"print"},{"value":"1095-7138","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}