  Nonnegativity certificates can be used to obtain tight dual bounds for
polynomial optimization problems. Hierarchies of certificate-based relaxations
ensure convergence to the global optimum, but higher levels of such hierarchies
can become very computationally expensive, and the well-known sums of squares
hierarchies scale poorly with the degree of the polynomials. This has motivated
research into alternative certificates and approaches to global optimization.
We consider sums of nonnegative circuit polynomials (SONC) certificates, which
are well-suited for sparse problems since the computational cost depends on the
number of terms in the polynomials and does not depend on the degrees of the
polynomials. We propose a method that guarantees that given finite variable
domains, a SONC relaxation will yield a finite dual bound. This method opens up
a new approach to utilizing variable bounds in SONC-based methods, which is
particularly crucial for integrating SONC relaxations into branch-and-bound
algorithms. We report on computational experiments with incorporating SONC
relaxations into the spatial branch-and-bound algorithm of the mixed-integer
nonlinear programming framework SCIP. Applying our strengthening method
increases the number of instances where the SONC relaxation of the root node
yielded a finite dual bound from 9 to 330 out of 349 instances in the test set.
