Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
From MaRDI portal
Publication:2156369
circuit polynomialsconvex optimizationdualitynonnegativity certificatespolynomial optimizationpower cone
Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Real algebraic sets (14P05) Computational real algebraic geometry (14Q30) Numerical methods involving duality (49M29) Semidefinite programming (90C22) Polynomial optimization (90C23) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)
Abstract: Circuit polynomials are polynomials satisfying a number of conditions that make it easy to compute sharp and certifiable global lower bounds for them. Consequently, one may use them to find certifiable lower bounds for any polynomial by writing it as a sum of circuit polynomials with known lower bounds (if possible), in a fashion similar to the better-known sum-of-squares polynomials. Seidler and de Wolff recently showed that sums of nonnegative circuit (SONC) polynomials can be used to compute global lower bounds (called SONC bounds) for polynomials in this manner in polynomial time, as long as the polynomial is bounded from below and its support satisfies a nondegeneracy assumption. The quality of the SONC bound depends on the circuits used in the computation, but finding the set of circuits that yield the best attainable SONC bound among the astronomical number of candidate circuits is a non-trivial task that has not been addressed so far. In this paper we propose an efficient method to compute the optimal SONC lower bound by iteratively identifying the optimal circuits to use in the SONC bounding process. The method is based on a new proof of a recent result by Wang which states that (under the same nondegeneracy assumption) every SONC polynomial decomposes into SONC polynomials on the same support. Our proof, based on convex programming duality, removes the nondegeneracy assumption and motivates an algorithm that generates an optimal set of circuits and computes the corresponding SONC bound in a manner that is particularly attractive for sparse polynomials. The method is implemented and tested on a large set of sparse polynomial optimization problems with up to 40 unknowns, of degree up to 60, and up to 3000 monomials in the support. The results indicate that the method is efficient in practice. [abstract truncated for arXiv character limits]
Recommendations
- A Positivstellensatz for sums of nonnegative circuit polynomials
- An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
- Nonnegative Polynomials and Circuit Polynomials
- Lower bounds for polynomials with simplex Newton polytopes based on geometric programming
- The dual cone of sums of non-negative circuit polynomials
Cites work
- A Cutting Surface Algorithm for Semi-Infinite Convex Programming with an Application to Moment Robust Optimization
- A Positivstellensatz for sums of nonnegative circuit polynomials
- A unified framework of SAGE and SONC polynomials and its duality theory
- Alfonso: Matlab Package for Nonsymmetric Conic Optimization
- Amoebas, nonnegative polynomials and sums of squares supported on circuits
- An approach to obtaining global extremums in polynomial mathematical programming problems
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars
- Exact optimization via sums of nonnegative circuits and arithmetic-geometric-mean-exponentials
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- Formal Proofs for Nonlinear Optimization
- Global optimization via the dual SONC cone and linear programming
- Global optimization with polynomials and the problem of moments
- GloptiPoly
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 3365044 (Why is no real title available?)
- Lower bounds for polynomials using geometric programming
- Newton polytopes and relative entropy optimization
- On exact Polya and Putinar's representations
- On the computational complexity of membership problems for the completely positive cone and its dual
- Relative entropy relaxations for signomial optimization
- Semidefinite Optimization and Convex Algebraic Geometry
- Sparsity in sums of squares of polynomials
- Sum-of-squares optimization without semidefinite programming
- The dual cone of sums of non-negative circuit polynomials
- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
- Verifying Nonlinear Real Formulas Via Sums of Squares
Cited in
(11)- An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
- scientific article; zbMATH DE number 7378399 (Why is no real title available?)
- Exact optimization via sums of nonnegative circuits and arithmetic-geometric-mean-exponentials
- A Positivstellensatz for sums of nonnegative circuit polynomials
- Rational dual certificates for weighted sums-of-squares polynomials with boundable bit size
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- Symmetric SAGE and SONC forms, exactness and quantitative gaps
- Relative entropy methods in constrained polynomial and signomial optimization
- Empirically exploring the space of monostationarity in dual phosphorylation
- Study of the cone of sums of squares plus sums of nonnegative circuit forms
- Dual certificates of primal cone membership
This page was built for publication: Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2156369)
