We prove three decomposition results for sparse positive ( semi- )definite polynomial matrices  . First, we show that a polynomial matrix P(x) with chordal sparsity is positive semidefinite for all x\in R^n if and only if there exists a sum-of-squares (SOS) polynomial \sigma(x) such that \sigma (x)P (x) can be decomposed into a sum of sparse SOS matrices , each of which is zero outside a small principal submatrix . Second, we establish that setting \sigma(x)=(x_1^2 + \cdots + x_n^2)^\nu for some integer \nu suffices if P (x) is even, homogeneous , and positive definite  . Third, we prove a sparse-matrix version of Putinar's Positivstellensatz: if P (x) has chordal sparsity and 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 , each of which is zero outside a small principal submatrix is not compact or does not satisfy the Archimedean condition, we obtain a similar decomposition for (x_1^2 + \ldots + 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 decomposition results, we obtain sparse SOS representation theorems for polynomials that are quadratic and correlatively sparse in a subset of variables . We also obtain new convergent hierarchies of sparsity-exploiting SOS reformulations to convex optimization problems with large and sparse polynomial matrix inequalities. Analytical examples illustrate all our decomposition results, while large-scale numerical examples demonstrate that the corresponding sparsity-exploiting SOS hierarchies have significantly lower computational complexity than traditional ones.
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\"atze . First, we establish that a polynomial matrix P(x) with chordal sparsity is positive semidefinite for all x\in 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 + \ldots + 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.
R
three decomposition results
decomposition theorems
R
semi-
semi
A
that can be viewed as sparsity-exploiting versions of the Hilbert--Artin, Reznick, Putinar, and Putinar--Vasilescu Positivstellens\"atze
R
show
establish
R
(x)P (x) can be decomposed into
P is
D
, each of which is zero outside a small principal submatrix
R
establish
show
R
(x) is even, homogeneous ,
is homogeneous
A
globally
R
a sparse-matrix version of Putinar's Positivstellensatz: if P (x) has chordal sparsity and
that if P
R
, each of which is zero outside a small principal submatrix
. Finally, if \mathcal{K
D
decomposition
R
obtain
find
R
. We also obtain
, and we construct
R
to
for
R
Analytical examples illustrate all our decomposition results, while large-scale numerical examples demonstrate that the corresponding sparsity-exploiting SOS hierarchies have
Numerical examples demonstrate that these hierarchies can have a