分块平方和分解

本文定义了分块平方和可分解多项式的概念.粗略地说,它是这样一类多项式,只考虑其支撑集(不考虑系数)就可以把它的平方和分解问题等价地转换为较小规模的同类问题(换句话说,相应的半正定规划问题的矩阵可以分块对角化).本文证明了近年文献中提出的两类方法—分离多项式(split polynomial)和最小坐标投影(minimal coordinate projection)—都可以用分块平方和可分解多项式来描述,证明了分块平方和可分解多项式集在平方和多项式集中为零测集.

Block SOS decomposition

In this paper,we define a concept of block SOS(sum of squares)decomposable polynomials which is a generalization of some special classes of polynomials in the literature.Roughly speaking,it is a class of polynomials whose SOS decomposition problem can be transformed equivalently into smaller ones(in other words,the corresponding semi-definite programming matrices can be block-diagonalized)by considering their supports only(coefficients are not considered).Then we prove that two recently proposed methods in the literature,the split polynomial and the minimal coordinate projection,can be described using the concept of block SOS decomposable polynomial.Also,we prove that the set of block SOS decomposable polynomials has measure zero in the set of SOS polynomials.