Sum-of-squares chordal decomposition of polynomial matrix inequalities

Abstract

We prove decomposition theorems for sparse positive (semi)definite polynomial matrices that can be viewed as sparsity-exploiting versions of the Hilbert--Artin, Reznick, Putinar, and Putinar--Vasilescu Positivstellensätze. First, we establish that a polynomial matrix $P(x)$ with chordal sparsity is positive semidefinite for all $x\in {\mathbb{R}}^n$ if and only if there exists a sum-of-squares (SOS) polynomial $\sigma (x)$ such that $\sigma P$ is a sum of sparse SOS matrices. Second, we show that setting $\sigma (x)=(x_1^2+\cdots +x_n^2{)}^{\nu }$ for some integer $\nu$ suffices if $P$ is homogeneous and positive definite globally. Third, we prove that if $P$ is positive definite on a compact semialgebraic set $\mathcal{K}=\{x:g_1(x)\ge 0,\dots ,g_m(x)\ge 0\}$ satisfying the Archimedean condition, then $P(x)=S_0(x)+g_1(x)S_1(x)+\cdots +g_m(x)S_m(x)$ for matrices $S_i(x)$ that are sums of sparse SOS matrices. Finally, if $\mathcal{K}$ is not compact or does not satisfy the Archimedean condition, we obtain a similar decomposition for $(x_1^2+\dots +x_n^2{)}^{\nu }P(x)$ with some integer $\nu \ge 0$ when $P$ and $g_1,\dots ,g_m$ 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.

32 pages, 7 figures, 4 tables. Established sparsity-exploiting versions of Reznick and Putinar--Vasilescu Positivstellensätze, and updated the second numerical example. Code for our numerical experiments is available here: https://github.com/aeroimperial-optimization/sos-chordal-decomposition-pmi

References in corpus (5)

• Symmetry groups, semidefinite programs, and sums of squares
• Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
• Sparse Noncommutative Polynomial Optimization
• Decomposed Structured Subsets for Semidefinite and Sum-of-Squares Optimization
• A sparse version of Reznick's Positivstellensatz

Cited by in corpus (4)

• Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization
• Finite convergence of the Moment-SOS hierarchy for polynomial matrix optimization
• Matrix Completion and Decomposition in Phase Bounded Cones
• A Moment-SOS Hierarchy for Robust Polynomial Matrix Inequality Optimization with SOS-Convexity