We present a branch-and-bound algorithm to improve the lower bounds obtained by SONC/SAGE.
The running time is fixed-parameter tractable in the number of variables.
Furthermore, we describe a new heuristic to obtain a candidate for the global minimum of a multivariate polynomial, based on its SONC decomposition.
Applying this approach to thousands of test cases, we mostly obtain small duality gaps.
In particular, we optimally solve the global minimisation problem in about 70% of the investigated cases.

§ INTRODUCTION

Finding the global minimum of a given multivariate polynomial is a well-known problem in optimisation.
This problem has countless applications, see e.g., [16].
Closely connected is the decision problem, whether a given multivariate polynomial is nonnegative.
Already this problem is known to be -hard, as follows from <cit.>.
Therefore, a common approach to certify nonnegativity is to use some sufficient criterion.
The most famous approach is sums of squares (SOS), which dates back to Hilbert.
This approach has been widely applied with success in recent years; see e.g., [4, 18, 16, 17] for an overview.

However, the SOS approach has some serious drawbacks.
In 2006, Blekherman proved that for fixed even degree $d \geq 4$ and $n \to \infty$ almost every nonnegative polynomial is not SOS [3].
Furthermore, deciding whether an $n$-variate polynomial of degree $d$ is SOS translates into an SDP of size $\binom{n+d}{d}$, which quickly becomes infeasible even to state, let alone be solved.
For sparse polynomials, i.e. where the support is significantly smaller than all $\binom{n+d}{d}$ possible monomials, this is particularly critical, as it presents an exponential blow-up.
In this setting, Renegar [23] presented a more efficient algorithm which runs in polynomial space and single exponential time.
Even under the view of parametrised complexity, deciding SOS for sparse polynomial only is in  parametrised by either the degree $d$ or the number of variables $n$.

An alternative certificate of nonnegativity is based on sums of nonnegative circuit polynomials (SONC), introduced by Iliman and de Wolff [14].
In a recent paper [24], we presented an algorithmic approach to obtain lower bounds via SONC, including the software POEM (Effective Methods in Polynomial Optimisation) [25].
This method computes a lower bound by solving a geometric programme.
While this approach fared well in experiments, it had some major drawbacks.

* It did not include a method to find any (local) minimiser, so we could not tell the optimality gap.

* To find the bound via SONC, we had to perform a relaxation, that allowed to restrict on the positive orthant, which possibly worsened the results.

* The method could only find some lower bound and not even the best bound theoretically obtainable via SONC.

An important improvement on the third issue came by Chandrasekaran and Shah by using sums of arithmetic geometric mean exponentials (SAGE), using relative entropy programmes (REP) [5, 6].
However, their variable substitution corresponds to a restriction on the positive orthant as well, but there they efficiently compute the best bound obtainable by SAGE.

In this contribution, we address the first two of the above issues.
First, in <ref>, we generalise [14] to explicitly compute minimisers for arbitrary circuit polynomials.
This serves as base for our heuristic to compute the minimum of the given polynomial in <Ref>.
Second, we present a branch-and-bound approach, where we branch over the signs on the variables in <Ref>.
This eventually gives us additional information for the sign of the terms, which allows to improve the lower bounds.
The running time may increase by a factor $2^n$, which is fixed-parameter tractable, so it is still considered efficient in parametrised complexity.
In fact, we only have to perform our initial algorithm on some of the $2^n$ orthants.
In <Ref> we suggest an alternative to the branch-and-bound, where we determine these orthants and compute a lower bound for each one, which can easily be done in parallel.
The time to find these orthants is negligible to the overall time.

We implemented these algorithms and included them in our software POEM.
In addition, we perform a large scale experiment on a subset of the examples from [24] and present the evaluation in <Ref>.
These polynomials have up to 8 variables, degree 60 and 50 terms.
In total, our experiment contains  instances with a total running time of more than 8 days.
Overall, we observe a significant improvement of the lower bounds and about 70% of our instances we solved optimally.

§.§ Acknowledgements

We thank Timo de Wolff for his suggestion to work on a branch-and-bound approach for SONC.
Further thanks go to Helena Müller for her improved computation of minimisers of circuit polynomials.

§ PRELIMINARIES

In this section we introduce our basic notation, sums of squares, sums of nonnegative circuit polynomials, and geometric programmes.

§.§ Representing Sparse Polynomials

Throughout the paper, we use bold letters for vectors (small) and matrices (capital), e.g., $\struc{\Vector{x}}=(x_1,\ldots,x_n) \in \mathds R^n$.
Let $\struc{\mathds R_{\geq 0}}$ and $\struc{\mathds R_{> 0}}$ denote the set of nonnegative and positive real numbers, respectively.
Furthermore, let $\mathds R[\Vector{x}] = \mathds R[x_1,\ldots,x_n]$ be the ring of real $n$-variate polynomials.
We denote the set of all $n$-variate polynomials of degree less than or equal to $2d$ by $\struc{\mathds R[\Vector{x}]_{n,2d}}$.
For $p \in \mathds R[\Vector{x}]$ we denote the total degree of $p$ by $\struc{\deg(p)}$.

We investigate sparse polynomials $p \in \mathds R[\Vector{x}]$ supported on a finite set $\struc{A} \subset \mathds N^n$; we write $\struc{\support{p}}$ if a clarification is necessary.
Thus, $p$ is of the form $\struc{p(\Vector{x})} = \sum_{\Vector{\alpha} \in A}^{} b_{\Vector{\alpha}}\Vector{x}^{\Vector{\alpha}}$ with $\struc{b_{\Vector{\alpha}}} \in \mathds R\setminus\{0\}$ and $\struc{\Vector{x}^{\Vector{\alpha}}} = x_1^{\alpha_1} \cdots x_n^{\alpha_n}$.
While a multivariate polynomial may have up to $\binom{n+d}{d}$ terms, sparsity means $|A| \ll \binom{n+d}{d}$.
Unless stated differently, we follow the convention $\struc{t} = |A|$.
The support of $p$ can be expressed as an $n \times t$ matrix, which we denote by $\struc{\Matrix{A}}$, such that the $j$-th column of $\Matrix{A}$ is $\Vector{\alpha(j)}$.
Hence, $p$ is uniquely described by the pair $(\Matrix{A},\Vector{b})$, written $p = \struc{\polynomial{\Matrix{A}}{\Vector{b}}}$.

The Newton polytope of $p$, denoted $\newton{p} = \operatorname{chull}(\support{})$, is the convex hull of all exponent vectors.
A lattice point $\Vector{\alpha}$ is called even if it is in $(2\mathds N)^n$ and a term $b_{\Vector{\alpha}}\Vector{x}^{\Vector{\alpha}}$ is called a monomial square if $b_{\Vector{\alpha}} > 0$ and $\Vector{\alpha}$ even.
We define

\begin{align*}
\struc{\monoSquares{p}} = \left\{\Vector{\alpha} \in \support{p} : \Vector{\alpha} \in (2\mathds N)^n, b_{\Vector{\alpha}} > 0\right\}
\end{align*}

as the set of monomial squares in the support of $p$.
Moreover, we use the notation $\struc{\nonSquares{p}} = \support{p} \setminus \monoSquares{p}$ for all elements of the support of $p$, which are not a monomial square.

§.§ Sums of Nonnegative Circuit Polynomials

