The concept of sums of nonnegative circuit (SONC) polynomials was recently introduced as a new certificate of nonnegativity especially for sparse polynomials. In this paper, we explore the relationship between nonnegative polynomials and SONCs. As a first result, we provide sufficient conditions for nonnegative polynomials with general Newton polytopes to be a SONC, which generalizes the previous result on nonnegative polynomials with simplex Newton polytopes. Second, we prove that every SONC admits a SONC decomposition without cancellation. In other words, SONC decompositions preserve sparsity of nonnegative polynomials, which is dramatically different from the classical sum of squares decompositions and is a key property to design efficient algorithms for sparse polynomial optimization based on SONC decompositions.
Publication:
SIAM Journal on Applied Algebra and Geometry, Vol. 6, Iss. 2, pp: 111–133.
Author:
Jie Wang
Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
Email: wangjie212@amss.ac.cn
