Samy Skander

Samy Skander Bahoura

A uniform result in dimension 2

Keywords:

Introduction and Main result

We set ∆ = -∇ i (∇ i ) the Laplace-Beltrami operator. We are on compact Riemannian surface (M, g) without boundary.

We start with the following example: for all ǫ > 0 the constant functions z ǫ = log ǫ a with a > 0, are solutions to ∆z ǫ +ǫ = ae zǫ and tend to -∞ uniformly on M .

Question: What's about the solutions u ǫ to the following equation

∆u ǫ + ǫ = V ǫ e uǫ , (E ǫ ) with 0 < a ≤ V ǫ (x) ≤ b < +∞ on M ?
Next, we assume V ǫ Hölderian and

V ǫ → V in L ∞
The equation (E ǫ ) is of prescribed scalar curvature type equation. The term ǫ replace the scalar curvature.

Theorem 1.1 . If ǫ → 0, the solutions u ǫ to (E ǫ ) satisfy: sup M u ǫ → -∞.
By using the same arguments of the next theorem, we have: * E-mails: samybahoura@yahoo.fr, samybahoura@gmail.com 1 Theorem 1.2 . If ǫ → 0, the solutions u ǫ to (E ǫ ) satisfy:

u ǫ -log ǫ → k ∈ R.
uniformly on M . Thus, we have a unifrom bound for the solutions:

k 1 + log ǫ ≤ u ǫ ≤ log ǫ + k 2 .
We also have another proof of the uniqueness result which appear in [START_REF] Bartolucci | Uniqueness and bifurcation for seminilinear elliptic equations on closed surfaces[END_REF]. This proof uses Brezis Merle arguments.

Theorem 1.3 . If ǫ → 0, the solutions u ǫ to (E ǫ ) with V ǫ ≡ 1, are such: u ǫ ≡ log ǫ.
2 Proof of the theorems 1,2,3.

Proof of theorem 1:

We have:

M V ǫ e uǫ → 0. ( * ) Let's consider x ǫ a point such that max M u ǫ = u ǫ (x ǫ ), then x ǫ → x 0 .
We consider a neighborhood of x 0 and we use isothermal coordinates around x 0 (see [START_REF] Chern | An elementary proof of the existence of isothermal parameters on a surface[END_REF]), there exists α > 0 and a regular function φ such that:

∆ E u ǫ + ǫe φ = V ǫ e φ e uǫ in B(0, α).
The metric g of M satisfies g = e φ (dx 2 + dy 2 ). Let's consider u 0 such that:

∆ E u 0 = e φ in B(0, α).
(with Dirichlet condition for example). The function v ǫ = u ǫ + ǫu 0 satisfies:

∆ E v ǫ = Ṽǫ e vǫ ,
with Ṽǫ = V ǫ e φ-ǫu0 . We use ( * ) to have:

B(0,α) e vǫ → 0 and 0 < ã ≤ Ṽǫ ≤ b. ( * * )
with α > 0.

The sequence v ǫ satisfies all the conditions of the theorem of Brezis and Merle, see [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF].

As v ǫ satisfy ( * * ), the last condtion of the theorem of [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF] is not possible. Now, suppose that the first assertion of the theorem of Brezis and Merle is true. We have the local boundedness result. We can say that u ǫ converge uniformly on M to a fonction u and in C 2 topology by the elliptic estimates.

If we tend ǫ to 0 we get that u satisfies in the sense of distributions:

∆u = V e u .
If we integrate the equation, we have a contradiction (since 0 < a ≤ V ≤ b < +∞.

Thus, u ǫ satisfies the second assertion of the theorem of [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF] and thus u ǫ diverge uniformly to -∞ on M .

Proof of Theoreme 2,3:

We set,

w ǫ = u ǫ -log ǫ.
Then, w ǫ is solution to:

∆w ǫ + ǫ = ǫV ǫ e wǫ .
We use Brezis and Merle's theorem and the previous arguments of theoerm 1, to have a convergence to a constant:

w ǫ → w ∞ = ct,
uniformly on M . In isothermal coordinates around x 0 = lim x ǫ with x ǫ such that, w ǫ (x ǫ ) = max M w ǫ , as in the previous case

∆ E w ǫ + ǫe φ = ǫe φ V ǫ e wǫ in B(0, α).
The metric g of M satisfies g = e φ (dx 2 + dy 2 ). Let's consider u 0 such that:

∆ E u 0 = e φ in B(0, α).
(with Dirichlet condition for example). The function v ǫ = w ǫ + ǫu 0 satisfies:

∆ E v ǫ = Ṽǫ e vǫ ,
with Ṽǫ = ǫV ǫ e φ-ǫu0 . One can apply the theorem of Brezis and Merle, see [START_REF] Brezis | Uniform estimates and blow-up bihavior for solutions of -∆u = V e u in two dimensions[END_REF].

w ǫ → w ∞ , in the C 2 topology with, ∆w ∞ = 0 ⇒ w ∞ ≡ k ∈ R.
For the third theorem we have:

M e wǫ = |M | ⇒ k = 0.
We write:

w ǫ = wǫ + f i ,
with the fact that, M f i = 0, and, f i is solution to: ∆f i = ǫ i (e wi+fi -1) = ǫ i (e wi (1 + f i + O(f 2 i )) -1), We multiply the equation by f i and we integrate, we obtain:

||∇f i || 2 L 2 = o(||f i || 2 L 2
). This is in contradiction with the Poincaré inequality if f i ≡ 0. Thus, f i ≡ 0, w i ≡ wi = 0.

  First we have, M V ǫ e wǫ = |M |, which imply, w ǫ → -∞, and, M ǫV ǫ e wǫ = ǫ|M | → 0, which imply the non-concentration. And,


SADIK ILIMAN Mareike Dressler
email: dressler@math.uni-frankfurt.de

Timo De Wolff
email: dewolff@math.tu-berlin.de

AN APPROACH TO CONSTRAINED POLYNOMIAL OPTIMIZATION VIA NONNEGATIVE CIRCUIT POLYNOMIALS AND GEOMETRIC PROGRAMMING

Keywords: 2010 Mathematics Subject Classification. 12D15, 14P99, 52B20, 90C25 Certificate, geometric programming, nonnegative polynomial, semidefinite programming, sum of nonnegative circuit polynomials, sum of squares, triangulation

In this article we combine two developments in polynomial optimization. On the one hand, we consider nonnegativity certificates based on sums of nonnegative circuit polynomials, which were recently introduced by the second and the third author. On the other hand, we investigate geometric programming methods for constrained polynomial optimization problems, which were recently developed by Ghasemi and Marshall. We show that the combination of both results yields a new method to solve certain classes of constrained polynomial optimization problems. We test the new method experimentally and compare it to semidefinite programming in various examples.

Introduction

Solving polynomial optimization problems is a key challenge in countless applications like dynamical systems, robotics, control theory, computer vision, signal processing, and economics; e.g. [START_REF] Blekherman | Semidefinite optimization and convex algebraic geometry[END_REF][START_REF]Moments, positive polynomials and their applications[END_REF]. It is well-known that polynomial optimization problems are NP-hard in general both in the constrained and in the unconstrained case [START_REF] Dickinson | On the computational complexity of membership problems for the completely positive cone and its dual[END_REF]. Starting with the seminal work of Lasserre in [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF], relaxation methods were developed which are significantly faster and provide lower bounds. These methods were studied intensively by means of aspects like exactness and quality of the relaxations [START_REF] De Klerk | Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube[END_REF][START_REF] Nie | Certifying convergence of Lasserre's hierarchy via flat truncation[END_REF][START_REF]An exact Jacobian SDP relaxation for polynomial optimization[END_REF][START_REF]Optimality conditions and finite convergence of Lasserre's hierarchy[END_REF], the speed of the computations [START_REF]Moments, positive polynomials and their applications[END_REF][START_REF] Parrilo | Minimizing polynomial functions, Algorithmic and quantitative real algebraic geometry[END_REF], and geometrical aspects of the underlying structures [START_REF] Blekherman | There are significantly more nonnegative polynomials than sums of squares[END_REF][START_REF]Nonnegative polynomials and sums of squares[END_REF]. A great majority of these results are based on the original approach by Lasserre, called Lasserre relaxation, which relies on semidefinite programming (SDP) methods and sums of squares (SOS) certificates to provide lower bounds for polynomial optimization problems. SDPs can be solved in polynomial time in problem size (up to an ε-error); e.g. [START_REF] Blekherman | Semidefinite optimization and convex algebraic geometry[END_REF]p. 41] and references therein. However, the size of such programs grows exponentially with the number of variables n or the degree d of the polynomials, as its size is given by the number of monomials of n-variate monomials of degree at most d.

Recently, Ghasemi and Marshall suggested a promising alternative approach both for constrained and unconstrained optimization problems based on geometric programming (GP) [START_REF] Ghasemi | Lower bounds for polynomials using geometric programming[END_REF][START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF]. GPs can also be solved in polynomial time (up to an ε-error) [START_REF] Nesterov | Interior point polynomial algorithms in convex programming[END_REF]; see also [START_REF] Boyd | A tutorial on geometric programming[END_REF]Page 118], but, by experimental results, e.g. [BKVH07, GM12, GM13, GLM14], in practice the corresponding geometric programs can be solved significantly faster than their counterparts in semidefinite programming. The lower bounds obtained by Ghasemi and Marshall are, however, by construction worse than lower bounds obtained via semidefinite programming, and they can only be applied in very special cases.