We introduce the fundamental facts of SONC polynomials, which we use in this article.
SONCs are constructed by circuit polynomials; which were first introduced in [14]:

A circuit polynomial $p = \polynomial{\Matrix{A}}{\Vector{b}} \in \mathds R[\Vector{x}]$ is of the form

\begin{align}
\struc{p(\Vector{x})} & = \sum_{j=0}^r b_{\Vector{\alpha}(j)} \Vector{x}^{\Vector{\alpha}(j)} + b_{\Vector{\beta}} \Vector{x}^{\Vector{\beta}},
\label{Equ:CircuitPolynomial}
\end{align}

with $0 \leq \struc{r} \leq n$, coefficients $\struc{b_{\Vector{\alpha}(j)}} \in \mathds R_{> 0}$, $\struc{b_{\Vector{\beta}}} \in \mathds R$, exponents $\struc{\Vector{\alpha}(j)} \in (2\mathds Z)^n$, $\struc{\Vector{\beta}} \in \mathds Z^n$, such that the following condition holds:
There exist unique, positive barycentric coordinates $\lambda_j$ relative to the $\Vector{\alpha}(j)$ with $j=0,\ldots,r$ satisfying

\begin{align}
\label{equ:BarycentricCoordinates}
\Vector{\beta} &= \sum_{j=0}^r \lambda_j \Vector{\alpha}(j) \ \text{ with } \ \lambda_j > 0 \ \text{ and } \ \sum_{j=0}^r \lambda_j = 1.
\end{align}

For every circuit polynomial $p$ we define the corresponding circuit number as

\begin{align*}
\struc{\Theta_p} &= \prod_{j = 0}^r \left(\frac{b_{\Vector{\alpha}(j)}}{\lambda_j}\right)^{\lambda_j}.
\qedhere
\end{align*}

Condition (<ref>) implies that $\Matrix{A}(p)$ forms a minimal affine dependent set.
Those sets are called circuits, see e.g., [22].
More specifically, Condition (<ref>) yields that $\newton{p}$ is a simplex with even vertices $\Vector{\alpha}(0), \Vector{\alpha}(1),\ldots,\Vector{\alpha}(r)$ and that the exponent $\Vector{\beta}$ is in the relative interior of $\newton{p}$.
Therefore, we call the terms $p_{\Vector{\alpha}(0)} \Vector{x}^{\Vector{\alpha}(0)},\ldots,p_{\Vector{\alpha}(r)} \Vector{x}^{\Vector{\alpha}(r)}$ the outer terms and $p_{\Vector{\beta}} \Vector{x}^{\Vector{\beta}}$ the inner term of $p$.

Circuit polynomials are proper building blocks for nonnegativity certificates since the circuit number alone determines whether they are nonnegative.

Let $p$ be a circuit polynomial of the form (<ref>). Then $p$ is nonnegative if and only if:

* $p$ is a sum of monomial squares, or

* the coefficient $b_{\Vector{\beta}}$ of the inner term of $p$ satisfies $|b_{\Vector{\beta}}| \leq \Theta_p$.

To compute $\Theta_p$, we solve a system of linear equations.
Hence, we have an easily checked arithmetic condition for the nonnegativity of a circuit polynomial.
These nonnegative circuit polynomials now generate the cone, we use as our certificate of nonnegativity.

We define for every $n,d \in \mathds N$ the set of sums of nonnegative circuit polynomials (SONC) in $n$ variables of degree $2d$ as

\begin{align*}
\struc{C_{n,2d}} = \left\{f \in \mathds R[\Vector{x}]_{n,2d} : f = \sum_{\text{finite}} p_i, \quad p_i \text{ is a nonnegative circuit polynomial} \right\}.
\tag*{\qedhere}
\end{align*}

We denote by  both the set of SONC polynomials and the property of a polynomial to be a sum of nonnegative circuit polynomials.

For further details about the SONC cone see [10, 14, 9].

§.§ Lower Bounds via SONC

Given an arbitrary polynomial $p$, we apply this approach to compute a lower bound for its values.
If we find some $\boundSONC \in \mathds R$ such that $p-\boundSONC \in \SONC$, then we have $p(x) \geq \boundSONC$ for all $x\in\mathds R^n$.
Note, that in general, this is not the infimum.

We shortly describe our algorithm from [24].
Further details can be found there.

Every monomial, that is not a square, must appear as the inner term of a circuit polynomial.
This corresponds to relaxing $p$ to the polynomial $\relaxPoly{p}$, where every non-square is equipped with a negative sign.
Furthermore, we now can restrict ourselves to the positive orthant, since $\relaxPoly{p}$ attains its minimum there.
For simplicity, we assume $p = \relaxPoly{p}$ when computing lower bounds for a polynomial.

Next, we determine the circuits involved in the decomposition.
For each $\Vector{\beta} \in \nonSquares{p}$, we write it as a convex combination of monomial squares, which means we find a solution of the LP

\begin{align*}
\sum_{\Vector{\alpha} \in \monoSquares{p}} \lambda_{\Vector{\alpha}}\Vector{\alpha} &= \Vector{\beta} &
\sum_{\Vector{\alpha} \in \monoSquares{p}} \lambda_{\Vector{\alpha}} &= 1 &
\lambda_{\Vector{\alpha}} &\geq 0 \text{ for all $\Vector{\alpha} \in \monoSquares{p}$}
\end{align*}

If necessary, we further eliminate some if the $\lambda_{\Vector{\alpha}}$ until $\cover^{\Vector{\beta}} := \left\{\Vector{\alpha} : \lambda_{\Vector{\alpha}} > 0\right\}\cup\{\Vector{\beta}\}$ forms a circuit.
This yields the covering $\cover := \left\{\cover^{\Vector{\beta}} : \Vector{\beta} \in \nonSquares{p}\right\}$.
Finally, we solve the following Geometric Programme:

b_0 - ∑_β∈p X_β, 0
∑_β∈p X_β,α≤b_αα ∈p, α ≠0
∏_α∈^β (X_β,α/λ^β_α)^λ^β_α= |b_β|β ∈p
X_β, α≥0α ∈p, β ∈p.

Then we obtain our lower bound $\boundSONC$.

For simplicity, we restricted to the case, where every non-square occurs in exactly one circuit.
Therefore, the size of this covering is bounded by $|\cover|\in\mathcal O(t)$.
If some $\Vector{\beta}$ occurs in multiple circuits, the coefficient $b_{\Vector{\beta}}$ has to be distributed among them and the second set of constraints has to be adjusted accordingly.
In the original approach, we checked for every circuit, which other exponents of non-squares are included in its Newton polytope and added these circuit as well.
This extended the size of the covering to $|\cover| \in \mathcal O(t^2)$.
In either case, the size of <ref> is polynomially bounded in the input size.

§.§ Computing Minima

While the previous section describes an algorithm to compute lower bounds for multivariate polynomials via SONC, we do not have upper bounds for the minimum, so we do not have any guarantees for the quality of our bounds.
While every local minimum gives such a bound, we can use the SONC decomposition for a heuristic to find a good (local) minimiser.
Müller investigated this idea in further detail in [21] and in this section, we present the main ideas of her work.
In short, given a SONC decomposition, we explicitly compute the minimiser of each circuit polynomial.
Then we take the barycentre of these minimisers and use it as starting point for some local minimisation method.

