Sum-of-squares chordal decomposition of polynomial matrix inequalities

• 成果类型: Article
• 署名作者: Zheng, Yang; Fantuzzi, Giovanni
• 署名单位: University of California System; University of California San Diego; Imperial College London
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01728-w
• 发表日期: 2023
• 页码: 71-108
• 关键词: moment-sos hierarchy; positive polynomials; exploiting sparsity; sdp-relaxations; optimization; PROGRAMS; tssos; real

摘要

We prove decomposition theorems for sparse positive (semi)definite polynomialmatrices that can be viewed as sparsity-exploiting versions of the Hilbert-Artin, Reznick, Putinar, and Putinar-Vasilescu Positivstellensatze. First, we establish that a polynomial matrix P( x) with chordal sparsity is positive semidefinite for all x is an element of R-n if and only if there exists a sum-of-squares (SOS) polynomial sigma( x) such that s P is a sum of sparse SOS matrices. Second, we show that setting sigma(x) = (x(1)(2) + center dot center dot center dot + x(n)(2))(upsilon). for some integer. suffices if P is homogeneous and positive definite globally. Third, we prove that if P is positive definite on a compact semialgebraic set K = {x : g(1)(x) >= 0,..., g(m)(x) >= 0} satisfying the Archimedean condition, then P( x) = S-0(x) + g(1)( x)S-1(x)+ center dot center dot center dot + g(m)(x)S-m( x) for matrices Si ( x) that are sums of sparse SOS matrices. Finally, if K is not compact or does not satisfy the Archimedean condition, we obtain a similar decomposition for (x(1)(2) + center dot center dot center dot + x(n)(2)). P(x) with some integer nu >= 0 when P and g1,..., gm are homogeneous of even degree. Using these results, we find sparse SOS representation theorems for polynomials that are quadratic and correlatively sparse in a subset of variables, and we construct new convergent hierarchies of sparsity-exploiting SOS reformulations for convex optimization problems with large and sparse polynomial matrix inequalities. Numerical examples demonstrate that these hierarchies can have a significantly lower computational complexity than traditional ones.