Nonnegative Polynomials and Circuit Polynomials
From MaRDI portal
certificate of nonnegativitynonnegative polynomialSONCsum of nonnegative circuit polynomialssum of squares
Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Semialgebraic sets and related spaces (14P10) Polynomial optimization (90C23) Nonconvex programming, global optimization (90C26)
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
- 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
- scientific article; zbMATH DE number 3214278 (Why is no real title available?)
- 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
(22)- Real zeros of SONC polynomials
- The dual cone of sums of non-negative circuit polynomials
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
- Characterization of circuits supporting polynomial systems with the maximal number of positive solutions
- SONC optimization and exact nonnegativity certificates via second-order cone programming
- Amoebas, nonnegative polynomials and sums of squares supported on circuits
- Sublinear circuits and the constrained signomial nonnegativity problem
- Certifying polynomials for AC^0(parity) circuits, with applications
- The algebraic boundary of the sonc-cone
- A second order cone characterization for sums of nonnegative circuits
- A Positivstellensatz for sums of nonnegative circuit polynomials
- A unified framework of SAGE and SONC polynomials and its duality theory
- Parameter Region for Multistationarity in \({\boldsymbol{n-}}\)Site Phosphorylation Networks
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- Symmetric SAGE and SONC forms, exactness and quantitative gaps
- On minimal extended representations of generalized power cones
- The duality of SONC: advances in circuit-based certificates
- Relative entropy methods in constrained polynomial and signomial optimization
- Empirically exploring the space of monostationarity in dual phosphorylation
- Initial application of SONC to Lyapunov stability of dynamical systems
- Study of the cone of sums of squares plus sums of nonnegative circuit forms
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)
