论文标题
多项式基质不等式的弦弦分解总和
Sum-of-squares chordal decomposition of polynomial matrix inequalities
论文作者
论文摘要
我们证明了分解定理的稀疏正（半）确定的多项式矩阵，可以看作是希尔伯特 - 阿特（Artin），reznick，putinar和putinar-putinar-vasilescupotitivstellensä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 $σ(x)$ such that $σP$ is a sum of sparse SOS matrices.其次，我们表明设置$σ（x）=（x_1^2 + \ cdots + x_n^2）^ν$对于某些整数$ν$，如果$ p $是同质且在全球范围内确定的，则足够。第三，我们证明，如果$ p $在紧凑的半格式集合$ \ mathcal {k} = \ {x：g_1（x）\ geq 0，\ ldots，g_m（x）\ geq 0 \} $满足acragimedean条件，然后满足$ p（x_1） + g_1 + g_1 + g_1（x）（x）（x x）（x）（x）（x）（x）（x）（x）（x）（x）（x）（x）（x）（x）（x） + + g_m（x）s_m（x）$用于矩阵$ s_i（x）$，是稀疏的SOS矩阵总和。最后，如果$ \ Mathcal {k} $不紧凑或不满足Archimedean条件，我们将获得$（x_1^2 + \ ldots + x_n^2）^n^2）^νp（x）$的类似分解，并带有一些integer $ν\ gq 0 $ p $ p $和$ g_1 $ g_1 $ g_1，form form，form for hous，forge nef for hous，forge at hous，forge at hous，forge at hous，forge at hous，forge at hous，dem g。使用这些结果，我们发现了变量子集中二次且相关性稀疏的多项式的稀疏SOS表示定理，并且我们构建了稀疏探索SOS的新收敛层次结构，以探索大量和稀疏的多项式矩阵不平等现象，以实现凸的优化问题。数值示例表明，这些层次结构的计算复杂性比传统的层次结构明显低。
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 $σ(x)$ such that $σP$ is a sum of sparse SOS matrices. Second, we show that setting $σ(x)=(x_1^2 + \cdots + x_n^2)^ν$ 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 $\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)^νP(x)$ with some integer $ν\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.
