A unified framework of SAGE and SONC polynomials and its duality theory

Authors:
Lukas Katthän, Helen Naumann and Thorsten Theobald

Journal:
Math. Comp. **90** (2021), 1297-1322

MSC (2020):
Primary 14P05, 90C30; Secondary 52A20, 12D15

DOI:
https://doi.org/10.1090/mcom/3607

Published electronically:
January 28, 2021

MathSciNet review:
4232225

Full-text PDF

View in AMS MathViewer

Abstract | References | Similar Articles | Additional Information

We introduce and study a cone which consists of a class of generalized polynomial functions and which provides a common framework for recent non-negativity certificates of polynomials in sparse settings. Specifically, this $\mathcal {S}$-cone generalizes and unifies sums of arithmetic-geometric mean exponentials (SAGE) and sums of non-negative circuit polynomials (SONC). We provide a comprehensive characterization of the dual cone of the $\mathcal {S}$-cone, which even for its specializations provides novel and projection-free descriptions. As applications of this result, we give an exact characterization of the extreme rays of the $\mathcal {S}$-cone and thus also of its specializations, and we provide a subclass of functions for which non-negativity coincides with membership in the $\mathcal {S}$-cone.

Moreover, we derive from the duality theory an approximation result of non-negative univariate polynomials and show that a SONC analogue of Putinar’s Positivstellensatz does not exist even in the univariate case.

