  Circuit polynomials are polynomials satisfying a number of conditions that
make it easy to compute sharp and certifiable global lower bounds for them.
Consequently, one may use them to find certifiable lower bounds for any
polynomial by writing it as a sum of circuit polynomials with known lower
bounds (if possible), in a fashion similar to the better-known sum-of-squares
polynomials. Seidler and de Wolff recently showed that sums of nonnegative
circuit (SONC) polynomials can be used to compute global lower bounds (called
SONC bounds) for polynomials in this manner in polynomial time, as long as the
polynomial is bounded from below and its support satisfies a nondegeneracy
assumption. The quality of the SONC bound depends on the circuits used in the
computation, but finding the set of circuits that yield the best attainable
SONC bound among the astronomical number of candidate circuits is a non-trivial
task that has not been addressed so far. In this paper we propose an efficient
method to compute the optimal SONC lower bound by iteratively identifying the
optimal circuits to use in the SONC bounding process. The method is based on a
new proof of a recent result by Wang which states that (under the same
nondegeneracy assumption) every SONC polynomial decomposes into SONC
polynomials on the same support. Our proof, based on convex programming
duality, removes the nondegeneracy assumption and motivates an algorithm that
generates an optimal set of circuits and computes the corresponding SONC bound
in a manner that is particularly attractive for sparse polynomials. The method
is implemented and tested on a large set of sparse polynomial optimization
problems with up to 40 unknowns, of degree up to 60, and up to 3000 monomials
in the support. The results indicate that the method is efficient in practice.
[abstract truncated for arXiv character limits]