Independent of Ghasemi and Marshall, the second and the third author recently developed a new certificate for nonnegativity of real polynomials called sums of nonnegative circuit polynomials (SONC) [START_REF] Iliman | Amoebas, nonnegative polynomials and sums of squares supported on circuits[END_REF]. SONC certificates are independent of SOS certificates. In [START_REF]Lower bounds for polynomials with simplex newton polytopes based on geometric programming[END_REF] the second and third author showed that the GP based approach for unconstrained optimization by Ghasemi and Marshall can be generalized crucially via SONC certificates. In consequence, the presented geometric programs are linked to sums of nonnegative circuit polynomials similarly as semidefinite programming relaxations are linked to sums of squares. Particularly, there exist various classes of polynomials for which the GP/SONC based approach is not only faster but, it also yields better bounds than the SDP/SOS approach. The reason is that all certificates used by Ghasemi and Marshall are always SOS, while SONCs are not SOS in general; see [START_REF] Iliman | Amoebas, nonnegative polynomials and sums of squares supported on circuits[END_REF]Proposition 7.2].

The first contribution of this article is an extension of the results in [START_REF]Lower bounds for polynomials with simplex newton polytopes based on geometric programming[END_REF] to constrained polynomial optimization problems. We focus on the class of ST-polynomials, that are polynomials which have a Newton polytope that is a simplex and which are satisfying some further conditions; see Section 2.1. The starting point is a general optimization problem from [IdW16b, Section 5], see (2.6), which provides a lower bound for the constrained problem but which is not a geometric program. Using results from [START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF], we relax the program (2.6) into a geometric optimization problem; see program (3.2) and Theorem 3.1. Additionally, we show in Theorem 3.4 that (2.6) can always at least be transformed into a signomial program; see Section 2.2 for background information. Furthermore, we prove that the new, relaxed geometric program (3.2) provides bounds as good as the initial program (2.6) for certain special cases, see Theorem 3.5.

In Section 4, we provide examples testing our new program (3.2) in practice and comparing it with semidefinite programming. Moreover, we demonstrate that increasing the degree of a given problem has almost no effect on the runtime of our program (3.2). This is in sharp contrast to SDPs, where one can nullify increased runtimes induced by high degrees only by additional pre-processing methods, e.g. by exploiting sparsity.

Furthermore, a bound obtained by Ghasemi and Marshall in [START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF] can never be better than the bound given by the d-th Lasserre relaxation for some specific d determined by the degrees of the involved polynomials. In Section 4 we provide examples showing that our program (3.2) can provide bounds which are better than the particularly d-th Lasserre relaxations.

The second contribution of this article is to apply polynomial optimization methods based on SONCs and GPs efficiently beyond the class of ST-polynomials. In Section 5, we develop an initial approach based on triangulations of support sets of the involved polynomials. It yields bounds for nonnegativity based on SONC/GP for arbitrary polynomials both in the constrained and in the unconstrained case. We provide several examples and compare the new bounds to the ones obtained by SDP based methods.

Acknowledgements. We thank Henning Seidler for various comments and his support on some of the computations. We also thank the anonymous referees, who helped us to improve the article significantly.

The third author was partially supported by the DFG grant WO 2206/1-1.

Preliminaries

In this section we recall key results about sums of nonnegative circuit polynomials (SONCs) and geometric programming (GP), which are used in this article.

2.1. The Cone of Sums of Nonnegative Circuit Polynomials. We denote by Rrxs " Rrx 1 , . . . , x n s the vector space of real n-variate polynomials. Let δ ij be the ij-Kronecker symbol, let e i " pδ i1 , . . . , δ in q be the i-th standard vector, and let A Ă N n be a finite set. We denote by convpAq the convex hull of A and by V pAq the vertices of convpAq. We consider polynomials f P Rrxs supported on A. That is, f is of the form f pxq "

ř αPA f α x α with f α P R, x α " x α 1 1 ¨¨¨x αn n .
We call a lattice point even if it is in p2Nq n . Furthermore, we denote the Newton polytope of f as Newpf q " convtα P N n : f α ‰ 0u.

For a given A Ă N n we define ∆pAq " AzV pAq. Let f be as before. We denote by ∆pf q the elements of ∆pAq which appear as exponents of non-zero terms, that are no monomial squares. I.e., we have ∆pf q " tα P ∆pAq : f α ‰ 0 and pf α ă 0 or α R p2Nq n qu.

A polynomial is nonnegative on the entire R n only if the following necessary conditions are satisfied; see e.g. [START_REF] Reznick | Extremal PSD forms with few terms[END_REF].

Proposition 2.1. Let A Ă N n be a finite set and f P Rrxs be supported on A such that Newpf q " convpAq. Then f is nonnegative on R n only if:

(1) All elements of V pAq are even.

(2) If α P V pAq, then the corresponding coefficient f α is strictly positive.

In other words, if α P V pAq, then the term f α x α has to be a monomial square.

The statement remains true for real Laurent polynomials g P Rrx ˘1s " Rrx ˘1 1 , . . . , x ˘1 n s, since we can consider g as a polynomial f divided by a monomial square x α for an even α; this is of relevance in Section 5. For the remainder of the article, we assume that these necessary conditions in Proposition 2.1 are satisfied including Newpf q " convpAq. For simplicity, we denote this assumption by the symbol p♣q from now on.

In what follows we consider the class of ST-polynomials. For further details about the following objects defined in this section see [START_REF] Wolff | Amoebas, nonnegative polynomials and sums of squares supported on circuits[END_REF][START_REF] Iliman | Amoebas, nonnegative polynomials and sums of squares supported on circuits[END_REF][START_REF]Lower bounds for polynomials with simplex newton polytopes based on geometric programming[END_REF]; see also [START_REF] Fidalgo | Positive semidefinite diagonal minus tail forms are sums of squares[END_REF][START_REF] Ghasemi | Lower bounds for polynomials using geometric programming[END_REF][START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF]. Definition 2.2. Let f P Rrxs be supported on A Ă N n such that p♣q holds. Then f is called an ST-polynomial if it is of the form Note that hypotheses (ST1) and (ST2) imply that V pAq " tαp0q, . . . , αprqu is the vertex set of an r-dimensional simplex. By the assumption p♣q it consists of even lattice points, and it coincides with Newpf q " convpAq. The λ pβq j denote the barycentric coordinates of β relative to the vertices αpjq with j " 0, . . . , r. The "ST" in "ST-polynomial" is short for "simplex tail". The tail part is given by the sum ř βP∆pAq f β x β , while the other terms define the simplex part. If an ST-polynomial f has a tail part consisting of at most one term, then we call f a circuit polynomial . Nonnegativity of ST-polynomials is closely related to an invariant called the circuit number.