Müller's experimental results were already promising.
We re-implemented the approach and include it in our software POEM.
See <ref> for the experimental results.

Generalising work from Iliman and de Wolff [14], Müller shows the following theorem.
For the reader's convenience, we also provide the proof here.

For a circuit polynomial $p$ with $\alpha(0) = 0$ and $b_{\Vector{\beta}}<0$, let $\Vector{s}$ be the vector satisfying the linear equation system

\begin{align}
\langle \Vector{s}, \Vector{\alpha}(j) - \Vector {\beta}\rangle &= \log\left(- \frac{\lambda_j}{b_{\Vector{\alpha}(j)}} \cdot b_{\Vector{\beta}}\right)
&\text{for all $1\leq j\leq n$.}
\label{equation:condition_min}
\end{align}

Then $e^{\Vector{s}}$ is the global minimiser of $p$.

Condition <ref> implies $e^{\langle\Vector{s},\Vector{\alpha}(j)\rangle} = -\frac{\lambda_j}{b_{\Vector{\alpha}(j)}} b_{\Vector{\beta}} \cdot e^{\langle\Vector{s},\Vector{\beta}\rangle}$.
Evaluating the shifted partial derivative at $e^{\Vector{s}}$ yields

\begin{align*}
\left(x_j\frac{\partial p}{\partial x_j}\right)\left(e^{\Vector{s}}\right)
&= \sum_{k=1}^n b_{\Vector{\alpha}(k)} \Vector{\alpha}(k)_j e^{\langle \Vector{s}, \Vector{\alpha}(k)\rangle} + b_{\Vector{\beta}} \beta_j e^{\langle\Vector{s},\Vector{\beta}\rangle}
= -\sum_{k=1}^n \lambda_k b_{\Vector{\beta}} \Vector{\alpha}(k)_j e^{\langle \Vector{s}, \Vector{\beta}\rangle} + b_{\Vector{\beta}} \beta_j e^{\langle\Vector{s},\Vector{\beta}\rangle} \\
&= b_{\Vector{\beta}} e^{\langle \Vector{s}, \Vector{\beta}\rangle} \left(-\sum_{k=1}^n \lambda_k \Vector{\alpha}(k)_j + \beta_j\right)
= 0
\end{align*}

Note that the 0-th summand vanished, since $\Vector{\alpha}(0)=\Vector{0}$ and the final sum vanishes, because

\begin{align*}
\Vector{\beta} = \sum_{k=0}^n \lambda_k \Vector{\alpha}(k) = \sum_{k=1}^n \lambda_k \Vector{\alpha}(k)
\end{align*}

Hence, $e^{\Vector{s}}$ is a local minimiser of $p$.
By <cit.>, it is the unique minimum in the positive orthant and since $b_{\Vector{\beta}}<0$, the global minimum is attained in the positive orthant.

Since $\Vector{\beta}$ lies in the interior of the Newton polytope, the vectors $\Vector{\beta}, \Vector{\alpha}(1), \ldots, \Vector{\alpha}(n)$ span a simplex as well.
Hence, the vectors $\Vector{\alpha}(j)-\Vector{\beta}$ are linearly independent.
Therefore, <ref> has a unique solution, so it is justified to speak of the solution $\Vector{s}$.
For $b_{\Vector{\beta}}>0$, the inner term either is a monomial square, or has an odd power.
If $b_{\Vector{\beta}}\Vector{x}^{\Vector{\beta}}$ is a monomial square, the minimiser trivially is $\Vector{0}$.
Otherwise, let $\beta_i$ be odd and put $\hat{p} = p(x_1,\ldots,-x_i,\ldots,x_n)$.
Then $\hat{p}$ satisfies the conditions of <ref> and has the same infimum.

Now let $\relaxPoly{p} = p_1+\ldots+p_{\coverLength}$ be the SONC decomposition of the relaxation of $p$.
Let $\minimum_i = e^{\Vector{s}_i}$ be the respective minima of the $p_i$ according to <ref>.
Then we use the barycentre $\overline{\minimum} := \frac{1}{\coverLength}\sum_{i=1}^{\coverLength} \minimum_i$ as starting point for a gradient method to find a local minimum of $\relaxPoly{p}$, which we denote $\minimum$.
The expectation is, that $\overline{\minimum}$ often lies sufficiently close to the global minimum of $\relaxPoly{p}$.
In these cases, this local minimum will also be the global minimum of $\relaxPoly{p}$.
If $p \neq \relaxPoly{p}$, we now call a gradient method on $p$ with $\minimum$ as starting point, to obtain our final result.

The algorithm to compute (local) minima via SONC in polynomial time works as follows.
For given accuracy $\varepsilon$, the running time is polynomial in the input size and $\frac{1}{\varepsilon}$.
[1]
$p$ – Polynomial
$\minimum$ – Local minimum of $p$
compute SONC-decomposition $\relaxPoly{p} = p_1+\ldots+p_{\coverLength} + \variableStyle{const}$
set $\Vector{s}_i$ as solution of <ref> for $p_i$
$\minimum_i \gets e^{\Vector{s}_i}$ minimum of circuit-polynomial $p_i$
$\minimum \gets \frac{1}{\coverLength}\sum_{i=1}^{\coverLength} \minimum_i$
$\minimum \gets \gradientDescent{\relaxPoly{p}, \minimum}$ local minimum of $\relaxPoly{p}$

$\minimum \gets \gradientDescent{p, \minimum}$ local minimum of $p$

As observed in <ref>, we have $\coverLength \in\mathcal O(t^2)$,
For each minimiser, we have to solve a linear equation system, which can be done in $\mathcal O(n^3)$.
For the local minimum, we can use nonlinear gradient descent, which has quadratic convergence [12].
Hence, we have an overall polynomial running time.

§.§ SAGE Polynomials

In [5] Chandrasekaran and Shah introduce another certificate for nonnegativity, based on “sums of arithmetic-geometric-mean exponentials” (SAGE).
They also form a class of sparse polynomials, whose nonnegativity can also easily be verified.
Both computing this certificate and decomposing a polynomial as SAGE (if possible) can be done by a relative entropy programme.
Like for SONC, the support of the certificate of nonnegativity is exactly the support of the input polynomial, which also makes this approach well-suited, to obtain lower bounds for sparse polynomials.
In fact, both approaches describe the same set of polynomials [19].

A signomial is an expression of the form

\begin{align*}
p = \sum_{j=1}^t b_j \cdot \exp\left(\langle\Vector{\alpha}(j), \Vector{x}\rangle\right)
\end{align*}

with $b_j\in\mathds R$ and $\Vector{\alpha}(j)\in\mathds N^n$.
Via logarithmic transformation, signomials correspond to polynomials, whose domain is restricted to $\mathds R_+^n$.

An arithmetic-geometric-mean-exponential (AGE) is a nonnegative signomial with at most one negative coefficient.
The name comes from the fact that its nonnegativity can be verified via arithmetic-geometric-mean inequality.
The sums of AGE polynomials (SAGE) form a convex cone.
Testing membership in this cone can be done by solving a relative entropy programme (REP), which is a type of convex optimisation problem.

