Exploiting Term Sparsity in Moment-SOS Hierarchy for Dynamical Systems

• 成果类型: Article
• 署名作者: Wang, Jie; Schlosser, Corbinian; Korda, Milan; Magron, Victor
• 署名单位: Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3293014
• 发表日期: 2023
• 页码: 8232-8237
• 关键词: Convex relaxation; dynamical system; global attractor (GA); maximum positively invariant (MPI) set; moment-sum-of-squares (moment-SOS) hierarchy; Region of attraction (ROA); semidefinite programming (SDP); term sparsity

摘要

In this article, we develop a dynamical system counterpart to the term sparsity sum-of-squares algorithm proposed for static polynomial optimization. This allows for computational savings and improved scalability while preserving convergence guarantees when sum-of-squares methods are applied to problems from dynamical systems, including the problems of approximating region of attraction, the maximum positively invariant set, and the global attractor. At its core, the method exploits the algebraic structure of the data, thereby complementing existing methods that exploit causality relations among the states of the dynamical system. The procedure encompasses sign symmetries of the dynamical system as was already revealed for polynomial optimization. Numerical examples demonstrate the efficiency of the approach in the presence of this type of sparsity.