f pxq " r ÿ j"0 f αpjq x αpjq `ÿ βP∆pAq f β x β , ( 2
Definition 2.3. Let f be an ST-polynomial with support set A. For every β P ∆pAq we define the corresponding circuit number as Θ f pβq "

ź jPnzpβq ˜fαpjq λ pβq j ¸λpβq j (2.2)
with nzpβq " tj P t0, . . . , ru : λ pβq j ‰ 0u, f αpjq , and λ pβq j as before.

The terms "circuit polynomial" and "circuit number" are chosen since β and the αpjq with j P nzpβq form a circuit; this is a minimally affine dependent set, see e.g. [START_REF] Oxley | Matroid theory[END_REF].

A fundamental fact is that nonnegativity of a circuit polynomial f can be decided by comparing its tail coefficient f β with its corresponding circuit number Θ f pβq alone.

Theorem 2.4 ([IdW16a], Theorem 3.8). Let f be a circuit polynomial with unique tail term f β x β and let Θ f pβq be the corresponding circuit number, as defined in (2.2). Then the following statements are equivalent:

(1) f is nonnegative.

(2) |f β | ď Θ f pβq and β R p2Nq n or f β ě ´Θf pβq and β P p2Nq n .

Note that (2) can be equivalently stated as: |f β | ď Θ f pβq or f is a sum of monomial squares.

Writing a polynomial as a sum of nonnegative circuit polynomials is a certificate of nonnegativity. We denote by SONC the class of polynomials that are sums of nonnegative circuit polynomials or the property of a polynomial to be in this class.

Geometric Programming. Geometric programming was introduced in [DPZ67].

It is a convex optimization problem and has applications for example in nonlinear network flow problems, optimal control, optimal location problems, chemical equilibrium problems and particularly in circuit design problems.

Definition 2.5. A function p : R n ą0 Ñ R of the form ppzq " ppz 1 , . . . , z n q " cz α 1 1 ¨¨¨z αn n with c ą 0 and α i P R is called a monomial (function). A sum

ř k i"0 c i z α 1 piq 1 ¨¨¨z αnpiq n
of monomials with c i ą 0 is called a posynomial (function).

A geometric program (GP) has the following form: $ ' & ' % minimize p 0 pzq, subject to: p1q p i pzq ď 1 for all 1 ď i ď m, p2q q j pzq " 1 for all 1 ď j ď l,

where p 0 , . . . , p m are posynomials and q 1 , . . . , q l are monomial functions.

Geometric programs can be solved with interior point methods. In [START_REF] Nesterov | Interior point polynomial algorithms in convex programming[END_REF], the authors prove worst-case polynomial time complexity of this method; see also [START_REF] Boyd | A tutorial on geometric programming[END_REF]Page 118]. A signomial program is given like a geometric program except that the coefficients c i of the involved posynomials can be arbitrary real numbers.

For an introduction to geometric programming, signomial programming, and an overview about applications see [START_REF] Boyd | A tutorial on geometric programming[END_REF][START_REF] Boyd | Convex optimization[END_REF].

SONC Certificates via Geometric Programming in the Unconstrained

Case. In this section we recall the main results from [START_REF]Lower bounds for polynomials with simplex newton polytopes based on geometric programming[END_REF] about SONC certificates obtained via geometric programming for unconstrained polynomial optimization problems. These results always require that the polynomial in the optimization problem is an ST-polynomial in the sense of Section 2.1.

Theorem 2.6. ([IdW16b, Theorems 3.4 and 3.5]) Assume that f is an ST-polynomial as in (2.1) with αp0q " 0 and let k P R. Suppose that for every pβ, jq P ∆pf q ˆt1, . . . , ru there exists an a β,j ě 0, such that:

(1) a β,j ą 0 if and only if λ .

Then f ´k is a sum of nonnegative circuit polynomials g 1 , . . . , g s such that s :" |∆pf q|, and for every g i the Newton polytope Newpg i q is a face of Newpf q. Let f sonc be the supremum of all k P R such that for every β P ∆pf q there exist nonnegative reals a β,1 , . . . , a β,r such that the conditions p1q to p4q are satisfied. Then f sonc coincides with the supremum of all k P R such that there exist nonnegative circuit polynomials g 1 , g 2 , . . . , g s whose Newton polytopes are faces of Newpf q and which satisfy f ´k " ř s i"1 g i .

We remark that Theorem 2.6 remains valid if all terms of an ST-polynomial are multiplied by a monomial square x αp0q P p2Nq n . In this case, condition needs to be replaced by

p4 1 q pf αp0q ´kqx αp0q ě ř βP∆pf q λ pβq 0 ‰0 λ pβq 0 |f β | 1{λ pβq 0 ś jPnzpβq jě1 ˆλpβq j a β,j ˙λpβq j {λ pβq 0 .
We then obtain a nonnegativity bound for the (positive) the coefficient of the term x αp0q instead of the constant term. We apply this slightly more general version of Theorem 2.6 in Section 5.

For the special case of scaled standard simplices Theorem 2.6 was shown earlier by Ghasemi and Marshall [GM12, Theorem 3.1]. In this special case every sum of nonnegative circuit polynomials is also a sum of binomial squares which is not true in general. For example, the Motzkin polynomial is an ST-polynomial with one interior term, which is not even a SOS.

Theorem 2.6 states

f sonc " suptk P R : f ´kx αp0q is a SONC u.
The bound f sonc is given by a geometric program [IdW16b, Corollary 4.2]:

Corollary 2.7. Let f P Rrxs be an ST-polynomial. Let R be the subset of an r|∆pf q|dimensional real space given by R " tpa β,j q : a β,j P R ą0 for every β P ∆pf q and j P nzpβqu.

Then f sonc " f αp0q ´m˚, where m ˚is given as the output of the following geometric program:

$ ' ' ' ' ' ' ' ' ' ' ' ' & ' ' ' ' ' ' ' ' ' ' ' ' % minimize ř βP∆pf q λ pβq 0 ‰0 λ pβq 0 |f β | 1{λ pβq 0 ś jPnzpβq jě1 ˆλpβq j a β,j ˙λpβq j {λ pβq 0 over the subset R 1 of R
defined by: p1q ř βP∆pf q pa β,j {f αpjq q ď 1 for every 1 ď j ď r,

p2q |f β | ś jPnzpβq ˆλpβq j a β,j ˙λpβq j ď 1 for every β P ∆pf q with λ pβq 0 " 0.
Hence, the optimal bound to find a SONC decomposition of an ST-polynomial is provided by geometric programming. Since a polynomial with a SONC decomposition is nonnegative, geometric programming can be used to find certificates of nonnegativity.

Following the literature, e.g. [START_REF] Blekherman | Semidefinite optimization and convex algebraic geometry[END_REF][START_REF] Laurent | Sums of squares, moment matrices and optimization over polynomials[END_REF], we define a global polynomial optimization problem for some f P Rrxs as the problem to determine the real number

f ˚" inftf pxq : x P R n u " suptλ P R : f ´λ ě 0u.
One can find a lower bound for f ˚by relaxing the nonnegativity condition in the above problem to finding the real number

f sos " sup # λ P R : f ´λ " k ÿ i"1
q 2 i for some q i P Rrxs + .

The bound f sos for the optimal SOS decomposition of f can be determined by semidefinite programming. By construction, we have f sos ď f ˚; see [START_REF]Moments, positive polynomials and their applications[END_REF].

A key observation is that the bounds obtained by this approach can be better than the ones obtained by SDP as the following result shows; see [IdW16b, Corollary 3.6].

Corollary 2.8. Let f be an ST-polynomial with ∆pAq " ∆pf q such that ∆pf q is contained in the interior of Newpf q. Let αp0q be the origin and suppose that there exists a vector v P pR ˚qn such that f α ¨vα ă 0 for all α P ∆pf q. Then f sonc " f ˚ě f sos .

2.4. SONC Certificates for the Constrained Case. In this subsection we restate facts from [IdW16b, Section 5] about SONC certificates applied to constrained polynomial optimization problems. Let f, g 1 , . . . , g s be elements of the polynomial ring Rrxs and let K " tx P R n : g i pxq ě 0 for all i " 1, . . . , su be a basic closed semialgebraic set defined by g 1 , . . . , g s . We consider the constrained polynomial optimization problem

f K " inf xPK f pxq " suptγ P R : f pxq ´γ ě 0 for all x P Ku.
If s " 0, then we have no g i and therefore K " R n , which leads to the global optimization problem explained in Section 2.3.

To obtain a general lower bound for f on K which is computable by geometric programming we replace the considered polynomials by a new function. Let

Gpµqpxq " f pxq ´s ÿ i"1 µ i g i pxq " ´s ÿ i"0 µ i g i pxq (2.4)
for µ " pµ 1 , . . . , µ s q P R s ě0 , g 0 " ´f and µ 0 " 1. For every fixed µ ˚P R s ě0 the function Gpxq " Gpµ ˚qpxq is a polynomial in Rrxs. Following an argument in [START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF] we can assume that all monomial squares of ´gi are vertices of NewpGpµqq: One can reduce to this case by neglecting all monomial squares not corresponding to such a vertex. That is, for all i " 0, . . . , s one can replace g i by gi , which resemble g i without monomial squares of ´gi in the interior of NewpGpµqq. Then ´g i ď ´gi on R n for i " 0, . . . , s, thus, K Ď K, where K " tx P R n : gi pxq ě 0, 1 ď i ď su, as well as f K ď f K .

Let A i Ă N n be the support of the polynomial g i for i " 0, . . . , s and let A " Ť s i"0 A i be the union of all supports of polynomials g i . We remark that while we consider a fixed support the Newton polytope of Gpµq is not invariant in general since certain µ i might equal 0 or term cancellation might occur. If for some µ P R s ě0 the polynomial Gpµq is an ST-polynomial, then we assume that NewpGpµqq " convpAq and V pAq " tαp0q, . . . , αprqu Ă p2Nq n and we denote Gpµq sonc as the optimal value of the geometric program in Corollary 2.7. Theorem 2.6 implies that Gpµq ´Gpµq sonc x αp0q ě 0 and Gpµq sonc P R is the maximal possible choice for nonnegativity. Hence, we obtain a bound for the coefficient of the term x αp0q depending on the other coefficients of Gpµq certifying nonnegativity of Gpµq. If Gpµq is not an ST-polynomial for some µ P R s ě0 , then we set Gpµq sonc " ´8, since the corresponding geometric program is infeasible. Thus, by (2.4), if µ is fixed, then Gpµq sonc is a lower bound for f on the semialgebraic set K regarding the coefficient of x αp0q . Let g " pg 1 , . . . , g s q. We define spf, gq " suptGpµq sonc : µ P R s ě0 u. Thus, we have particularly for αp0q " 0: spf, gq ď f K .

(2.5) For every fixed µ the bound Gpµq sonc is computable by a geometric program. Unfortunately, this does not imply that the supremum is computable by a GP as well. However, following ideas by Ghasemi and Marshall [START_REF] Ghasemi | Lower bounds for polynomials using geometric programming[END_REF] the second and third author presented a general optimization program for a lower bound of spf, gq in [START_REF]Lower bounds for polynomials with simplex newton polytopes based on geometric programming[END_REF], which is a geometric program under special conditions. We recall these results in what follows.

We define ∆pAq in the sense of Section 2.1 as the set of exponents of the tail terms of Gpµq and ∆pGpµqq Ď ∆pAq as the set of exponents which have a non-zero coefficient and are not a monomial square. Moreover, we define ∆pGq " Ť µPR s ě0 ∆pGpµqq. Note that ∆pGpµqq Ď ∆pGq Ď ∆pAq for all µ. We have by Section 2.1, Definition 2.2

Gpµqpxq " ´s ÿ i"0 µ i g i pxq " r ÿ j"0 Gpµq αpjq x αpjq `ÿ βP∆pGq Gpµq β x β
with coefficients Gpµq αpjq , Gpµq β P R depending on µ. We set the coefficients Gpµq β " 0 for all β P ∆pGqz∆pGpµqq.