The relative entropy function is defined for $\Vector{\lambda}, \Vector{v} \in \mathds R_+^t$ by $\struc{D(\Vector{\lambda},\Vector{v})} := \sum_{j=1}^t \lambda_j \log \frac{\lambda_j}{v_j}$.
Furthermore, let $\Vector{v}_{\setminus i}\in\mathds R^{n-1}$ denote the vector derived from $\Vector{v}\in\mathds R^{n}$, where the entry at index $i$ was removed and for a matrix $\Matrix{X}$ let $\Vector{X}^{(j)}$
Then from <cit.>, we have the following characterisation.

A signomial $p=\sum_{j=1}^t b_j \exp \, (\langle \Vector{\alpha}(j), \Vector{x}\rangle)$ lies in SAGE if and only if there are $\Matrix{X}$, $\Matrix{\lambda} \in \mathds R^{t\times t}$ satisfying the following conditions:

\begin{align}
\label{problem:SAGE-feas}
\begin{aligned}
\sum_{i=1}^t \Vector{X}^{(i)} = \Vector{b} \,, \quad
\sum_{j=1}^t \Vector{\alpha}(j) \Vector{\lambda}_j^{(i)} = \Vector{0} \,, \quad
-\Vector{1} \cdot \Vector{\lambda}_{\setminus i}^{(i)} = \lambda_i^{(i)} \,, \\
\Vector{X}_{\setminus i}^{(i)},	\Vector{\lambda}_{\setminus i}^{(i)} \geq \Vector{0} \,, \quad
D\left(\Vector{\lambda}_{\setminus i}^{(i)}, e\Vector{X}_{\setminus i}^{(i)}\right) \leq X_i^{(i)}
\,, \quad i=1,\dots,t \,.
\end{aligned}
\tag{SAGE-feas}
\end{align}

One way to obtain lower bounds of a signomial $f$ is to solve the following REP:

\begin{align}
\label{problem:SAGE}
\struc{p_{\text{SAGE}}} := \sup \{ b \in \mathds R: p - b \text{ is SAGE}\}.
\tag{SAGE}
\end{align}

The constraints of <ref> correspond to <ref>, after replacing $b_0$ by $b_0 - C$.

The second type of constraints has a size in $\mathcal O(n)$ but by restricting to the ambient space, we may assume $n\leq t$.
So the overall size of both the decision and the optimisation problem lies in $\mathcal O(t^2)$.
Most notably, it is independent of the degree $d$.
Recall, that we investigate sparse polynomials, which means $t \ll \binom{n+d}{d}$.

§.§ Parametrised Complexity

When solving a problem, one mainly is interested in efficient algorithms, which usually means a running time polynomial in the input length.
However, even a theoretically exponential time algorithm might be practically feasible, if the exponential part is sufficiently small.
These considerations have led to a whole hierarchy of complexity classes, but in this paper, we are only interested in the class of fixed-parameter tractable problems ().
See [13] for more details.

A parametrised problem is a pair $(P,\kappa)$ such that $P\subseteq\Sigma^*$ is a language and $\struc{\kappa}:\Sigma^*\to\mathds N$ is called the parameter.

The class  is the class of all parametrised problems $(P,\kappa)$, where there exists a computable function $f:\mathds N\to\mathds N$ and a constant $c$, such that $x$ can be decided in time $\mathcal O(f(\kappa(x)) \cdot |x|^c)$.

Note, that increasing the parameter here only affects a factor of the running time, but not the exponent $c$.
So for moderate values of the parameter, these problems can often be solved in practice.

In contrast, the often found description “polynomial time for constant parameter” describes the class $\struc{\XP}$.
More formally, it contains all problems such that there is a computable function $g:\mathds N\to\mathds N$ such that the problem can be solved in $\mathcal O\left(|x|^{g(\kappa(x))}\right)$.
We have strict containment $\FPT\subset\XP$, see e.g. <cit.>.

§ BRANCH AND BOUND

In our previous paper [24], we described a method to obtain lower bounds for polynomials, as also given in <ref>.
As initial step, we relaxed the polynomial by giving every possibly negative term a negative sign and then restricting ourselves to the positive orthant.
However, this is overly pessimistic, as can be seen in the following example.

Let $p=x^4+x^3-x+1$, which has minimum $\approx 0.682$.
This polynomial is relaxed to $\relaxPoly{p} = x^4-x^3-x+1$, which has minimum $0$.

[->] (0,-0.5) – (0,3);
[->] (-2,0) – (2,0);
plot[domain=-1:1] (,***+ **- + 1);
[dashed] plot[domain=-1.2:-1] (,***+ **- + 1);
[dashed] plot[domain=1:1.1] (,***+ **- + 1);
[red] plot[domain=-0.8:1.5] (,***- **- + 1);
[red, dashed] plot[domain=-0.9:-0.8] (,***- **- + 1);
[red, dashed] plot[domain=1.5:1.6] (,***- **- + 1);
[-] (1,-0.1) – (1,0.1);
[-] (-1,-0.1) – (-1,0.1);
[-] (-0.1,1) – (0.1,1);
[-] (-0.1,2) – (0.1,2);

Graphs of $p$ (black) and $\relaxPoly{p}$ (red)

To overcome this problem, we propose a branch-and-bound algorithm, where we branch over the signs of the variables.
By fixing a sign for a variable, some terms with an odd power are then known to be positive, so they can be regarded as monomial squares.
Hence, we do not have to cancel out their negative weight, but in addition gain new positive weights to cancel out the remaining negative terms.

To denote our restrictions on the signs of the variables, we introduce sign cones.

Let $\Vector{s}\in\{-1,0,1\}^n$.
We call $\Vector{s}$ a sign vector, where $-1,0,1$ represents negative/unknown/positive sign, respectively, and define the corresponding sign cone as

\begin{align*}
\struc{\signCone{s}} := \left\{\Vector{x}\in\mathds R^n: x_i\cdot s_i \geq 0 \text{ for all } i=1,\ldots,n\right\}.
\end{align*}

For some sign vector $\Vector{s}$, the positive points are given by

\begin{align*}
\posPoints{p}{\Vector{s}} = \left\{\Vector{\alpha} \in \support{p} : \operatorname{sgn}(\Vector{\alpha}) \cdot \prod_{i=1}^n s_i^{\Vector{\alpha}_i \bmod 2} = 1\right\}
\end{align*}

with the convention $0^0=1$.
The negative points are $\negPoints{p}{s} := \support{p} \setminus\posPoints{p}{s}$.
The corresponding positive and negative terms are the terms $b_{\Vector{\alpha}}\Vector{x}^{\Vector{\alpha}}$ for $\Vector{\alpha}\in \posPoints{p}{s}$ and $\Vector{\alpha}\in \negPoints{p}{s}$, respectively.
The whole polynomial restricted to the domain $\signCone{s}$ we denote by $\struc{p_{\Vector{s}}}$.

In this notation $p = p_{\Vector{0}}$.
Clearly, $\monoSquares{p} \subseteq \posPoints{p}{s}$ for any sign vector $\Vector{s}$.
So we obtain the new relaxation

\begin{align*}
\struc{\relaxPoly{p}_{\Vector{s}}} = \sum_{\Vector{\alpha} \in \posPoints{p}{s}} b_{\Vector{\alpha}}\Vector{x}^{\Vector{\alpha}} - \sum_{\Vector{\beta} \in \negPoints{p}{s}} \left|b_{\Vector{\beta}}\right| x^{\Vector{\beta}}.
\end{align*}

