Nonnegative Polynomials and Circuit Polynomials
From MaRDI portal
Publication:5073707
sum of squaresnonnegative polynomialsum of nonnegative circuit polynomialscertificate of nonnegativitySONC
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)
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.
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
Cites work
- scientific article; zbMATH DE number 3214278 (Why is no real title available?)
- A new sparse SOS decomposition algorithm based on term sparsity
- A note on mediated simplices
- A second order cone characterization for sums of nonnegative circuits
- A unified framework of SAGE and SONC polynomials and its duality theory
- Amoebas, nonnegative polynomials and sums of squares supported on circuits
- An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
- Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
- Convex Analysis
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Extremal psd forms with few terms
- Forms derived from the arithmetic-geometric inequality
- Global injectivity and multiple equilibria in uni- and bi-molecular reaction networks
- Lower bounds for polynomials with simplex Newton polytopes based on geometric programming
- Newton polytopes and relative entropy optimization
- Signomial and polynomial optimization via relative entropy and partial dualization
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Symmetry groups, semidefinite programs, and sums of squares
- Systems of polynomials with at least one positive real zero
- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
Cited in
(16)- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- A unified framework of SAGE and SONC polynomials and its duality theory
- Certifying polynomials for AC^0(parity) circuits, with applications
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- Amoebas, nonnegative polynomials and sums of squares supported on circuits
- A Positivstellensatz for sums of nonnegative circuit polynomials
- Real zeros of SONC polynomials
- The algebraic boundary of the sonc-cone
- Characterization of circuits supporting polynomial systems with the maximal number of positive solutions
- The dual cone of sums of non-negative circuit polynomials
- Symmetric SAGE and SONC forms, exactness and quantitative gaps
- Parameter Region for Multistationarity in \({\boldsymbol{n-}}\)Site Phosphorylation Networks
- Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
- On minimal extended representations of generalized power cones
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- Sublinear circuits and the constrained signomial nonnegativity problem
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)