As before, we denote by tλ pβq 0 , . . . , λ pβq r u the barycentric coordinates of the lattice point β P ∆pAq with respect to the vertices of the simplex NewpGpµqq " convpAq. We define for every β P ∆pGq a set R β " ta β : a β " pa β,1 , . . . , a β,r q P R r ą0 u. Furthermore, we define the nonnegative real set R as R " r0, 8q s ˆą βP∆pGq pR β ˆRě0 q.

Hence, R is the Cartesian product of r0, 8q s and |∆pGq| many copies R r ą0 ˆRě0 ; each given by one R β with β P ∆pGq and one R ě0 . We define the function p from R to R ě0 as ppµ, tpa β , b β q : β P ∆pGquq "

s ÿ i"1 µ i g i,αp0q
`ÿ βP∆pGq where, as before, αp0q is a vertex of NewpGpµqq and g i,αp0q is the coefficient of the monomial x αp0q in the polynomial g i .

For the coefficient Gpµq β of the term with exponent β of Gpµq we use the notation Gpµq β " ´řs i"0 µ i ¨gi,β . In other words, Gpµq β is a linear form in the µ i 's given by the coefficients of the polynomials g i ; analogously for Gpµq αpjq . We consider the following optimization problem: (2.6)

$ ' ' ' ' ' ' ' ' ' ' & ' ' ' ' ' ' ' ' ' ' % minimize ppµ,
In [IdW16b, Theorems 5.1 and 5.2] the second and third author show the following theorem.

Theorem 2.9. Let γ be the optimal value of the optimization problem (2.6). Then we have f αp0q ´γ ď spf, gq. The optimization problem (2.6) restricted to µ P p0, 8q s is a signomial program if for every β P ∆pGq it holds that Gpµq β has the same sign for every choice of µ.

Assume additionally that every linear form Gpµq αpjq " ´řs i"0 µ i ¨gi,αpjq corresponding to a vertex αpjq of NewpGpµqq has only one summand and is strictly positive. Assume moreover that for all β P ∆pGq the linear form Gpµq β " ´řs i"0 µ i ¨gi,β has only positive terms. If furthermore all g i,αp0q for 1 ď i ď s are greater than or equal to zero, then (2.6) is a geometric program.

Constrained Polynomial Optimization via Signomial and Geometric Programming

In this section, we provide relaxations of the program (2.6) following ideas of Ghasemi and Marshall in [START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF]. The goal is to weaken the assumptions which are needed to obtain a geometric program or at least a signomial program. We provide such relaxations in the programs (3.2) and (3.3) and provide the desired properties in the Theorems 3.1 and 3.4. Moreover, we show that under certain extra assumptions the bound obtained by the new program (3.2) equals the optimal bound spf, gq from the previous section; see Theorem 3.5. Let all notation regarding Gpµq be given as in Section 2.4. Assume that we have for each 0 ď i ď s g i "

ÿ βPA i g i,β
¨xβ with g i,β P R. We have ∆pA i q Ď ∆pAq and hence write

g i " r ÿ j"0 g i,αpjq x αpjq `ÿ βP∆pAq g i,β x β
and set g i,αpjq " 0 for all αpjq P V pAqzA i and g i,β " 0 for all β P ∆pAqzA i . We remark that three cases can occur for β P ∆pAq X A i :

(1) ´gi,β x β is not a monomial square. Then we have β P ∆pGq.

(2) ´gi,β x β is a monomial square, but there exists another g l such that ´gl,β x β is not a monomial square. Then we have β P ∆pGq. (3) ´gi,β x β is a monomial square, and there exists no other g l such that ´gl,β x β is not a monomial square. Then we have β R ∆pGq.

Sums of monomial squares as described in case (3) are ignored in our program (2.6). Hence, we can also ignore this case here. We investigate the other two cases in detail now. As already mentioned in Section 2.4 we can interpret the coefficients Gpµq αpjq and Gpµq β as linear forms in µ since we have for all j " 0, . . . , r Gpµq αpjq " ´s ÿ

i"0 µ i ¨gi,αpjq and Gpµq β " ´s ÿ

i"0

µ i ¨gi,β .
We decompose every Gpµq β into a positive and a negative part such that Gpµq β " Gpµq β ´Gpµq β , where

Gpµq β " ÿ g i,β ą0 µ i ¨gi,β and Gpµq β " ´ÿ g i,β ă0 µ i ¨gi,β . (3.1)
This decomposition is independent of the choice of µ in the sense that no g i,β can be a summand of both Gpµq β and Gpµq β for different choices of µ since µ P R s ě0 . The key idea is to redefine the constraint b β ě |Gpµq β | by a new constraint b β ě maxtGpµq β , Gpµq β u. Let R be defined as in Section 2.4 and let g ì,αp0q " maxtg i,αp0q , 0u, i.e., we only consider the terms with exponents αp0q which are positive in the g i and thus negative in Gpµq.

We redefine p as ppµ, tpa β , b β q : β P ∆pGquq "

s ÿ i"1 µ i g ì,αp0q
`ÿ βP∆pGq .

We consider the following optimization problem in the variables µ 1 , . . . , µ s and a β,1 , . . . , a β,r , b β for every β P ∆pGq. This problem is, by condition (1), feasible only for choices of µ such that Gpµq αpjq ą 0 for all αpjq since all a β,j are strictly positive. We set the output as ´8 in all other cases. Indeed, with some additional assumptions the program (3.2) is a geometric program. Moreover, it is a relaxation of the program (2.6).

$ ' ' ' ' ' ' ' ' ' ' ' ' & ' ' ' ' ' ' ' ' ' ' ' ' % minimize ppµ,
Theorem 3.1. Assume that for every 1 ď j ď r the form Gpµq αpjq " ´řs i"0 µ i ¨gi,αpjq has exactly one strictly positive term, i.e. there exists exactly one strictly negative g i,αpjq . Then the optimization problem (3.2) restricted to µ P p0, 8q s is a geometric program. Assume that γ sonc denotes the optimal value of (3.2) and γ denotes the optimal value of (2.6). Then we have

f αp0q ´γsonc ď f αp0q ´γ ď spf, gq.
The typical choice for αp0q is the origin which yields a lower bound for f to be nonnegative on K with the inequality (2.5):

Corollary 3.2. Let all assumptions be as in Theorem 3.1. If αp0q is the origin, then we have

f 0 ´γsonc ď f 0 ´γ ď spf, gq ď f K .
Proof. (Theorem 3.1) If we restrict ourselves to µ P p0, 8q s , then all functions involved in (3.2) depend on variables in R ą0 . By assumption every Gpµq αpjq has exactly one strictly positive term. Thus, we can express constraint (1) as ř βP∆pGq a β,j `Gpµq άpjq Gpµq ὰpjq ď 1, with Gpµq άpjq and Gpµq ὰpjq defined analogously as in (3.1). Since Gpµq ὰpjq is a monomial the left hand side is a posynomial in µ and x. The constraints (2) -( 4) are posynomial constraints in the sense of Definition 2.5 of a geometric program. The function p is also a posynomial since all terms are nonnegative by construction and all exponents are rational. Moreover, every b β in (3.2) has to be greater or equal than the corresponding b β in (2.6) because maxta, bu ě |a ´b| for all a, b P Rzt0u. Since furthermore g ì,αp0q ě g i,αp0q it follows that γ sonc ď γ by the definitions of (3.2) and (2.6). The last inequality follows from Theorem 2.9.

One expects the programs (2.6) and (3.2) to have a similar optimal value if, for example, g i,αp0q ě 0 for most i " 1, . . . , s and if one Gpµq β , Gpµq β is identically zero for most β P ∆pGq. Note that one of Gpµq β , Gpµq β is zero if and only if maxtGpµq β , Gpµq β u " |Gpµq β ´Gpµq β | " |Gpµq β | if and only if the g i,β are all ě 0 or all ď 0 for i " 0, . . . , s.

We give an example to demonstrate how a given constrained polynomial optimization problem can be translated into the geometric program (3.2). In Section 4, we provide several further examples including actual computations of infima using the GP-solver CVX. Example 3.3. Let f " 1 `2x 2 y 4 `1 2 x 3 y 2 and g 1 " 1 3 ´x6 y 2 . From these two polynomials we obtain a function