For $\monoSquares{p} \neq \posPoints{p}{s}$, this is an improvement of the original relaxation.
Note, that by fixing more signs, the set of positive terms may only grow.

Our branch-and-bound algorithm creates a binary search tree, where each node has a sign vector and a flag, whether it is active or not.
Furthermore, we store the best known lower bound and the lowest found function value over the corresponding sign cone.
For simplicity, we identify the nodes with their sign vectors and denote the lower bounds as $\lowerBound{p_{\Vector{s}}}$.

Initially, the tree consists only of the root node, which is active and has sign vector $\Vector{s} = \Vector{0}$.
So it corresponds to $\signCone{s}=\mathds R^n$ as the domain and we compute bounds as in <Ref>.
In each iteration, we then pick some active node, which becomes inactive.
If it satisfies any bounding criterion, we continue with the next iteration.
Otherwise, we determine some index $i$ with undetermined sign $s_i=0$ and create two new child nodes for $\Vector{s}$, where we update $\Vector{s}$ with $s_i=\pm 1$.
We compute lower bounds and minimisers for both nodes and mark them as active.
Then we continue with the next iteration.

We have the following branch-and-bound blueprint.
[1]
$p$ – Polynomial
p – Lower bound of $p$
run SONC, SAGE on $p$
$\variableStyle{active} := \{p\}$
$\variableStyle{active} \neq \emptyset$
pick some $p_{\Vector{s}} \in \variableStyle{active}$

$\variableStyle{active} = \variableStyle{active} \setminus\{p_{\Vector{s}}\}$
$p_{\Vector{s}}$ does not satisfy bounding criterion

pick index $i$ with $s_i=0$

set $\Vector{s}^+$ as $\Vector{s}$ with $s_i=1$ and $\Vector{s}^-$ as $\Vector{s}$ with $s_i=-1$
compute SONC/SAGE bounds for $p_{\Vector{s}^+}$ and $p_{\Vector{s}^-}$
$\variableStyle{active} = \variableStyle{active} \cup \{p_{\Vector{s}^+},p_{\Vector{s}^-}\}$

Termination follows immediately, since there are at most $2^{n+1}-1$ polynomials involved, and once a polynomial is removed from $\variableStyle{active}$, it is never inserted again.

To investigate the algorithm, let $\subtree{\Vector{s}}$ denote the current subtree, with root $\Vector{s}$.
This means, we may regard the search tree at any intermediate state, and the root of this subtree need not correspond to all of $\mathds R^n$.
First we observe the following.

Each node has a bound at least as good as its parent.
From the mathematical side, this is clear since we restrict the domain.
But also from the algorithmic side, the certificate of the parent is also a certificate for the node itself.

With this observation, we can see how the search tree yields a global bound for a polynomial $p$.

A lower bound for the polynomial $p_{\Vector{s}}$ is given by

\begin{align*}
\inf p &\geq \min\left\{\max\left\{\lowerBound{v}: v\in P\right\}: P\text{ is maximal path in $\subtree{\Vector{s}}$}\right\}
= \min\left\{\lowerBound{l} : l \text{ is leaf in }\subtree{\Vector{s}}\right\}
\end{align*}

for any intermediate state of the search tree $\subtree{\Vector{s}}$.
In particular, we get a lower bound for $p$ from the tree $\subtree{\Vector{0}}$.

Since any node has lower bound at least as good as its parent, the maximum of any path is attained at its endpoint, which is a leaf of $\subtree{\Vector{s}}$.
The sign cones, represented by the leaves, partition the whole space $\signCone{s}$.
Put $M:=\min\left\{\lowerBound{l} : l \text{ is leaf in }\subtree{\Vector{s}}\right\}$.
Let $\Vector{s}_1,\ldots,\Vector{s}_r$ be the leaves of $\subtree{\Vector{s}}$.
Then, in each of these sign cones, we have $\inf p_{\Vector{s}}\geq \lowerBound{p_{\Vector{s}_i}}\geq M$.
Hence, globally we have $\inf p_{\Vector{s}}\geq M$.

However, the method in <ref> so far only presents a blueprint.
The following steps still have to be made more precise.

* Which node $\Vector{s}$ do we pick in <ref>?

* What are our bounding criteria in <ref>?

* Which index $i$ do we choose in <ref>?

We address these issues in the following subsections.

§.§ Bounding Criteria

A crucial part in a branch-and-bound algorithm is to have efficient bounds.
So we need some easily checkable criteria, which allow us to cut off a branch of the search tree.

Let $\Vector{c}$ be our current node.
We define the following criteria for cutting off branches.

If we have found some argument $\Vector{x}$ such that $p(\Vector{x})\leq \lowerBound{p_{\Vector{c}}}$, then we cut off the branch at $\Vector{c}$.

If there is some leaf $\Vector{s} \in \{-1,1\}^n$, i.e. leaf $\Vector{s}$ lies at depth $n$, with $\lowerBound{p_{\Vector{s}}} \leq \lowerBound{p_{\Vector{c}}}$, then we cut off the branch at $\Vector{c}$.

The above cut criteria are correct.

Since both criteria are independent, we show their correctness separately.

According to <ref>, our lower bound is

\begin{align*}
M:=\min\left\{\lowerBound{p_{\Vector{s}}} : \Vector{s} \text{ is leaf in } T\right\}.
\end{align*}

As observed before, in any state, the sign cones cover $\mathds R^n$, so let $\Vector{x} \in \signCone{s}$ for some $\Vector{s}$.
Then, of course, $\lowerBound{p_{\Vector{s}}} \leq p(\Vector{x})$.
Hence, branching $\Vector{c}$ any further, would only increase $\lowerBound{p_{\Vector{c}}}$ but not affect the minimum.
So we can cut off the branch at $\Vector{c}$.

Since $\Vector{s} \in \{-1,1\}^n$, we cannot branch it any further, so its bound will not improve.
Therefore, $M\leq \lowerBound{p_{\Vector{s}}}$.
Again, increasing $\lowerBound{p_{\Vector{c}}}$ will then not affect the minimum, so can cut off the branch at $\Vector{c}$.

Both criteria can easily be checked.
We separately store the lowest value, we have found, and the lowest value of some leaf $\lowerBound{p_{\Vector{s}}}$ for $\Vector{s}\in\{-1,1\}^n$.
(As long as we have not processed any such node, this value is $\infty$.)
Then both <ref> and <ref> are single comparisons, which take $\mathcal O(1)$ time.

§.§ Choice of Branching Node

Another problem to be addressed is the choice of the node, on which to branch in <ref>.

With regard to the quality of the solution, the best choice is to choose the node with the smallest lower bound.
As we have seen in <ref>, the final bound is the smallest bound of any leaf.
Hence, if we do not improve this worst bound, the final bound will not improve.
The main disadvantage is, that the number of active leaves can grow exponentially, so this requires space exponential in $n$.

If memory is an issue, then the tree should be traversed in a depth-first-search.
With this strategy, we ensure $|\variableStyle{active}|\leq n+1$, so the computation runs in polynomial space.
The significant disadvantage is the higher running time, because we compute more nodes than with the previous strategy.

§.§ Practical Improvements

