Sum-of-squares chordal decomposition of polynomial matrix inequalities
File(s)2007.11410v2.pdf (1.17 MB)
Working Paper
Author(s)
Zheng, Yang
Fantuzzi, Giovanni
Type
Working Paper
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)\geq 0,\ldots,g_m(x)\geq 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 + \cdots + x_n^2)^\nu P(x)$ with some integer $\nu\geq 0$ when $P$ and $g_1,\ldots,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.
Date Issued
2021-10-25
Date Acceptance
2021-10-24
Citation
Mathematical Programming, 2021
ISSN
0025-5610
Publisher
Springer
Journal / Book Title
Mathematical Programming
Copyright Statement
©2021 The Author(s)
Identifier
http://arxiv.org/abs/2007.11410v2
Subjects
math.OC
math.OC
cs.DS
cs.SY
eess.SY
math.AG
Notes
32 pages, 7 figures, 4 tables. Established sparsity-exploiting versions of Reznick and Putinar--Vasilescu Positivstellens\"atze, and updated the second numerical example. Code for our numerical experiments is available here: https://github.com/aeroimperial-optimization/sos-chordal-decomposition-pmi
Publication Status
Published
Date Publish Online
2021-11-20