Gpµq " ˆ1 ´1 3 µ ˙`2x 2 y 4 `µx 6 y 2 `1 2 x 3 y 2 .
For Gpµq to be an ST-polynomial, we have to choose µ P p0, 3q. Here, the vertices of NewpGpµqq are αp0q " p0, 0q, αp1q " p2, 4q, αp2q " p6, 2q, and we have ∆pGq " tβu " tp3, 2qu. Thus, we introduce 4 variables pa β,1 , a β,2 , b β , µq. First, we compute the barycentric coordinates of β and get

λ pβq 0 " 3 10 , λ pβq 1 " 3 10 , λ pβq 2 " 2 5 .
We match the coefficients of Gpµq with the vertices αpjq:

' g 1,αp0q " maxt 1 3 , 0u " 1 3 , ' Gpµq αp1q " 2, Gpµq αp2q " µ , ' Gpµq β " 1 2 , Gpµq β does not exist. Hence, Program (3.2) is of the form: inf # 1 3 µ `3 10 ¨b 10 3 β ¨ˆ3 10
˙1 ¨ˆ2 5
˙4 3 ¨pa β,1 q ´1 ¨pa β,2 q ´4 3 + such that:

(1) a β,1 ď 2, a β,2 ď µ.

(2) The second constraint does not appear, because we do not have λ In what follows, we extend Theorem 2.9 by reformulating the program (3.2) such that it is always applicable. On the one hand, the new program is only a signomial program instead of a geometric program in general. On the other hand, the reformulated program covers the missing cases of Theorem 3.1 and also yields better bounds than the corresponding geometric program (3.2) in general. Let qpµ, tpa β , c β q : β P ∆pGquq "