If we choose the node with the worst bound for further branching, then the criterion <ref> never applies.
However, for numerical computations, we use a relaxed version.
Let $p(\Vector{m})$ be the lowest function value we found so far and let $\varepsilon$ be some given accuracy.
If for the current node $\Vector{c}$ we have $\lowerBound{p_{\Vector{c}}} \geq p(\Vector{m}) + \varepsilon$, we stop the whole computation, because we already have solved the problem up to accuracy $\varepsilon$.
To use this criterion, we integrate the computation of local minima via  into the branch-and-bound method.
The global minimum is also more likely to be found in the sign cone with the worst lower bound.
So, whenever we compute bounds for a sign cone, we also search for a  local minimiser via <ref>.
However, the minima we compute for the circuit polynomials always lie in the positive orthant.
Hence, our starting point $\relaxPoly{\minimum}$ for the minimisation lies in the positive orthant as well.
To comply with our orthant restriction, we flip some signs of our starting point and define

\begin{align*}
\relaxPoly{\minimum}' = \begin{cases}
-\relaxPoly{m}_i &: s_i = -1 \\
\relaxPoly{m}_i &: \text{else}
\end{cases}.
\end{align*}

as use $\relaxPoly{\minimum}'$ as our starting point in <ref>, where we run gradient descent for $p$.

Furthermore, we adjust <ref> as follows.
Once we reach a node $\Vector{s}\in\{-1,1\}^n$, i.e. all signs are known we stop the whole algorithm.
We cannot improve this node by further branching, since by our choice of $\Vector{s}$ and <ref>, we already have $\lowerBound{p} = \lowerBound{p_{\Vector{s}}}$.
Hence, we cannot improve the bound of $p$ by our approach any more.

All combined, this yields the following algorithm.

We have the following branch-and-bound algorithm, whose running time is fixed parameter tractable in the number of variables $n$.
[1]
$p$ – Polynomial
p – Lower bound of $p$
run SONC, SAGE on $p$
$\variableStyle{min} \gets \operatorname{SONC-Min}(p)$
$\variableStyle{active} \gets \{p\}$
$\variableStyle{active} \neq \emptyset$
$\Vector{s} \gets \operatorname{argmin} \left\{ \lowerBound{p_{\Vector{s}}} : \Vector{s} \in \{-1,0,1\}^n, p_{\Vector{s}} \in \variableStyle{active} \right\}$

cone with worst bound
$\variableStyle{active} \gets \variableStyle{active} \setminus\{p_{\Vector{s}}\}$
$p_{\Vector{s}}$ satisfies <ref> or <ref>
see <Ref>

compute SONC/SAGE for $p_{\Vector{s}^+}$ and $p_{\Vector{s}^-}$
propagate new bound upwards
$\operatorname{SONC-Min}(p_{\Vector{s}^+}) < \variableStyle{min}$ or $\operatorname{SONC-Min}(p_{\Vector{s}^-}) < \variableStyle{min}$
update $\variableStyle{min}$
$\variableStyle{active} \gets \variableStyle{active}\cup\{p_{\Vector{s}^+}, p_{\Vector{s}^-}\}$

Our search tree is a binary tree of height at most $n$, so it has at most $2^{2n+1}-1$ nodes, which means at most $2^{n+1}-1$ different polynomials are involved.
Furthermore, in each state, exactly the leaves are in $\variableStyle{active}$ and we never remove nodes from the tree.
Therefore, each polynomial is chosen at most once in the loop in <ref>.

As a final variation, it turned out that SAGE takes significantly longer than SONC, but for most sign cones the bound computed via SONC suffices.
So, initially we only compute a lower bound via SONC for each $p_{\Vector{s}}$.
If some node is chosen for the first time, we then compute a lower bound via SAGE and the node remains active.
Only if this node is chosen a second time, it becomes inactive and we branch into the two sub-cones.

§ MINIMAL ORTHANTS

As alternative to the branch-and-bound algorithm, we can find a sufficient subset of the leaves and directly compute lower bounds for these polynomials.

As soon as we are given a concrete orthant, i.e. we know the sign of every variable, we can compute the effective sign of each term, i.e. we know whether it is positive or negative.
To keep consistent with our previous notation for the relaxation, we also denote this polynomial as $\relax{p} = \left(A(p), \relax{b(p)}\right)$.
Now we define a partial order $b_1\leq b_2$ on the effective coefficient vectors as elementwise $\leq$.
This lifts to a partial order on the polynomials

\begin{align*}
\polynomial{A}{b_1} \leq \polynomial{A}{b_2} :\Leftrightarrow b_1\leq b_2.
\end{align*}

Going over all orthants yields $2^n$ polynomials.
But the crucial observation is that we only need to compute bounds for the minimal polynomials.

Consider the following polynomial with 3 variables.

\begin{align*}
p&=2.723 + 3.932\cdot x_2^{8} + 6.054\cdot x_1^{2} + 1.963\cdot x_1^{4} x_2^{2} - 1.204\cdot x_0^{1} x_1^{1} x_2^{3} + 1.462\cdot x_0^{1} x_1^{2} x_2^{1}\\
&\quad+ 1.766\cdot x_0^{1} x_1^{2} x_2^{2} + 0.841\cdot x_0^{1} x_1^{2} x_2^{4} - 0.329\cdot x_0^{2} x_1^{1} x_2^{2} + 7.57\cdot x_0^{2} x_1^{2} x_2^{4} + 2.428\cdot x_0^{4} x_2^{2}
\end{align*}

Then the minimal orthants are given by the signs $(-,+,+)$, $(-,+,-)$ and $(-,-,+)$.
So instead of solving $8=2^3$ instances, we only have to solve the three instances where we restrict $p$ to each of the above orthants.

§.§ Computing Minimal Orthants

For convenience, we define the indicator function for strictly negative terms

\begin{align*}
\struc{\negative}(x) = \begin{cases}1&:x<0\\0&:x\geq0\end{cases}.
\end{align*}

If called on a vector, the function is applied elementwise.

Computing the orthants with minimal coefficient vector is fixed parameter tractable in $n$, via the following algorithm.

$p$ – Polynomial
$\minList$ – Set of orthants, where coefficients have minimal effective sign
$\minList = \emptyset$
$\variableStyle{sign} \in \{0,1\}^n$ fork over all orthants
$v = \left(\variableStyle{sign} \cdot A + \negative(b)\right) \bmod 2$
$(e,s) \in \minList$
$e \leq v$
continue with next $\variableStyle{sign}$ $v$ is not minimal
$v < e$
$\minList.remove(e,s)$ $e$ is not minimal
$\minList.add(v,\variableStyle{sign})$ $v$ is minimal, if we reach the end of the for-loop

