{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,16]],"date-time":"2025-11-16T21:47:08Z","timestamp":1763329628883},"reference-count":64,"publisher":"Oxford University Press (OUP)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IMA J Math Control Info"],"published-print":{"date-parts":[[2016,9]]},"DOI":"10.1093\/imamci\/dnv003","type":"journal-article","created":{"date-parts":[[2015,2,18]],"date-time":"2015-02-18T05:13:27Z","timestamp":1424236407000},"page":"723-756","source":"Crossref","is-referenced-by-count":24,"title":["Linear relaxations of polynomial positivity for polynomial Lyapunov function synthesis"],"prefix":"10.1093","volume":"33","author":[{"given":"Mohamed Amin","family":"Ben Sassi","sequence":"first","affiliation":[]},{"given":"Sriram","family":"Sankaranarayanan","sequence":"additional","affiliation":[]},{"given":"Xin","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Erika","family":"\u00c1brah\u00e1m","sequence":"additional","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2015,2,17]]},"reference":[{"key":"2016090600134130000_33.3.723.1","doi-asserted-by":"crossref","unstructured":"Ahmadi A. A. Krstic M. Parrilo P. A. (2011) A globally asymptotically stable polynomial vector field with no polynomial Lyapunov function. Proceedings of the 50th IEEE Conference on Decision and Control, 2011, pp. 7579\u20137580","DOI":"10.1109\/CDC.2011.6161499"},{"key":"2016090600134130000_33.3.723.2","doi-asserted-by":"crossref","unstructured":"Ahmadi A. Majumdar A. (2014) DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization. International Conference on Information Sciences and Systems (CISS), Princeton University. IEEE Press, pp. 1\u20135.","DOI":"10.1109\/CISS.2014.6814141"},{"key":"2016090600134130000_33.3.723.3","first-page":"1","article-title":"D\u00e9monstration du th\u00e9or\u00e9me de Weierstrass fond\u00e9e sur le calcul des probabilit\u00e9s","volume":"13","author":"Bernstein","year":"1912","journal-title":"Comm. Kharkov Math. Soc."},{"key":"2016090600134130000_33.3.723.4","first-page":"227","article-title":"On the representation of positive polynomials","volume":"2","author":"Bernstein","year":"1915","journal-title":"Soobshch Kharkov marem ob-va"},{"key":"2016090600134130000_33.3.723.5","unstructured":"Bernstein S. (1952) Collected Works, vol. 1. USSR Academy of Sciences. Russia."},{"key":"2016090600134130000_33.3.723.6","unstructured":"Bernstein S. (1954) Collected Works, vol. 2. USSR Academy of Sciences. Russia."},{"key":"2016090600134130000_33.3.723.7","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1016\/j.sysconle.2006.10.012","article-title":"Estimating the domain of attraction via union of continuous families of Lyapunov estimates","volume":"56","author":"Chesi","year":"2005","journal-title":"Syst. Control Lett."},{"key":"2016090600134130000_33.3.723.8","doi-asserted-by":"publisher","DOI":"10.1080\/00207720903078867"},{"key":"2016090600134130000_33.3.723.9","doi-asserted-by":"publisher","DOI":"10.1002\/rnc.967"},{"key":"2016090600134130000_33.3.723.10","unstructured":"Collins G. (1975) Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Automata Theory and Formal Languages ( Brakhage H. , ed.), Lecture Notes in Computer Science 33. Berlin: Springer, pp. 134\u2013183."},{"key":"2016090600134130000_33.3.723.11","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80152-6"},{"key":"2016090600134130000_33.3.723.12","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/3-540-45319-9_6","article-title":"Synthesis of linear ranking functions","volume-title":"Tools and Algorithms for Construction and Analysis of Systems","volume":"2031","author":"Colon","year":"2001"},{"key":"2016090600134130000_33.3.723.13","unstructured":"Dang T. Salinas D. (2009) Image computation for polynomial dynamical systems using the Bernstein expansion. CAV\u201909, LNCS 5643. Berlin: Springer, pp. 219\u2013232."},{"key":"2016090600134130000_33.3.723.14","unstructured":"Datta R. (2002) Computing Handelman representations. Mathematical Theory of Networks and Systems, 2002. Cf. math.berkeley.edu\/\u223cdatta\/MTNSHandelman.ps ."},{"key":"2016090600134130000_33.3.723.15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/261320.261324","article-title":"REDLOG: computer algebra meets computer logic","volume":"31","author":"Dolzmann","year":"1997","journal-title":"ACM SIGSAM Bull."},{"key":"2016090600134130000_33.3.723.16","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2012.03.001"},{"key":"2016090600134130000_33.3.723.17","doi-asserted-by":"crossref","unstructured":"Forsman K. (1991) Construction of Lyapunov functions using Gr\u00f6bner bases. Proceedings of the 30th IEEE Conference on Decision and Control. IEEE, Brighton, December, pp. 798\u2013799.","DOI":"10.1109\/CDC.1991.261424"},{"key":"2016090600134130000_33.3.723.18","unstructured":"Garey M. R. Johnson D. S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Oxford: W.H.Freeman."},{"key":"2016090600134130000_33.3.723.19","first-page":"154","article-title":"The Bernstein algorithm","volume":"2","author":"Garloff","year":"1993","journal-title":"Reliab. Comput."},{"key":"2016090600134130000_33.3.723.20","doi-asserted-by":"crossref","unstructured":"Goubault E. Jourdan J.-H. Putot S. Sankaranarayanan S. (2014) Finding non-polynomial positive invariants and Lyapunov functions for polynomial systems through Darboux polynomials. Proc. American Control Conference (ACC). Portland: IEEE Press, pp. 3571\u20133578.","DOI":"10.1109\/ACC.2014.6859330"},{"key":"2016090600134130000_33.3.723.21","unstructured":"Hafstein S. (2002) Stability analysis of nonlinear systems with linear programming. Ph.D. Thesis, Gerhard-Mercator-University Duisburg."},{"key":"2016090600134130000_33.3.723.22","first-page":"610","article-title":"Revised CPA method to compute Lyapunov functions for nonlinear systems","volume":"4","author":"Hafstein","year":"2014","journal-title":"J. Math. Anal. Appl."},{"key":"2016090600134130000_33.3.723.23","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1988.132.35"},{"key":"2016090600134130000_33.3.723.24","doi-asserted-by":"crossref","unstructured":"Harrison J. (2007) Verifying nonlinear real formulas via sums of squares. Proceeding of the International Conference on Theorem Proving in Higher Order Logics ( Schneider K. Brandt J. , eds), Lecture Notes in Computer Science 4732. Berlin: Springer, 2007, pp. 102\u2013118.","DOI":"10.1007\/978-3-540-74591-4_9"},{"key":"2016090600134130000_33.3.723.25","unstructured":"H\u00e4rter V. Jansson C. Lange M. (2012) VSDP: A matlab toolbox for verified semidefinte-quadratic-linear programming. Cf. http:\/\/www.ti3.tuhh.de\/jansson\/vsdp\/ ."},{"key":"2016090600134130000_33.3.723.26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01378337"},{"key":"2016090600134130000_33.3.723.27","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2005.863494"},{"key":"2016090600134130000_33.3.723.28","unstructured":"Jarvis-Wloszek Z. W. (2003) Lyapunov based analysis and controller synthesis for polynomial systems using sum-of-squares optimization. Ph.D. Thesis, UC Berkeley."},{"key":"2016090600134130000_33.3.723.29","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(00)00088-1"},{"key":"2016090600134130000_33.3.723.30","doi-asserted-by":"publisher","DOI":"10.3166\/ejc.13.152-170"},{"key":"2016090600134130000_33.3.723.31","unstructured":"Kamyar R. Peet M. M. (2014) Polynomial optimization with applications to stability analysis and control\u2014alternatives to sum of squares. arXiv, vol. abs\/1408.5119, Available online: http:\/\/arxiv.org\/abs\/1408.5119 ."},{"key":"2016090600134130000_33.3.723.32","doi-asserted-by":"crossref","unstructured":"Kapinski J. Deshmukh J. V. Sankaranarayanan S. Arechiga N. (2014) Simulation-guided Lyapunov analysis for hybrid dynamical systems. Hybrid Systems: Computation and Control (HSCC). Berlin, Germany: ACM Press, pp. 133\u2013142.","DOI":"10.1145\/2562059.2562139"},{"key":"2016090600134130000_33.3.723.33","doi-asserted-by":"crossref","unstructured":"Kvasnica M. Grieder P. Baotic M. Morari M. (2004) Multi-parametric toolbox (MPT). HSCC (Hybrid Systems: Computation and Control). Lecture Notes in Computer Science, vol. 2993, pp. 448\u2013462.","DOI":"10.1007\/978-3-540-24743-2_30"},{"key":"2016090600134130000_33.3.723.34","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"2016090600134130000_33.3.723.35","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0898-1221(96)00020-X","article-title":"Interval approximation of higher order to the ranges of functions","volume":"31","author":"Lin","year":"1996","journal-title":"Comput. Math. Appl."},{"key":"2016090600134130000_33.3.723.36","unstructured":"Majumdar A. Ahmadi A. A. Tedrake R. (2014) Control and verification of high-dimensional systems via DSOS and SDSOS optimization. IEEE Conference on Decision and Control (CDC), Los Angeles, December 2014."},{"key":"2016090600134130000_33.3.723.37","doi-asserted-by":"crossref","unstructured":"Meiss J. D. (2007) Differential Dynamical Systems. SIAM, Philadelphia.","DOI":"10.1137\/1.9780898718232"},{"key":"2016090600134130000_33.3.723.38","unstructured":"Monniaux D. Corbineau P. (2011) On the generation of Positivstellensatz witnesses in degenerate cases. ITP, Lecture Notes in Computer Science 6898. Berlin: Springer, pp. 249\u2013264."},{"key":"2016090600134130000_33.3.723.39","unstructured":"Motzkin T. (1967) The arithmetic-geometric inequality. Proceedings of a Symposium on Inequalities. Wright-Patterson Air Force Base, Ohio: Academic Press, pp. 205\u2013224."},{"key":"2016090600134130000_33.3.723.40","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-012-9256-3"},{"key":"2016090600134130000_33.3.723.41","unstructured":"Papachristodoulou A. Anderson J. Valmorbida G. Prajna S. Seiler P. Parrilo P. A. (2013) SOSTOOLS: Sum of squares optimization toolbox for MATLAB Version 3.00."},{"key":"2016090600134130000_33.3.723.42","doi-asserted-by":"crossref","unstructured":"Papachristodoulou A. Prajna S. (2002) On the construction of Lyapunov functions using the sum of squares decomposition. IEEE CDC. Las Vegas, Nevada: IEEE Press, 2002, pp. 3482\u20133487.","DOI":"10.1109\/CDC.2002.1184414"},{"key":"2016090600134130000_33.3.723.43","doi-asserted-by":"crossref","unstructured":"Papachristodoulou A. Prajna S. (2005) Analysis of non-polynomial systems using the sum of squares decomposition. Positive Polynomials in Control ( Henrion D. Garulli A. , eds), Lecture Notes in Control and Information Science 312. Berlin, Heidelberg: Springer, pp. 23\u201343.","DOI":"10.1007\/10997703_2"},{"key":"2016090600134130000_33.3.723.44","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0387-5"},{"key":"2016090600134130000_33.3.723.45","unstructured":"Platzer A. Quesel J.-D. R\u00fcmmer P. (2009) Real world verification. Proceedings of International Conference on Automated Deduction. Berlin: Springer, pp. 485\u2013501."},{"key":"2016090600134130000_33.3.723.46","doi-asserted-by":"crossref","unstructured":"Podelski A. Rybalchenko A. (2004) A Complete Method for the Synthesis of Linear Ranking Functions, Lecture Notes in Computer Science 2937. Berlin: Springer. pp. 239\u2013251.","DOI":"10.1007\/978-3-540-24622-0_20"},{"key":"2016090600134130000_33.3.723.47","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-00-02595-2"},{"key":"2016090600134130000_33.3.723.48","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1993.42.42045"},{"key":"2016090600134130000_33.3.723.49","doi-asserted-by":"publisher","DOI":"10.1137\/090749955"},{"key":"2016090600134130000_33.3.723.50","doi-asserted-by":"crossref","unstructured":"Sankaranarayanan S. Chen X. \u00c1braham E. (2013) Lyapunov function synthesis using Handelman representations. IFAC Conference on Nonlinear Control Systems (NOLCOS), pp. 576\u2013581.","DOI":"10.3182\/20130904-3-FR-2041.00198"},{"key":"2016090600134130000_33.3.723.51","unstructured":"Sassi M. A. B. Sankaranarayanan S. Chen X. Abraham E. (2014) Linear relaxations of polynomial positivity for polynomial Lyapunov function synthesis. arXiv, vol. arXiv:1407. 2952 [math.DS]."},{"key":"2016090600134130000_33.3.723.52","doi-asserted-by":"crossref","unstructured":"Sassi M. B. Testylier R. Dang T. Girard A. (2012) Reachability analysis of polynomial systems using linear programming relaxations. Automated Technology for Verification and Analysis, Thiruvananthapuram, India, pp. 137\u2013151.","DOI":"10.1007\/978-3-642-33386-6_12"},{"key":"2016090600134130000_33.3.723.53","doi-asserted-by":"publisher","DOI":"10.1007\/BF01446568"},{"key":"2016090600134130000_33.3.723.54","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.06.003"},{"key":"2016090600134130000_33.3.723.55","doi-asserted-by":"publisher","DOI":"10.1016\/j.nahs.2009.04.010"},{"key":"2016090600134130000_33.3.723.56","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF00121304","article-title":"A global optimization algorithm for polynomial programming using a reformulation linearization technique","volume":"2","author":"Sherali","year":"1991","journal-title":"J. Global Optim."},{"key":"2016090600134130000_33.3.723.57","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00013-8"},{"key":"2016090600134130000_33.3.723.58","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1007\/BF01070233","article-title":"Class of global minimum bounds on polynomial functions","volume":"23","author":"Shor","year":"1987","journal-title":"Cybernetics"},{"key":"2016090600134130000_33.3.723.59","doi-asserted-by":"crossref","unstructured":"Tabuada P. (2009) Verification and Control of Hybrid Systems: A Symbolic Approach. Berlin: Springer.","DOI":"10.1007\/978-1-4419-0224-5"},{"key":"2016090600134130000_33.3.723.60","unstructured":"Tan W. Packard A. (2007) Stability region analysis using sum of squares programming. Proceedings of the 2006 American Control Conference Minneapolis, Minnesota, USA,14\u201316 June 2006."},{"key":"2016090600134130000_33.3.723.61","doi-asserted-by":"crossref","unstructured":"Tarski A. (1951) A decision method for elementary algebra and geometry. Tech. rep., Univ. of California Press, Berkeley.","DOI":"10.1525\/9780520348097"},{"key":"2016090600134130000_33.3.723.62","first-page":"3860","article-title":"Estimation of the domain of attraction for polynomial systems via LMIs","volume-title":"IEEE CDC","volume":"4","author":"Tibken","year":"2000"},{"key":"2016090600134130000_33.3.723.63","doi-asserted-by":"crossref","unstructured":"Topcu U. Packard A. Seiler P. Wheeler T. (2007) Stability region analysis using simulations and sum-of-squares programming. Proceeding of the ACC. New York: IEEE Press, pp. 6009\u20136014.","DOI":"10.1109\/ACC.2007.4283013"},{"key":"2016090600134130000_33.3.723.64","doi-asserted-by":"publisher","DOI":"10.1016\/0005-1098(85)90099-8"}],"container-title":["IMA Journal of Mathematical Control and Information"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/imamci\/article-pdf\/33\/3\/723\/6766905\/dnv003.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,30]],"date-time":"2022-04-30T01:48:17Z","timestamp":1651283297000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/imamci\/article-lookup\/doi\/10.1093\/imamci\/dnv003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,17]]},"references-count":64,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2016,9,5]]},"published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1093\/imamci\/dnv003"],"URL":"https:\/\/doi.org\/10.1093\/imamci\/dnv003","relation":{},"ISSN":["0265-0754","1471-6887"],"issn-type":[{"value":"0265-0754","type":"print"},{"value":"1471-6887","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,17]]}}}