s ÿ i"1 µ i g i,αp0q
`ÿ βP∆pGq (3.3)

The key difference between this program and (3.2) is that

c β ě maxtGpµq β ´Gpµq β , Gpµq β ´Gpµq β u " |Gpµq β |.
We obtain the following statement.

Theorem 3.4. The optimization problem (3.3) restricted to µ P p0, 8q s is a signomial program. Assume that γ snp denotes the optimal value of (3.3) and γ sonc , γ denote the optimal values of (3.2) and (2.6) as before. Then we have f αp0q ´γsonc ď f αp0q ´γsnp ď f αp0q ´γ ď spf, gq.

Particularly, we have γ snp " γ if the program (2.6) attains its optimal value for µ P p0, 8q s .

Proof. The proof is analogue to the proof of Theorem 3.1. The only difference is that certain terms can have a negative sign now and hence posynomials then become signomials.

The statement follows with the definition of a signomial program; see Section 2.2. .

Hence, f αp0q ´γsonc ě Gpµ ˚qsonc " spf, gq.

Examples for Constrained Optimization via Geometric Programming and a Comparison to Lasserre Relaxations

We consider constrained polynomial optimization problems of the form

f K " inf xPK f pxq,
where K is a basic closed semialgebraic set defined by g 1 , . . . , g s ě 0. One of the main results in [START_REF]Lower bounds for polynomials with simplex newton polytopes based on geometric programming[END_REF] is the observation that lower bounds for global optimization problems arising from SONCs via GP can not only be computed faster, but also be better than the bounds obtained by SOS via SDP. Here, we show that competitive bounds arising from SONC via GP can also be obtained for constrained problems. Particularly, if 2d is the maximal total degree of f and g 1 , . . . , g s , then the bound given by the d-th Lasserre relaxation is not necessarily as good as our optimal solution, which is in contrast to the bounds obtained by Ghasemi and Marshall; see Example 4.5 for further details. Moreover, we provide runtimes for rescaled version of our examples demonstrating that the runtime of the GP approach is not sensitive to increasing the degree of a given problem. This has been observed by several authors in the past, e.g. [BKVH07, GM12, GM13], and is in contrast to the runtime of SDPs.

Let ΣRrxs 2 denote the set of n-variate sums of squares. We consider the d-th Lasserre relaxation [Las10]

f pdq sos " sup # r : f ´r " s ÿ i"0 σ i g i , σ i P ΣRrxs 2 , g 0 " 1, degpσ i g i q ď 2d + , (4.1)
where d ě max trdegpf q{2s, max 1ďiďs trdegpg i q{2suu.

In what follows we provide several examples comparing Lasserre relaxation using the Matlab SDP solver Gloptipoly [START_REF] Henrion | GloptiPoly 3: moments, optimization and semidefinite programming[END_REF] to our approach given in program (3.2) using the Matlab GP solver CVX [START_REF] Boyd | Graph implementations for nonsmooth convex programs, Recent Advances in Learning and Control[END_REF][START_REF] Boyd | Disciplined convex programming, Global optimization[END_REF]. In every example in this section we optimize with respect to the constant term when applying program (3.2).

Example 4.1. Let f " 1 `x4 y 2 `x2 y 4 ´3x 2 y 2 be the Motzkin polynomial and g 1 " x 3 y 2 . Then K " tpx, yq P R 2 : x ě 0 or y " 0u.

Since f is globally nonnegative and has two zeros p1, 1q, p1, ´1q on K, e.g. [Rez00], we have f K " 0. We consider the third Lasserre relaxation and obtain f p3q sos " sup r : f ´r " σ 0 `σ1 ¨g1 , σ 0 , σ 1 P ΣRrxs 2 , degpσ 0 q ď 6, degpσ 1 g 1 q ď 6 ( " ´8, since the problem is infeasible. Note that K is unbounded. Hence, it is not necessarily the case that f pdq sos ą ´8 for sufficiently high relaxation order d. Here, using Gloptipoly, one can find that f p7q sos " 0 " f K . Now, we consider spf, g 1 q " suptGpµq sonc : µ P R ě0 u ď f K where Gpµq " f ´µg 1 with µ ě 0. Note that NewpGpµqq is a simplex for every choice of µ. In particular, for µ " 0 we have that Gpµq sonc " f sonc " 0, since the Motzkin polynomial is a SONC polynomial; see Section 2.1 and also [START_REF] Iliman | Amoebas, nonnegative polynomials and sums of squares supported on circuits[END_REF]. It follows that ´8 " f p3q sos ă spf, g 1 q " 0 " f K . Hence, spf, g 1 q yields the exact solution compared to the Lasserre relaxation. This is in sharp contrast to the geometric programming approach proposed in [START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF] where f pdq sos ě spf, gq holds in general.

Note that there are techniques which handle polynomial optimization problems over unbounded feasible sets better than the SOS/SDP method, e.g. using the gradient ideal [START_REF] Nie | Minimizing polynomials via sum of squares over the gradient ideal[END_REF] or using gradient tentacles [START_REF] Schweighofer | Global optimization of polynomials using gradient tentacles and sums of squares[END_REF]. Here, we restrict ourselves, however, to a comparison to SDP based methods.

Example 4.2. Let f " 1 `x4 y 2 `xy and g 1 " 1 2 `x2 y 4 ´x2 y 6 . The feasible set K is a non-compact set depicted in Figure 1. Using Gloptipoly, one can check that ´8 " f p4q sos and the optimal solution is given for d " 8 with f p8q sos « 0.4474. In this case one can extract the minimizers p´0.557, 1.2715q and p0.557, ´1.2715q.

We compare the results to our approach via geometric programming instead of Lasserre relaxations. From f and g 1 we get Gpµq " p1 ´1 2 µq `x4 y 2 `µx 2 y 6 `xy ´µx 2 y 4 . Note that NewpGpµqq is a two dimensional simplex if µ R t0, 2u. Then, we have ∆pGq " tβ, βu " tp1, 1q, p2, 4qu. Hence, we introduce the variables pa β,1 , a β,2 , a β,1 , a β,2 , b β , b β, µq. Therefore, the geometric program (3.2) reads as follows:

inf " 1 2 µ `7 10 ¨b 10 7 β ¨`1 5 ˘2 7 ¨`1 10 ˘1 7 ¨pa β,1 q ´2 7 ¨pa β,2 q ´1 7 `1 5 ¨b5 β ¨`1 5 ˘1 ¨`3 5 ˘3 ¨pa β,1 q ´1 ¨pa β,2 q ´3*
such that the variables satisfy

a β,1 `aβ ,1 ď 1, a β,2 `aβ ,2 ď µ and 1 ď b β , µ ď b β .
We use the Matlab solver CVX to solve the program given above. The optimal solution is given by pa β,1 , a β,2 , a β,1 , a β,2 , b β , b β, µq " p0.9105, 0.0540, 0.0895, 0.0319, 1.0000, 0.0859, 0.0859q .

This leads to

γ sonc « 0.5526 and hence f αp0q ´γsonc « 0.4474. Thus, we have

f p8q
sos " f αp0q ´γsonc " spf, g 1 q. The equality f αp0q ´γsonc " spf, g 1 q is not surprising, since the assumptions of Theorem 3.5 are satisfied. Thus, we get the optimal solution immediately via geometric programming whereas one needs 5 relaxation steps via Lasserre relaxation. In this example both geometric programing and the Lasserre approach have a runtime below 1 second. Now, we demonstrate that our approach, in contrast to SDPs, is not sensitive to increasing the degree, since it is based on GPs. Namely, if we multiply all exponents in f and g 1 by 10, then the approaches differ significantly. By multiplying the exponents by 10 we have made a severe change to the problem since the term x 10 y 10 is now a monomial square such that the exponent is a lattice point in the interior of the Newton polytope of the adjusted Gpµq. Therefore, we have to ignore this term out when running the constrained optimization program (3.2). The adjusted program yields with CVX an output NaN in below one second. However, the reason is that it computes µ " 0, which is the correct answer. Namely, after multiplying the exponents by 10, the only non monomial square terms are given by g 1 . Thus, the optimal choice is µ " 0, and we can see that the minimal value is attained at p0, 0q and f K " 1 is given by the constant term of f .

In comparison, we have a runtime of approximately 1110 seconds, i.e. approximately 18.5 minutes with Gloptipoly. After this time Gloptipoly provides an output "Run into numerical problems.". It claims, however, to have solved the problem and provides the correct minimum f K " 1 at a minimizer 10 ´7 ¨p´0.1057, 0.1711q, which, of course, is the origin up to a numerical error.

We remark that this particular artificial increase of the degree can, of course, be handled with SDP methods using pre-processing methods, e.g. a change of variables. The purpose of the rescaling of this and later examples is, however, to show that SONC/GP methods are inherently not sensitive to an increase of the degree.

Example 4.3. Let f " 1`x 2 z 2 `y2 z 2 `x2 y 2 ´8xyz and g 1 " x 2 yz `xy 2 z `x2 y 2 ´2`xyz.
Using Gloptipoly, we get the following sequence of lower bounds:

f p2q
sos " f p3q sos " f p4q sos " ´8 ă f p5q sos « ´14.999. However, one cannot certify the optimality via Gloptipoly in this case. Additionally, the sequence f pdq sos is not guaranteed to converge to f K , since K is unbounded. Symbolically, we were able to prove a global minimum of f K " ´15 with four global minimizers p2, 2, 2q, p´2, ´2, 2q, p´2, 2, ´2q, p2, ´2, ´2q using the quantifier elimination software Synrac, see [START_REF] Anai | SyNRAC: a Maple-package for solving real algebraic constraints[END_REF]. Now, we consider the approach via geometric programming instead of Lasserre relaxations. We have

Gpµq " p1 `2µq `x2 z 2 `y2 z 2 `p1 ´µqx 2 y 2 `p´8 ´µqxyz ´µx 2 yz ´µxy 2 z.
Therefore, Gpµq is an ST-polynomial for µ P r0, 1q, and we have ∆pGq " tβ, β, βu " tp1, 1, 1q, p2, 1, 1q, p1, 2, 1qu. Thus, our geometric program has the following 13 variables

pa β,1 , a β,2 , a β,3 , a β,1 , a β,2 , a β,3 , a β,1 , a β,2 , a β,3 , b β , b β , b β, µq. Hence, program (3.2) is of the form inf " 0 ¨µ `1 4 ¨b4 β ¨ˆ1 4 ˙¨ˆ1 4 ˙¨ˆ1 4 ˙¨pa β,1 q ´1 ¨pa β,2 q ´1 ¨pa β,3 q ´1* such that p1q a β,1 `aβ,1 `aβ ,1 ď 1, a β,2 `aβ,2 `aβ ,2 ď 1, a β,3 `aβ,3 `aβ ,3 `µ ď 1, p2q 1 2 ¨bβ ¨`a β,1 ˘´1 2 ¨`a β,3 ˘´1 2 ď 1, 1 2 ¨bβ ¨´a β,2 ¯´1 2 ¨´a β,3 ¯´1 2 ď 1, p3q 8 ¨b´1 β ď 1, µ ¨b´1 β ď 1, µ ¨b´1 β ď 1, µ ¨b´1 β ď 1 .
This leads to γ sonc " 1 256 ¨84 " 16 and so f αp0q ´γsonc " ´15. The runtime for this example is below 1 second. Multiplying the exponents of f and g 1 by 10 yields the same results; the runtime for the geometric program remains below 1 second. In comparison, Gloptipoly yields f pdq sos " ´8 for d ď 19, and provides a bound f p20q sos « ´14.999 in the 20-th relaxation after 36563 seconds, i.e. approximately 10.16 hours. Moreover, although this bound is numerically equal to f K , Gloptipoly was not able to certify that the correct bound was found.

Example 4.4. Let f " z 6 `x4 y 2 `x2 y 4 ´3x 2 y 2 z 2 and g 1 " x 2 `y2 `z2 ´1. We obtain Gpµq " f ´µg 1 . This problem is infeasible in the sense of program (3.2). Namely, condition p♣q is never satisfied since for any µ ą 0 we have a vertex p2, 0, 0q or p0, 2, 0q of NewpGpµqq with a negative coefficient. Therefore, one can immediately conclude that spf, g 1 q has to be obtained for µ " 0. Thus, we have spf, g 1 q " f sonc . Since f is the homogenized Motzkin polynomial we obtain immediately f sonc " f K " 0. An analogous argumentation holds for the variation Gpµq " f `µg 1 . It is well-known that SDP solvers have serious issues with optimizing f for g 1 ě 0 or g 1 ď 0. For further information see [START_REF]An exact Jacobian SDP relaxation for polynomial optimization[END_REF]Examples 5.3 and 5.4].

In the last example in this section we show that for special simplices our geometric programming approach coincides with the one in [START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF].

Example 4.5. Suppose that NewpGpµqq " convt0, 2d e 1 , . . . , 2d e n u. Hence, the Newton polytope is a 2d-scaled standard simplex in R n , which is the case if the pure powers x 2d j for 1 ď j ď n are present in the polynomial f or in the constrained polynomials g i . The corresponding polynomial Gpµq is an ST-polynomial; see Section 2.1. Indeed, all examples in [GM13, Example 4.8] are of that form and thus all of them are ST-polynomials.

In this case the program (2.6) coincides with the program (3) in [START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF]. One drawback of this setting is that the geometric programming bounds obtained from (2.6) are at most as good as the bound f pdq sos . Namely, if the Newton polytope of a circuit polynomial is a scaled standard simplex, then it is nonnegative if and only if it is a sum of squares; see [START_REF] Iliman | Amoebas, nonnegative polynomials and sums of squares supported on circuits[END_REF] for further details. Thus, if we are in the setting of Ghasemi and Marshall and Gpµq is nonnegative, then it is a sum of squares of degree at most 2d which guarantees the existence of a decomposition in the sense of f pdq sos ; see (4.1). However, as we have shown in the previous examples, in the case of our program (2.6) there exist also cases where the geometric programming bounds are better than f pdq sos , since our approach is more general than in [START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF]. The reason is that the cones of sums of nonnegative circuit polynomials and sums of squares do not contain each other (but both of them are contained in the cone of nonnegative polynomials); see [IdW16a, Prop. 7.2].

We point out that we make no assumption about the feasible set K. In particular, it is not assumed to be compact as it is in the classical setting via Lasserre relaxations in order to guarantee convergence of the relaxations. However, the crucial point in our setting so far is that Gpµq has to be an ST-polynomial. In the following Section 5 we lay the foundation for the usage of our geometric programming approach also for non-STpolynomials.

But even if Gpµq is not an ST-polynomial, then we can enforce it to be an ST-polynomial in the case of a compact K. This can be achieved by adding a redundant constraint g s`1 " x 2d 1 `. . . `x2d n `c for c P R to the feasible set K. In consequence NewpGpµqq is a 2d-scaled standard simplex and by the previous example our approach coincides with the one in [START_REF]Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming[END_REF]. Hence, the Lasserre relaxation cannot be outperformed in quality anymore. However, our approach can still have the better runtime. It would be interesting to add other redundant inequalities to K such that the corresponding bounds are better than the ones obtained via Lasserre relaxations. Unfortunately, no systematic way is known so far. Furthermore, we consider in this paper numerical methods to certify nonnegativity of polynomials. Often it is desirable to obtain exact solutions, i.e. a symbolic certification. It would be interesting to find symbolic certificates from our provided numerical solution. For SOS polynomials this has been studied e.g. by Peyrl and Parrilo [START_REF] Peyrl | Computing sum of squares decompositions with rational coefficients[END_REF] and by Kaltofen, Li, Yang, and Zhi [START_REF] Kaltofen | Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients[END_REF].

Optimization for Non-ST-Polynomials

The goal of this section is to provide a first approach to tackle optimization problems (both constrained and unconstrained) which cannot be expressed as a single STpolynomial using the methods developed in [START_REF] Iliman | Amoebas, nonnegative polynomials and sums of squares supported on circuits[END_REF][START_REF]Lower bounds for polynomials with simplex newton polytopes based on geometric programming[END_REF] and in Section 3 in this article. A more careful investigation of these general types of nonnegativity problems will be content of a follow-up article.

We start with the case of global nonnegativity for arbitrary polynomials via SONC certificates. We recall the following statement from [IdW16a, Definition 7.1 and Proposition 7.2], which immediately follows from Section 2.1.

Fact 5.1. Let f P Rrxs and assume that there exist SONC polynomials g 1 , . . . , g k and positive real numbers µ 1 , . . . , µ k such that f " ř k i"1 µ i g i . Then f is nonnegative. Of course, if a SONC decomposition exists, then it is not obvious how to find it in general. For ST-polynomials we know that we can find a SONC decomposition via the geometric optimization problem described in Theorem 2.6. Thus, we investigate a general polynomial f P Rrxs supported on a set A Ă N n satisfying p♣q. We denote

f " d ÿ j"0 f αpjq x αpjq `ÿ βP∆pf q f β x β
such that f αpjq x αpjq are monomial squares. By p♣q, V pAq are the vertices of Newpf q and we have V pAq Ď tαp0q, . . . , αpdqu; equality, however, is not required here: tαp0q, . . . , αpdqu can also contain exponents of monomial squares in ∆pAqz∆pf q which are not vertices of convpAq. For simplicity we assume in what follows that the affine span of A is ndimensional. We proceed as follows:

(1) Choose a triangulation T 1 , . . . , T k of exponents αp0q, . . . , αpdq P A corresponding to the monomial squares. (2) Compute the induced covering A 1 , . . . , A k of A given by A i " A X T i for 1 ď i ď k.

(3) Assume that β P ∆pf q Ă A is contained in more than one of the A i 's. Let without loss of generality β P A 1 , . . . , A l with 1 ă l ď k. Then we choose f β,1 , . . . , f β,l P R such that ř l i"1 f β,i " f β and signpf β,i q " signpf β q for all 1 ď i ď l. We proceed analogously for αp0q, . . . , αpdq. (4) Define new polynomials g 1 , . . . , g k such that

g i " ÿ βPA i f β,i x β .
Note that by (1) and (2) the covering A i is a set of integer tuples such that convpA i q is a simplex with even vertices and A i contains no even points corresponding to monomial squares except for the vertices of convpA i q. Thus, by (2)-(4) we see that all g i are STpolynomials, since the signs of the f β,i are identical with the signs of the coefficients of f . Therefore, monomial squares f αpjq x αpjq of f get decomposed into a sum of monomial squares ř k i"1 f αpjq,i x αpjq such that each individual monomial square f αpjq,i x αpjq is a term of exactly one g i . We proceed analogously for the terms f β x β . Additionally, it follows by construction that f " ř k i"1 g i . We apply the GP proposed in Corollary 2.7 on each of the g i with respect to a monomial square f αpjq,i x αpjq , which is a vertex of Newpg i q " convpA i q (not necessarily the same αpjq for every g i ); we denote the minimizer by m i . We make the following observation about these minimizers which was similarly already pointed out in [IdW16a, Section 3]: Lemma 5.2. Let f P Rrxs be a nonnegative circuit polynomial. Let b α x α be a monomial with b α ą 0 and α P p2Zq n . Then b α x α ¨f is also a nonnegative circuit polynomial.

Note particularly that if v P pR ˚qn satisfies f pvq " 0, then pb α x α ¨f qpvq " 0.

Proof. It is easy to see that all conditions for p♣q as well as the conditions (ST1) and (ST2) remain valid for b α x α ¨f . Thus, b α x α ¨f still is a circuit polynomial and since b α x α ě 0 it is also nonnegative. Proposition 5.3. Let f , g 1 , . . . , g k , and m i be as explained above. Assume for i " 1, . . . , k that m i corresponds to the monomial square f αpjq,i x αpj i q with αpj i q P tαp1q, . . . , αpdqu X V pA i q. Then f ´řk i"1 m i x αpj i q is a SONC and hence nonnegative. Thus, the m i provide bounds for the coefficients f αpjq,i for f to be nonnegative. Particularly, if for i " 1, . . . , l with l ď k the exponents αpj i q are the origin, then f αp0q ´řl i"1 m i is a lower bound for f ˚" suptγ P R | f ´γ ě 0u.

Proof. By construction, we know that g i ´mi x αpj i q is a SONC. Thus, f ´řk i"1 m i x αpj i q " ř k i"1 g i ´mi x αpj i q is a SONC, too. The last part follows by the definitions of the m i 's and f ˚.

Note that the decomposition of f into the g i 's is not unique. First, the triangulation in (1) is not unique in general. And, second, the decomposition of the terms in (3) is arbitrary. Note also that there exist several monomial squares which appear in more than one g i , since membership in A i is given by the chosen triangulation and every simplex T 1 intersects at least one other simplex T 2 in an n ´1 dimensional face, which means that A 1 X A 2 contains at least n even elements. As mentioned in the introduction, the problem to identify an optimal triangulation and an optimal decomposition of coefficients will be For the corresponding Newton polytope see Figure 2. First, we split the coefficients equally among the three triangulations such that we obtain g 1 " 0.5 `1.5x 2 1 x 6 2 `2x 2 1 x 2 2 ´x1 x 2 2 , g 2 " 0.5 `1x 6 1 x 2 2 `2x 2 1 x 2 2 ´2x 2 1 x 2 , g 3 " 1.5x 2 1 x 6 2 `1x 6 1 x 2 2 `2x 2 1 x 2 2 ´3x 3 1 x 3 2 .

All three g i have a joint monomial x 2 1 x 2 2 . For all i " 1, 2, 3 we compute the maximal b i ą 0 such that g i ´bi x 2 1 x 2 2 is a nonnegative circuit polynomial. This yields a bound for the coefficient of x 2 1 x 2 2 certifying that f is a SONC and hence nonnegative. We could apply the GP from Corollary 2.7, but since all g i are circuit polynomials we can compute the corresponding circuit numbers symbolically. We obtain with Theorem 2.4: This provides solutions: 2 4 a 3{2 ¨p2 ´b1 q ě 1 ô 3{2 ¨p2 ´b1 q ě 1{16 ô b 1 ď 47{24, . We choose a triangulation tp0, 0q, p0, 2q, p4, 0q, p1, 1qu, tp0, 2q, p2, 4q, p4, 0q, p1, 2q, p2, 3qu, tp2, 4q, p4, 0q, p4, 4q, p3, 3qu. Again, we choose a decomposition of coefficients such that their values split equally. We obtain the following ST-polynomials

Θ g1 p1, 2q " ˆ1{2 1{2 ˙1 2 ¨ˆ3{2 1{4 ˙1 4 ¨ˆ2 ´b1 1{4
g 1 " 1 `1{3 ¨x4 1 `1{2 ¨x2 2 ´x1 x 2 , g 2 " 1{3 ¨x4 1 `1{2 ¨x2 1 x 4 2 `1{2 ¨x2 2 ´x1 x 2 2 ´x2 1 x 3 2 , g 3 " 1{3 ¨x4 1 `1{2 ¨x2 1 x 4 2 `x4 1 x 4 2 ´x3
1 x 3 2 . g 1 and g 3 are circuit polynomials while g 2 contains two negative terms. For the corresponding Newton polytope see Figure 3. Note that only the exponent p4, 0q is contained in the support of all three ST-polynomials. Since p4, 0q is a monomial square which is a vertex of the convex hull of the three support sets, we optimize the corresponding coefficient in g 1 , g 2 and g 3 . Applying the GP from Corollary 2.7 yields optimal values m 1 " 0.0625, m 2 " 4.2867, and m 3 " 0.0625. Since m 2 " 4.2867 ą 1{3 we found no certificate of nonnegativity for f . However, we find a SONC decomposition for f if the coefficient b p4,0q of x 4 1 is at least m 1 `m2 `m3 " 4.412. For this minimal choice of b p4,0q a SONC decomposition is given by 0.063x 4 1 `1 `0.5x Finally, we apply the new method to a constrained optimization problem using the methods developed in Section 3.

  .1) with r ď n, exponents αpjq and β, and coefficients f αpjq , f β , for which the following conditions hold:(ST1): The points αp0q, αp1q, . . . , αprq are affinely independent and equal V pAq. (ST2): Every exponent β P ∆pAq can be written uniquely as β "

  f αpjq ě ř βP∆pf q a β,j for all 1 ď j ď r, (4) f αp0q ´k ě ř

ě

  tpa β , b β q : β P ∆pGquq over the subset of R defined by: p1q ř βP∆pGq a β,j ď Gpµq αpjq for all 1 ď j ď r, b β for every β P ∆pGq with λ pβq 0 " 0, and p3q |Gpµq β | ď b β for every β P ∆pGq with λ pβq 0 ‰ 0.

ě b β , for all β P ∆pGq with λ pβq 0 " 0 ,p3q

 00 tpa β , b β q : β P ∆pGquq over the subset of R defined by: p1q ř βP∆pGq a β,j ď Gpµq αpjq for all 1 ď j ď r, Gpµq β ď b β for all β P ∆pGq, and p4q Gpµq β ď b β for all β P ∆pGq.(3.2)

  The fourth constraint does not appear, because we do not have a Gpµq β .

ě c β for all β P ∆pGq with λ pβq 0 " 0 ,p3q

 00 tpa β , c βq : β P ∆pGquq over the subset of R defined by: p1q ř βP∆pGq a β,j ď Gpµq αpjq for all 1 ď j ď r, Gpµq β ´Gpµq β ď c β for all β P ∆pGq, and p4q Gpµq β ´Gpµq β ď c β for all β P ∆pGq.

  Gpµ ˚qαpjq for all 1 ď j ď r, and p2q ś jPnzpβq ˆaβ,j λ pβq j ˙λpβq j ě |µ k ¨gk,β | for all β P ∆pGq with λ pβq 0 " 0. Then every pa β,1 , . . . , a β,r , b β , µ ˚q with b β ě |µ k ¨gk,β | for all β P ∆pGq is a feasible point of (3.2). Furthermore,

Figure 1 .

 1 Figure 1. The feasible set for the constrained optimization problem in Example 4.2 is the unbounded green (light) area.

Figure 2 .

 2 Figure 2. The Newton polytopes of the polynomials in the Examples 5.4 and 5.5 and their triangulations.

4 a 2

 42 ´b2 ě 1 ô b 2 ď 1, 2 4 a 2{27 a 2 ´b3 ě 1 ô a 2{27 ¨p2 ´b3 q ě 1{4 ô b 3 ď 2 ´?27{p2 ? 2q.

Figure 3 .

 3 Figure 3. The Newton polytopes of the polynomials in the Examples 5.6 and 5.7 and their triangulations.

We discuss a third example which shows that, in the case of global optimization, for the GP/SONC approach it is not necessary to optimize the constant term to obtain a bound for nonnegativity on the coefficients, but that in some cases it can be informative to focus on other vertices of the Newton polytope or on other monomial squares instead.

Finally, we show that if we strengthen the assumptions in Theorem 3.1, then, the output f αp0q ´γsonc of (3.2) equals the output f αp0q ´γ of (2.6) and particularly the bound spf, gq. Theorem 3.5. Assume that for every 1 ď j ď r the form Gpµq αpjq " ´řs i"0 µ i ¨gi,αpjq has exactly one strictly positive term. Furthermore, assume that g i,αp0q ě 0 for all i " 1, . . . , s, and that ∆pAq X A i X A l " H for all 0 ď i ă l ď s. Let γ be the optimal value of the program (2.6). If the optimal value spf, gq " suptGpµq sonc : µ P R s ě0 u is attained for some µ P p0, 8q s , then f αp0q ´γsonc " f αp0q ´γ " spf, gq, where, as before, γ sonc denotes the optimal value of (3.2).

Note that the condition ∆pAq X A i X A l " H is satisfied if the supports of g i and g l differ in all elements that are not vertices of NewpGpµqq.

Proof. The assumption ∆pAq X A i X A l " H for all 0 ď i ă l ď s implies for every β P ∆pGq that Gpµq β " ´řs i"0 µ i ¨gi,β " ´µk ¨gk,β , for some k P r0, ss. Therefore, we have for every β P ∆pGq that

Furthermore, we have g i,αp0q ě 0 for all i " 1, . . . , s by assumption and thus we obtain ř s i"1 µ i g i,αp0q "

. Hence, the two programs (2.6) and (3.2) coincide. By assumption, every Gpµq αpjq consists of exactly one positive term. Therefore, (3.2) is a GP by Theorem 3.1. Considering Theorem 3.1 it suffices to show the inequality f αp0q ´γsonc ě spf, gq for f αp0q ´γsonc " f αp0q ´γ " spf, gq to hold. Let µ ˚P p0, 8q s be such that Gpµ ˚qsonc " spf, gq. By Corollary 2.7 Gpµ ˚qsonc is given by a feasible point pa β,1 , . . . , a β,r q of the program

discussed in a follow-up article.

We provide some examples to show how this generalized approach can be used in practice.

We choose a triangulation tp0, 0q, p2, 6q, p4, 6q, p2, 3q, p3, 5qu, tp0, 0q, p4, 6q, p8, 2q, p2, 3q, p4, 3q, p5, 2q, p7, 2qu.

Here and in what follows the vertices of each simplex are printed in red (bold). For the corresponding Newton polytope see Figure 2. We split the coefficients equally among the two triangulations and obtain two ST-polynomials

Using CVX, we apply the GP from Corollary 2.7 and obtain optimal values m 1 " 0.2121, m 2 " 2.5193, and a SONC decomposition

with ε ă 10 ´10 , i.e. ε is numerically zero. Namely, p2, 3q is located on the segment given by p0, 0q and p4, 6q and thus p2, 6q and p8, 2q have coefficients zero in the convex combinations of the point p2, 3q. Thus, the optimal value f sonc , which provides us a lower bound for f ˚, is f sonc « 6 ´2.731 " 3.269. In comparison, via Lasserre relaxation one obtains an only slightly better optimal value f ˚" 3.8673.

Our GP based bound can be improved significantly via making small changes in the distribution of the coefficients. For example, if one decides not to split the coefficient of the term x 2 1 x 3 2 among g 1 and g 2 equally, but to put the entire weight of the coefficient into g 1 , i.e., g1 " 3 `x2

then this yields to an improved bound fsonc « 3.572.

The next example shows that we can use the approach of this section to take monomial squares into account, which are not vertices of the Newton polytope of the polynomial which we intend to minimize.

We choose a triangulation tp0, 0q, p2, 2q, p2, 6q, p1, 2qu, tp0, 0q, p2, 2q, p6, 2q, p2, 1qu, tp2, 2q, p2, 6q, p6, 2q, p3, 3qu.

Hence, we obtain the following bound for the coefficient of x 2 1 x 2 2 : 6 ´p47{24 `1 `2 ´?27{p4 ? 2qq « 6 ´4.03977468 « 1.96.

A double check with the CVX solver for GPs yields the same value in approximately 0.753 seconds.

We want to compute a bound for f ˚. We choose the same triangulation and the same split of coefficients as before, but now we optimize the constant term in g 1 and g 2 , and we optimize the coefficient of x 2 1 x 6 2 in g 3 . After a runtime of approximately 0.6657 seconds we obtain optimal values 0.0722, 0.3536, and 0.3164. Thus, we found a lower bound for the constant term given by m 1 `m2 « 0.0722 `0.3536 " 0.4268.

The corresponding optimal SONC decomposition is given by

Thus, we obtain a bound for f ˚given by

We make a comparison and optimize f with Lasserre relaxation. This yields an optimal value f sos " f ˚« 0.8383.

Therefore, we want to improve our bound. We keep the triangulation, but we use another distribution of the coefficients among the polynomials g 1 , g 2 and g 3 and define instead

Again, we optimize g1 and g2 with respect to the constant term and g3 with respect to x 2 1 x 6 2 . We obtain optimal values 0.0801, 0.2616, and 0.9912. Thus, we are able to improve our bound for f ˚to fsonc « 1 ´p0.0801 `0.2616q " 0.6583.

The corresponding optimal SONC decomposition is given by 0

Example 5.7. Let f " 1 `x4 `x2 y 4 and g " 1 2 `x2 y ´x6 y 4 ´x3 y 3 . Hence, we obtain Gpµq " p1 ´1 2 µq `x4 `x2 y 4 `µx 6 y 4 ´µx 2 y `µx 3 y 3 . Choosing the triangulation tp0, 0q, p4, 0q, p6, 4q, p2, 1qu, tp0, 0q, p6, 4q, p2, 4q, p3, 3qu, we split the coefficients again, such that their values are equal. For the corresponding Newton polytope see Figure 3. We obtain the ST-polynomials

Therefore, we see that the possible µ values to obtain ST-polynomials are µ P r0, 2q. We optimize both polynomials with respect to the constant term and obtain m 1 " m 2 " 0.

The CVX solver yields NaN as an optimal value, since 0 is not positive. However, it solves the problem and computes values 0 or ε ă 10 ´200 for all variables, such that m 1 " m 2 " 0 follows. Hence, f αp0q ´m˚" 1 ´0 " 1 and because all of the assumptions in Theorem 3.5 are satisfied we know spf, gq " 1.

Checking this optimization problem with Lasserre relaxation, we get f sos " f K " 1, which approves the optimal value. Both, for the SDP and the GP we have runtimes below 1 second. Now, we tackle the same problem, but we multiply every exponent by 10, and we compare the runtimes again. For the GP we obtain the same result and the runtime remains below 1 second. For the SDP we obtain with Gloptipoly f sos " f K " 1 in approximately 5034.5 seconds, i.e. approximately 1.4 hours.

In a third approach we tackle the same problem, but we multiply the originally given exponents by 20. In this case Gloptipoly is not able to handle the given matrices anymore. In comparison, we still have a runtime below 1 second for our GP providing the same bound as before. Now, we also re-compute the example with the software SOSTOOLS [PAV `13], which, in contrast to Gloptipoly, can exploit sparsity patterns. For the original problem size, the runtime is 0.42 seconds, but already in the case that all exponents are multiplied by 10 we have a runtime of 302.7100 seconds, i.e. about 5 minutes.

Finally, we make a last comparison using the software SparsePOP [WKK `09], which especially serves to compute sparse problems based on SOS. Here we start with a runtime of 0.4495 seconds for the original problem. For the case of all exponents of f multiplied by 10 we get a runtime of 81.5438 seconds, i.e. 1.359 minutes.