Let $t'$ be the number of non-squares.
The length of $\minList$ is bounded by both $2^n$ and the length of the maximal antichain $\binom{t'}{t'/2}$.
Furthermore, each comparison runs in $\mathcal O(t')$.
So the overall running time is

\begin{align*}
\mathcal O\left(t'\cdot 2^n\cdot \min\left(2^n, \binom{t'}{t'/2}\right)\right)
\subseteq \mathcal O\left(t\cdot 4^n\right)
\end{align*}

which is fixed parameter tractable in $n$.

In particular, the proof shows that this approach is useful for polynomials with few non-squares.

Experiments show that for $n=10$ variables and $t'=100$ this can be done in about 2 seconds.
We consider the problem of determining the minimal orthants practically feasible for values $n\leq 15$.

Then, we create polynomials

\begin{align*}
p_v = \polynomial{A}{v} \quad\text{ for all }(v,\variableStyle{sign})\in \minList
\end{align*}

and optimise each over the positive orthant.
Hence, the running time significantly depends on the number of minimal orthants.
For polynomials with many monomial non-squares, we usually have $|\minList| = 2^n$, but for instances with few monomial non-squares, we significantly reduce the running time by restricting ourselves to the minimal orthants.

For the final lower bound, we then get

\begin{align*}
\lowerBound{p} = \min\left\{\lowerBound{p_v} : (v,\variableStyle{sign}) \in \minList\right\}.
\end{align*}

The advantage of this approach, compared to the search tree, is its easy parallelisation.
The major disadvantage is that a numerical failure in a single polynomial $p_v$ already causes the trivial bound $\lowerBound{p} = -\infty$.
We discuss the quality of the results and the frequency of this problem in <ref>.

§.§ Reducing the Search Tree

The idea of this section also gives rise to a variant of the branch-and-bound approach from <ref>.
First we compute the minimal orthants $\minList$ as described in <ref>.
Then we create a tree whose leaves are the elements of $\minList$ and we branch the signs of the variables $x_1,\ldots,x_n$ in that order.
Whenever we compute a node of the tree, that only has a single child, we further descend down the tree, until we arrive at a node with two children, or a leaf.
Otherwise we apply the same algorithm as in <ref>, including the criteria for cutting off a branch.
We denote this algorithm by -sparse.

§ EXPERIMENTAL RESULTS

We start by discussing the running time and the results of the algorithms presented above on a few selected examples.
Afterwards, we describe how the algorithms behaved on a large set of test cases.

§.§ Experimental Setup

We give an overview about the experimental setup.

The entire experiment was steered by our Python 3.7 based software POEM 0.3.0.0(a) (Effective Methods in Polynomial Optimisation), [25], which we develop since July 2017.
POEM is open source, under GNU public license, and available at:

For our experiment, POEM calls a range of further software and solvers for computing the certificates.
For the numerical solutions of SONC and SAGE, we use CVXPY 1.0.28 [7], to create the convex optimisation problems.
To solve the problems, we use  2.0.7 [8],  9 [2] and  1.2.2 [1].

As heuristic to find local minima of polynomials we use Müller's approach as decribed in <ref>.
In addition, we call local minimisation methods from random starting points and differential evolution from SciPy 1.4.1. [15].

Investigated Data
The experiment was carried out on a database containing  randomly generated polynomials.
The possible numbers of variables are $n=\variables$; the degree takes various (even) values $4\leq d\leq 60$ and the number of terms can be $t=\Myterms$.

We created the examples using POEM, and they are available in full at the homepage cited above.
The instances investigated here, are a subset of those from [24].
In that paper, we also describe their creation in more detail.
The overall running time for all our instances was  hours.

Hardware and System
We used an  CPU with 1.8 GHz, 4 cores, 8 threads and 16 GB of RAM under Ubuntu 18.04 for our computations.

Stopping Criteria
For the accuracy of the solver and the precision of the rounding in Python we used a tolerance of $\varepsilon=2^{-23}$.
We restrict ourselves to $n\leq 8$, to keep the potential factor $2^n$ for the running time in a reasonable range.
Furthermore, when running SAGE, we noticed a significant increase in both run time, memory consumption and occurrences of numerical problems for $t\geq 100$.
Therefore, we restrict ourselves to $t\leq 50$ (which was the next lower number of terms in our example set).

§.§ Selected Examples

We consider a polynomial with $n=4$ variables, degree $d=16$ and $t=50$ terms.
Here we particularly see, how the branch and bound approach significantly improved the bound.
The lowest value we found, is $\xmin \approx 19.203$.
We present lower bounds we obtained in <ref>.

The best bound was found by .
The approach by  failed, because for at least one of the orthants, both SONC and SAGE encountered numerical issues.
Since the overall bound is given by the worst bound on any of the orthants, we only obtain the trivial bound $-\infty$.

Next, we observe, that the sparse version of  here actually takes longer than the standard version.
Both methods compute 23 out of 31 possible nodes of the search tree.
So the sparse method does not have any advantage.

Furthermore, it computes a worse bound.
The reason for the latter is, that we branch the variables in a different order.
At some point, SAGE runs into numerical problems, and these issues arise at different nodes in the search tree.
The remaining bounds are then computed with the weaker, but more stable SONC method.
Therefore, the two versions of  can have different results.

lower bound           difference      time       strategy     options

11.992  	    7.211            0.17      SONC

13.693  	    5.510            0.19      SONC          alternative covering

14.458  	    4.745            3.09      SAGE

18.769  	    0.434           53.98

18.284  	    0.918           56.43      ,     sparse

$-\infty$     $\infty$         2.26      ,     SONC only

$-\infty$     $\infty$         9.97      ,     SONC and SAGE

Comparison of time and quality of the lower bounds obtained by different approaches.
Branch and bound yields the best bound.
The forking algorithm numerically failed on some orthant, so its bound is $-\infty$.

The next example is a polynomial with $n=4$ variables, degree $d=10$ and $t=30$ terms.
Here, -sparse computes the optimal bound $\xmin \approx 4.08$, while all of our other methods have an optimality gap of at least $0.27$.
Together with <ref>, it shows that  and -sparse are in general incomparable in terms of their results.

lower bound     difference      time     strategy     options

-58.80          62.88           0.12     SONC

-51.84          55.92           0.20     SONC    alternative covering

-25.65          29.73           1.46     SAGE

3.80          0.277          31.98

4.08          0              35.84     ,     sparse

0.40          3.681           1.39     ,     SONC only

3.80          0.277           4.29     ,     SONC and SAGE

Comparison of time and quality of the lower bounds obtained by different approaches.
Here, the sparse version of  computed the best bound but also took the longest tie.
All of our other methods computed worse bounds.

§.§ Evaluation of the Experiment

In this section, we summarise our findings from running our experiment on  instances.

The bound of  is at least as good as the bound of .
<ref> shows the difference between the lower bounds obtained by  and , where a positive value means that  gave a better bound.
In the majority of cases the difference is numerically zero, but in some cases,  performs significantly better.
In no case the differences goes below $-10^{-5}$.

Difference between the bounds of  and .
Practically, the result of  is always as least as good as the one of .
In the majority of our examples the difference is numerically zero.

Sparse  is slightly faster than standard .
The quotients of the running time for standard  divided by the time of sparse  range from  to  with a geometric mean of .
So, on average, the standard version takes about % longer.
The distribution of these quotients is shown with more detail in <ref>.
In particular, in the majority of our cases, the run times differ by a factor of at most 2.

Quotient of runtimes of standard  divided by sparse .
In most cases the times differ by a factor of at most 2, but overall the sparse version has a slight advantage.

Failure of  is rare.
As seen in <ref>,  may return the trivial bound $-\infty$.
However, this only rarely happends.
Among our test cases, there are only  instances, where  fails, but (at least one variant of)  finds a lower bound.

Run time of  and , depending on $n,t$
As expected, the running time increases with both $n$ and $t$.
In <ref> and <ref>, we present the running times of  and , depending on $n$ and $t$.
Since we observed in <ref> and [24], that the running time is independent of the degree, we average over the degree as well.
We can see, that the growth in $n$ is slower than $\Theta(2^n)$.
Also note, that we have at least $n+1$ monomial squares, so for few terms the ratio of non-squares decreases with growing $n$.
Thus, in these cases, the running time even decreases with growing $n$.

Average runtime of standard , depending on $n$ and $t$.
A  marks parameters, where we have less than 10 instances.

Average runtime of  with SAGE, depending on $n$ and $t$.
A  marks parameters, where we have less than 10 instances.

Optimality Gap
In <ref>, we can see the distribution of the optimality gap among our instances, for how many instances the gap lies in the given interval.
For the left bars (blue), we combined all of our new methods and took their best bound.
The right bars (orange) show the distribution of the optimality gap, when just using SAGE.
We computed the (local) minima via  along with the lower bounds.

For  instances, about %, our methods yield a gap of at most $10^{-6}$, which we consider numerically zero.
Furthermore, we see a clear improvement compared to using only a single call of SAGE.

Distribution of the optimality gap;
Left, in blue, we show the optimality gap for the combined methods standard-, sparse- and  with SAGE, taking their best bound.
The right bars, in orange, show the optimality gap if we just use SAGE to compute a global lower bound.

§ RESUME AND OUTLOOK

Our paper consists of two main contributions.
The first contribution is a branch-and-bound framework, where we branch over the signs of the variables.
Thus, additional terms can be identified as positive, which improves the lower bounds obtained via SONC and SAGE.
Second, we give an alternative to the branch-and-bound approach.
We identify the minimal orthants with respect to their sets of positive terms.
In these orthants we compute lower bounds for the given polynomial and the worst of these bounds is a global lower bound.
The two algorithms are fixed parameter tractable when parametrised by the number of variables.

We ran these methods on a larger number of test cases and draw the following conclusions.

* To obtain the best result, the method of choice is .
However, between standard- and sparse- there is no clear favourite, which approach computes a better bound.
Only with respect to the running time there is a slight advantage for using the sparse version.

* Especially for few terms,  runs significantly faster than .
This speed-up partially comes from parallel computations, but also from our preprocessing, so we run fewer instances of SONC and SAGE.

* Computing the minimal orthants for  runs fast.
So it is possible to a priori get an estimate of the running time of .
If the gain from eliminating orthant is too small, we can simply run  instead.

The most interesting course for further work is to find better cut criteria for the branch-and-bound approach.
These might significantly improve the running time of our algorithm.
Also, the order, in which we branch the variables, is important for the size of the search tree and thus, for the running time.
A significant advantage for  is its parallelisation.
To speed up , we can compute several nodes of the search tree in parallel.

To improve the results of , we can identify the orthants, where some computation failed.
These orthants correspond to leaves in the search tree of .
By moving up in the tree and computing lower bounds for these nodes, we still obtain lower bounds for the original orthant.

Finally, we want to emphasise, that both  and  are just frameworks, which use SONC and SAGE.
So any improvement for these, which could be quality of results, running time or numerical stability, results in an improvement for the algorithms in this paper.

[1]
M. Andersen, J.Dahl, and L. Vandenberghe.
CVXOPT - Python Software for Convex Optimization.

[2]
M. ApS.
MOSEK Optimizer API for Python 9.0.98, 2019.

[3]
G. Blekherman.
There are significantly more nonegative polynomials than sums of
Israel Journal of Mathematics, 153(1):355–380, Dec 2006.

[4]
G. Blekherman, P. Parrilo, and R. Thomas.
Semidefinite Optimization and Convex Algebraic Geometry,
volume 13 of MOS-SIAM Series on Optimization.
SIAM and the Mathematical Optimization Society, Philadelphia, 2013.

[5]
V. Chandrasekaran and P. Shah.
Relative Entropy Relaxations for Signomial Optimization.
SIAM J. Optim., 26(2):1147–1173, 2016.

[6]
V. Chandrasekaran and P. Shah.
Relative entropy optimization and its applications.
Mathematical Programming, 161(1-2):1–32, 2017.

[7]
S. Diamond and S. Boyd.
CVXPY: A Python-embedded modeling language for convex
Journal of Machine Learning Research, 17(83):1–5, 2016.

[8]
A. Domahidi, E. Chu, and S. Boyd.
ECOS: An SOCP solver for embedded systems.
In European Control Conference (ECC), pages 3071–3076, 2013.

[9]
M. Dressler, S. Iliman, and T. de Wolff.
A Positivstellensatz for Sums of Nonnegative Circuit
SIAM J. Appl. Algebra Geom., 1(1):536–555, 2017.

[10]
T. de Wolff.
Amoebas, nonnegative polynomials and sums of squares supported on
Oberwolfach Rep., (23):1308–1311, 2015.

[11]
J. Flum and M. Grohe.
Parameterized Complexity Theory.
Springer, 2006.

[12]
R. Fletcher and C. M. Reeves.
Function minimization by conjugate gradients.
The Computer Journal, 7(2):149–154, 1964.

[13]
M. Grohe.
Logic, Graphs, and Algorithms.
In Logic and automata, pages 357–422, 2008.

[14]
S. Iliman and T. de Wolff.
Amoebas, nonnegative polynomials and sums of squares supported on
Res. Math. Sci., 3:3:9, 2016.

[15]
E. Jones, T. Oliphant, P. Peterson, et al.
SciPy: Open source scientific tools for Python, 2001–.
[Online; accessed August 27, 2024].

[16]
J. Lasserre.
Moments, positive polynomials and their applications, volume 1
of Imperial College Press Optimization Series.
Imperial College Press, London, 2010.

[17]
J. Lasserre.
An introduction to polynomial and semi-algebraic optimization.
Cambridge Texts in Applied Mathematics. Cambridge University Press,
Cambridge, 2015.

[18]
M. Laurent.
Sums of squares, moment matrices and optimization over polynomials.
In Emerging applications of algebraic geometry, volume 149 of
IMA Vol. Math. Appl., pages 157–270. Springer, New York, 2009.

[19]
R. Murray, V. Chandrasekaran, and A. Wierman.
Newton polytopes and relative entropy optimization.
arXiv preprint arXiv:1810.01614, 2018.

[20]
K. G. Murty and S. N. Kabadi.
Some NP-complete Problems in Quadratic and Nonlinear
Mathematical Programming, 39(2):117–129, 1987.

[21]
H. Müller.
Minima of Polynomials via SONC Decompositions.
Bachelor's thesis, TU Berlin, Berlin, October 2018.

[22]
J. Oxley.
Matroid theory, volume 21 of Oxford Graduate Texts in
Oxford University Press, Oxford, second edition, 2011.

[23]
J. Renegar.
A faster PSPACE algorithm for deciding the existential theory of
the reals.
In Foundations of Computer Science, 1988., 29th Annual Symposium
on, pages 291–295. IEEE, 1988.

[24]
H. Seidler and T. de Wolff.
An Experimental Comparison of SONC and SOS Certificates for
Unconstrained Optimization.
arXiv preprint arXiv:1808.08431, 2018.

[25]
H. Seidler.
POEM: Effective methods in polynomial optimization, version
<http://www.user.tu-berlin.de/henning.seidler/POEM/>, May 2021.