Non-SOS Putinar-like certificates of non-negativity: semi- and fully-sparse.




A certificate of non-negativity is a way to formulate a given polynomial such that its non-negativity becomes evident. Certificates of non-negativity are fundamental tools for polynomial optimization. Most of the current literature on certificates of non-negativity have been concentrated on certificates based on Sum-of-squares (SOS) polynomials. We propose a framework for constructing certificates of non-negativity based on any class of non-negative polynomials satisfying some mild assumptions. These certificates are similarly structured as Putinar's certificate. In addition to classic certificates of non-negativity, this framework can be used to obtain sparse certificates of non-negativity. For instance, we construct sparse certificates based on other polynomials such as 

SDSOS-, SAGE-, SONC- and SOS-polynomials. 

Sparse certificates are often much more efficient to compute than non-sparse certificates of non-negativity, and we expect our work to close the gap between the applicability of SOS-based and other types of certificates of non-negativity.

Zoom link:

Meeting ID: 926 2585 9904