SONC optimization and exact nonnegativity certificates via second-order cone programming
From MaRDI portal
Publication:2674014
Abstract: The second-order cone (SOC) is a class of simple convex cones and optimizing over them can be done more efficiently than with semidefinite programming. It is interesting both in theory and in practice to investigate which convex cones admit a representation using SOCs, given that they have a strong expressive ability. In this paper, we prove constructively that the cone of sums of nonnegative circuits (SONC) admits a SOC representation. Based on this, we give a new algorithm for unconstrained polynomial optimization via SOC programming. We also provide a hybrid numeric-symbolic scheme which combines the numerical procedure with a rounding-projection algorithm to obtain exact nonnegativity certificates. Numerical experiments demonstrate the efficiency of our algorithm for polynomials with fairly large degree and number of variables.
Recommendations
- A Positivstellensatz for sums of nonnegative circuit polynomials
- Exact optimization via sums of nonnegative circuits and arithmetic-geometric-mean-exponentials
- Nonnegative Polynomials and Circuit Polynomials
- The \(\mathcal{S}\)-cone and a primal-dual view on second-order representability
- The dual cone of sums of non-negative circuit polynomials
Cites work
- scientific article; zbMATH DE number 52177 (Why is no real title available?)
- scientific article; zbMATH DE number 1489799 (Why is no real title available?)
- 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
- Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials
- Amoebas, nonnegative polynomials and sums of squares supported on circuits
- An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
- Certified roundoff error bounds using semidefinite programming
- Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
- Computing sum of squares decompositions with rational coefficients
- DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization
- Exact optimization via sums of nonnegative circuits and arithmetic-geometric-mean-exponentials
- Exploiting term sparsity in noncommutative polynomial optimization
- Forms derived from the arithmetic-geometric inequality
- Global optimization via the dual SONC cone and linear programming
- Initial steps in the classification of maximal mediated sets
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Lieb's concavity theorem, matrix geometric means, and semidefinite optimization
- Lower bounds for polynomials with simplex Newton polytopes based on geometric programming
- Newton polytopes and relative entropy optimization
- On exact Polya and Putinar's representations
- On exact Reznick, Hilbert-Artin and Putinar's representations
- On representing the positive semidefinite cone using the second-order cone
- On the semidefinite representation of real functions applied to symmetric matrices
- Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
- Relative entropy relaxations for signomial optimization
- Second-order cone programming
- Signomial and polynomial optimization via relative entropy and partial dualization
- Sparse noncommutative polynomial optimization
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
- {\textsc{RealCertify}}: a Maple package for certifying non-negativity
Cited in
(12)- Sum of squares generalizations for conic sets
- Dual certificates and efficient rational sum-of-squares decompositions for polynomial optimization over compact sets
- On minimal extended representations of generalized power cones
- A Positivstellensatz for sums of nonnegative circuit polynomials
- Weighted geometric mean, minimum mediated set, and optimal simple second-order cone representation
- Symmetric SAGE and SONC forms, exactness and quantitative gaps
- Exact optimization via sums of nonnegative circuits and arithmetic-geometric-mean-exponentials
- Pourchet’s theorem in action: decomposing univariate nonnegative polynomials as sums of five squares
- On representing the positive semidefinite cone using the second-order cone
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- Real zeros of SONC polynomials
This page was built for publication: SONC optimization and exact nonnegativity certificates via second-order cone programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2674014)
