joint work with Helena Müller, Timo de Wolff
In this article, we describe a new way to obtain a candidate for the global minimum of a multivariate polynomial, based on its SONC decomposition. Furthermore, we present a branch-and-bound algorithm to improve the lower bounds obtained by SONC/SAGE. Applying this approach to thousands of test cases, we mostly obtain small duality gaps. In particular, we optimally solve the global minimization problem in about 75% of the investigated cases.
We describe a generalization of the SAGE polynomial cone for obtaining bounds on constrained polynomial optimization problems. Our approach leverages the fact that the SAGE signomial cone conveniently and transparently blends with convex duality. This result is extended to polynomials by the notion of a "signomial representative." Key properties of the original SAGE polynomial cone (e.g. sparsity preservation) are retained by this more general approach. We illustrate the utility of this methodology with a range of examples from the global polynomial optimization literature.
joint work with Haokun Li, Bican Xia
We consider a new pattern of sparsity for SOS programming named cross sparsity patterns. A new sparse SOS algorithm is proposed by exploiting cross sparsity patterns, and is applied to unconstrained polynomial optimization problems. It is proved that the SOS decomposition obtained by the new algorithm is always a refinement of the block-diagonalization obtained by the sign-symmetry method. Various experiments show that the new algorithm dramatically saves the computational cost compared with existing tools and can handle some really huge polynomials.