SONC optimization and exact nonnegativity certificates via second-order cone programming
From MaRDI portal
Publication:2674014
DOI10.1016/J.JSC.2022.08.002zbMATH Open1500.90045arXiv2012.07903OpenAlexW3113334666WikidataQ114154427 ScholiaQ114154427MaRDI QIDQ2674014FDOQ2674014
Authors: Victor Magron, Jie Wang 
Publication date: 22 September 2022
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/2012.07903
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
polynomial optimizationsecond-order cone programmingsum of nonnegative circuit polynomialsexact nonnegativity certificaterounding-projection algorithmsum of binomial squares
Cites Work
- Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials
- {\textsc{RealCertify}}: a Maple package for certifying non-negativity
- Title not available (Why is that?)
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Second-order cone programming
- 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
- On the semidefinite representation of real functions applied to symmetric matrices
- Relative entropy relaxations for signomial optimization
- Lieb's concavity theorem, matrix geometric means, and semidefinite optimization
- Computing sum of squares decompositions with rational coefficients
- Title not available (Why is that?)
- A unified framework of SAGE and SONC polynomials and its duality theory
- Initial steps in the classification of maximal mediated sets
- Signomial and polynomial optimization via relative entropy and partial dualization
- Certified roundoff error bounds using semidefinite programming
- An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
- A note on mediated simplices
- Global optimization via the dual SONC cone and linear programming
- On representing the positive semidefinite cone using the second-order cone
- On Exact Polya and Putinar's Representations
- Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
- On exact Reznick, Hilbert-Artin and Putinar's representations
- Sparse noncommutative polynomial optimization
- Exploiting term sparsity in noncommutative polynomial optimization
- 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
- Exact Optimization via Sums of Nonnegative Circuits and Arithmetic-geometric-mean-exponentials
Cited In (9)
- Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
- A Positivstellensatz for sums of nonnegative circuit polynomials
- Symmetric SAGE and SONC forms, exactness and quantitative gaps
- On representing the positive semidefinite cone using the second-order cone
- On minimal extended representations of generalized power cones
- Pourchet’s theorem in action: decomposing univariate nonnegative polynomials as sums of five squares
- Dual Certificates and Efficient Rational Sum-of-Squares Decompositions for Polynomial Optimization over Compact Sets
- Sum of squares generalizations for conic sets
- Weighted geometric mean, minimum mediated set, and optimal simple second-order cone representation
Uses Software
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)