- Amir Ali Ahmadi and Anirudha Majumdar,
*Some applications of polynomial optimization in operations research and real-time decision making*, Optim. Lett.**10**(2016), no. 4, 709–729. MR**3477372**, DOI 10.1007/s11590-015-0894-3 - Amir Ali Ahmadi and Anirudha Majumdar,
*DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization*, SIAM J. Appl. Algebra Geom.**3**(2019), no. 2, 193–230. MR**3939321**, DOI 10.1137/18M118935X - Gennadiy Averkov,
*Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization*, SIAM J. Appl. Algebra Geom.**3**(2019), no. 1, 128–151. MR**3922906**, DOI 10.1137/18M1201342 - Venkat Chandrasekaran and Parikshit Shah,
*Relative entropy relaxations for signomial optimization*, SIAM J. Optim.**26**(2016), no. 2, 1147–1173. MR**3499559**, DOI 10.1137/140988978 - Venkat Chandrasekaran and Parikshit Shah,
*Relative entropy optimization and its applications*, Math. Program.**161**(2017), no. 1-2, Ser. A, 1–32. MR**3592772**, DOI 10.1007/s10107-016-0998-2 - M. Dressler, J. Heuer, H. Naumann, and T. de Wolff,
*Global optimization via the dual SONC cone and linear programming*, Proc. 45th International Symposium on Symbolic and Algebraic Computation, 2020, pp. 138–145. - Mareike Dressler, Sadik Iliman, and Timo de Wolff,
*An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming*, J. Symbolic Comput.**91**(2019), 149–172. MR**3860889**, DOI 10.1016/j.jsc.2018.06.018 - Mareike Dressler, Adam Kurpisz, and Timo de Wolff,
*Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials*, 43rd International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 117, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, pp. Art. No. 82, 17. MR**3854037** - M. Dressler, H. Naumann, and T. Theobald,
*The dual cone of sums of non-negative circuit polynomials*, To appear in Adv. Geom. 2020. - G. Hall,
*Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming*, PhD thesis, Dept. of Operations Research and Financial Engineering, Princeton University, 2018. - G. H. Hardy, J. E. Littlewood, and G. Pólya,
*Inequalities*, Cambridge, at the University Press, 1952. 2d ed. MR**0046395** - D. Henrion and A. Garulli (eds.),
*Positive polynomials in control*, Lecture Notes in Control and Information Sciences, vol. 312, Springer-Verlag, Berlin, 2005. MR**2121436**, DOI 10.1007/b96977 - Sadik Iliman and Timo de Wolff,
*Amoebas, nonnegative polynomials and sums of squares supported on circuits*, Res. Math. Sci.**3**(2016), Paper No. 9, 35. MR**3481195**, DOI 10.1186/s40687-016-0052-2 - C. Josz,
*Application of Polynomial Optimization to Electricity Transmission Networks*, PhD thesis, University Paris VI, 2016. - O. Karaca, G. Darivianakis, P. Beuchat, A. Georghiou, and J. Lygeros,
*The REPOP toolbox: tackling polynomial optimization using relative entropy relaxations*, 20th IFAC World Congress, IFAC PapersOnLine, vol. 50(1), Elsevier, 2017, pp. 11652–11657. - Masakazu Kojima, Sunyoung Kim, and Hayato Waki,
*Sparsity in sums of squares of polynomials*, Math. Program.**103**(2005), no. 1, Ser. A, 45–62. MR**2166534**, DOI 10.1007/s10107-004-0554-3 - Jean Bernard Lasserre,
*Moments, positive polynomials and their applications*, Imperial College Press Optimization Series, vol. 1, Imperial College Press, London, 2010. MR**2589247** - Jean B. Lasserre and Tim Netzer,
*SOS approximations of nonnegative polynomials via simple high degree perturbations*, Math. Z.**256**(2007), no. 1, 99–112. MR**2282261**, DOI 10.1007/s00209-006-0061-8 - Jean B. Lasserre,
*A sum of squares approximation of nonnegative polynomials*, SIAM Rev.**49**(2007), no. 4, 651–669. MR**2375528**, DOI 10.1137/070693709 - Victor Magron, George Constantinides, and Alastair Donaldson,
*Certified roundoff error bounds using semidefinite programming*, ACM Trans. Math. Software**43**(2017), no. 4, Art. 34, 31. MR**3638571**, DOI 10.1145/3015465 - R. Murray, V. Chandrasekaran, and A. Wierman,
*Newton polytopes and relative entropy optimization*, Preprint, arXiv:1810.01614, 2018. - Jiawang Nie,
*The $\scr {A}$-truncated $K$-moment problem*, Found. Comput. Math.**14**(2014), no. 6, 1243–1276. MR**3273678**, DOI 10.1007/s10208-014-9225-9 - Mihai Putinar,
*Positive polynomials on compact semi-algebraic sets*, Indiana Univ. Math. J.**42**(1993), no. 3, 969–984. MR**1254128**, DOI 10.1512/iumj.1993.42.42045 - Cordian Riener, Thorsten Theobald, Lina Jansson Andrén, and Jean B. Lasserre,
*Exploiting symmetries in SDP-relaxations for polynomial optimization*, Math. Oper. Res.**38**(2013), no. 1, 122–141. MR**3029481**, DOI 10.1287/moor.1120.0558 - Rolf Schneider,
*Convex bodies: the Brunn-Minkowski theory*, Second expanded edition, Encyclopedia of Mathematics and its Applications, vol. 151, Cambridge University Press, Cambridge, 2014. MR**3155183** - J. Wang,
*Nonnegative polynomials and circuit polynomials*, Preprint, arXiv:1804.09455, 2018. - J. Wang and V. Magron,
*A second order cone characterization for sums of nonnegative circuits*, Proc. 45th International Symposium on Symbolic and Algebraic Computation, 2020, pp. 450–457. - J. Wang, V. Magron, and J. B. Lasserre,
*TSSOS: a moment-SOS hierarchy that exploits term sparsity*, Preprint, arXiv:1912.08899, 2019. - J. Wang, V. Magron, and J. B. Lasserre,
*Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension*, Preprint, arXiv:2003.03210, 2020. - Tillmann Weisser, Jean B. Lasserre, and Kim-Chuan Toh,
*Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity*, Math. Program. Comput.**10**(2018), no. 1, 1–32. MR**3773087**, DOI 10.1007/s12532-017-0121-6 - Günter M. Ziegler,
*Lectures on polytopes*, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR**1311028**, DOI 10.1007/978-1-4613-8431-1

Retrieve articles in *Mathematics of Computation*
with MSC (2020):
14P05,
90C30,
52A20,
12D15

Retrieve articles in all journals with MSC (2020): 14P05, 90C30, 52A20, 12D15

Additional Information

**Lukas Katthän**

Affiliation:
Goethe-Universität, FB 12 – Institut für Mathematik, Postfach 11 19 32, D–60054 Frankfurt am Main, Germany

Email:
katthaen@math.uni-frankfurt.de

**Helen Naumann**

Affiliation:
Goethe-Universität, FB 12 – Institut für Mathematik, Postfach 11 19 32, D–60054 Frankfurt am Main, Germany

Email:
naumann@math.uni-frankfurt.de

**Thorsten Theobald**

Affiliation:
Goethe-Universität, FB 12 – Institut für Mathematik, Postfach 11 19 32, D–60054 Frankfurt am Main, Germany

MR Author ID:
618735

ORCID:
0000-0002-5769-0917

Email:
theobald@math.uni-frankfurt.de

Received by editor(s):
May 3, 2019

Received by editor(s) in revised form:
February 25, 2020, and September 19, 2020

Published electronically:
January 28, 2021

Article copyright:
© Copyright 2021
American Mathematical Society