The dual cone of sums of non-negative circuit polynomials (Q2035029): Difference between revisions

The natural duality pairing between real polynomials \(f=\sum_{\alpha\in \mathcal{A}} c_\alpha x^\alpha \in \mathbb{R}[x_1,\dots,x_n]\) supported on a finite set \(\mathcal{A}\subseteq \mathbb{N}_0^n\) and vectors \(\nu \in \mathbb{R}^{\mathcal A}\) is given by \(\nu(f)=\sum_{\alpha\in \mathcal{A}} c_\alpha \nu_{\alpha}.\) A circuit polynomial in \(\mathbb{R}[x_1,\dots, x_n] \) is an expression of the form \(\sum_{j=1}^k c_j x^{\alpha(j)} + \delta x^{\beta},\) with \(c_j\) positive and \(\beta\) lying in the relative interior of a set \(\{\alpha(j)\}_{j=1}^k\) of lattice points which are supposed to be affinely independent and even. The circuit polynomials which are nonnegative and supported on \(\mathcal{A}\) generate a cone \(C_{\mathrm{sonc}}(\mathcal A),\) where SONC is acronym for `sum of nonnegative circuit polynomials' . The main purpose of the paper is the determination of the dual \((C_{\mathrm{sonc}}(\mathcal A))^*= \{\nu\in \mathbb{R}^{\mathcal{A}}: \nu(f)\geq 0 \text{ for all } f\in C_{\mathrm{sonc}}(\mathcal A) \}\) of that cone. To achieve this goal the authors find a necessary and sufficient criterion for the nonnegativity of a circuit polynomial in terms of the relative entropy function \(D(\nu, \zeta)=\sum_{i=1}^k \nu_j \log\frac{\nu_j}{\zeta_j}.\) This gives an alternative to the known criterion in terms of the circuit number found by \textit{S. Iliman} and \textit{T. de Wolff} [SIAM J. Optim. 26, No. 2, 1128--1146 (2016; Zbl 1380.12001)]. The relative entropy function was used by \textit{V. Chandrasekaran} and \textit{P. Shah} [SIAM J. Optim. 26, No. 2, 1147--1173 (2016; Zbl 1345.90066)] to study the SAGE-cone (i.e. sum of arithmetic geometric exponentials) and its dual. A useful comparison between SAGEs and SONCs is in [\textit{M. Dressler} et al., SIAM J. Appl. Algebra Geom. 1, No. 1, 536--555 (2017; Zbl 1372.14051)] and additional understanding is provided by the present paper. Theorem 3.1 describes \((C_{\mathrm{sonc}}(\mathcal A))^* \) as the set of all \((\nu_\alpha)_{\alpha\in \mathcal A}\) for which \( \nu_\alpha\geq 0 \text{ for } \alpha \in \mathcal A \cap (2\mathbb{N}_0)^n\) and for which furthermore for all \(k\geq 2\) and \((\alpha(1),\dots, \alpha(k),\beta) \) with properties like those alluded to above there exist \(\nu^* \geq |\nu_\beta|\) and \(\tau \in \mathbb{R}^n\) so that \(\nu^* \log \frac{\nu^*}{\nu_{\alpha(j)} }\leq (\beta-\alpha(j))^{\mathsf T} \tau \) for \(1\leq j\leq k.\) This description is similar although more complicated than Chandrasekaran and Shah's description of \((C_{\mathrm{sage}}(\mathcal A))^*. \) The proof is a preceded by the description of the dual of the cone \(C_{nc}(\alpha(1),\dots,\alpha(k),\beta)\) of nonnegative circuit polynomials of support contained in \((\alpha(1),\dots, \alpha(k),\beta)\) and uses elementary convexity theory. As one application of the main theorem, the dual of the SONC cone of univariate quartics is described via polynomial inequalities and the situation illuminated with duality theory of plane algebraic curves. As another application, in Section 4 it is shown that if \(\nu \in \mathbb{R}^\mathcal{A}\) is an optimal solution for the program \(p^*_{\mathrm{sonc}}= \inf_{\nu\in \mathbb{R}^\mathcal A}\{ c^{\mathsf T} \nu \text{ so that } \nu\in (C_{\mathrm{sonc}}(\mathcal A))^* \}\) (which is dual to the SONC-cone relaxation for the problem \(\inf_{x\in \mathbb{R}^n } p(x)\)) and if there exists a \(z\in \mathbb{R}^n\) so that \(\nu=(z^\alpha)_{\alpha\in \mathbb{A}},\) then \(p^*_{\mathrm{sonc}}=\inf_{x\in \mathbb{R}^n } p(x).\)