Nonnegative Polynomials and Circuit Polynomials

DOI10.1137/20M1313969zbMATH Open1498.14145arXiv1804.09455MaRDI QIDQ5073707FDOQ5073707

Authors: Jie Wang 

Publication date: 3 May 2022

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Abstract: The concept of sums of nonnegative circuit polynomials (SONC) was recently introduced as a new certificate of nonnegativity especially for sparse polynomials. In this paper, we explore the relationship between nonnegative polynomials and SONC polynomials. As a first result, we provide sufficient conditions for nonnegative polynomials with general Newton polytopes to be SONC polynomials, which generalizes the previous result on nonnegative polynomials with simplex Newton polytopes. Secondly, we prove that every SONC polynomial admits a SONC decomposition without cancellation. In other words, SONC decompositions can exactly preserve the sparsity of nonnegative polynomials, which is dramatically different from the classical sum of squares (SOS) decompositions and is a key property to design efficient algorithms for sparse polynomial optimization based on SONC decompositions.

Full work available at URL: https://arxiv.org/abs/1804.09455

Recommendations

• A Positivstellensatz for sums of nonnegative circuit polynomials
• The dual cone of sums of non-negative circuit polynomials
• Polynomials with Nonnegative Coefficients
• scientific article; zbMATH DE number 1151814
• Non-negativity properties of \(R\)-polynomials
• Nonnegative polynomials and their Carathéodory number
• Maximally positive polynomial systems supported on circuits
• Nonnegative polynomials and sums of squares
• Nonnegative polynomials and sums of squares
• On coefficients of circuit polynomials and characteristic polynomials

zbMATH Keywords

sum of squaresnonnegative polynomialsum of nonnegative circuit polynomialscertificate of nonnegativitySONC

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Semialgebraic sets and related spaces (14P10) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Polynomial optimization (90C23)

Cites Work

• Convex Analysis
• Symmetry groups, semidefinite programs, and sums of squares
• Title not available (Why is that?)
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Forms derived from the arithmetic-geometric inequality
• Amoebas, nonnegative polynomials and sums of squares supported on circuits
• Lower bounds for polynomials with simplex Newton polytopes based on geometric programming
• DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
• Newton polytopes and relative entropy optimization
• Extremal psd forms with few terms
• Global injectivity and multiple equilibria in uni- and bi-molecular reaction networks
• A unified framework of SAGE and SONC polynomials and its duality theory
• Signomial and polynomial optimization via relative entropy and partial dualization
• An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
• A note on mediated simplices
• TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
• Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
• A second order cone characterization for sums of nonnegative circuits
• A new sparse SOS decomposition algorithm based on term sparsity
• Systems of polynomials with at least one positive real zero

Cited In (16)

• Certifying polynomials for AC^0(parity) circuits, with applications
• Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
• A Positivstellensatz for sums of nonnegative circuit polynomials
• The algebraic boundary of the sonc-cone
• Real zeros of SONC polynomials
• Amoebas, nonnegative polynomials and sums of squares supported on circuits
• Characterization of circuits supporting polynomial systems with the maximal number of positive solutions
• Symmetric SAGE and SONC forms, exactness and quantitative gaps
• The dual cone of sums of non-negative circuit polynomials
• Parameter Region for Multistationarity in \({\boldsymbol{n-}}\)Site Phosphorylation Networks
• On minimal extended representations of generalized power cones
• Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
• SONC optimization and exact nonnegativity certificates via second-order cone programming
• Sublinear circuits and the constrained signomial nonnegativity problem
• A unified framework of SAGE and SONC polynomials and its duality theory
• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials

Uses Software

• SPOTless
• TSSOS

This page was built for publication: Nonnegative Polynomials and Circuit Polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5073707)