New Certificates of Nonnegativity and Their Application in Science and Engineering

Emmy Noether研究小组提出的目的是建立一种独立于平方和的新型非负性证书，并将这种新型证书应用于实践。实多元多项式和平方和的非负性研究是一个经典课题。希尔伯特和其他人在19世纪已经取得了初步成果，并在希尔伯特第17个问题的解决中达到了高潮。该主题仍然是一个非常活跃的研究领域，特别是由于它与多项式优化密切相关。当且仅当某半定优化问题（SDP）可行时，一个多项式可以通过SOS证书证明为非负的。在实践中，sdp可以有效地求解，并且已知在多项式时间复杂度中可解到一个ε -误差。然而，正如Blekherman（2006）在理论上以及在实践中所表明的那样，SDP方法具有天然的局限性。因此，迫切需要独立于SOS和sdp的新的非负性证书。非负回路多项式和（SONC）就是一种新型的非负性证明。它们是我和Iliman最近在2013年开发的。我们已经表明，通过几何规划（GP）和相对熵规划（REP），这些证书在实践中是高度适用的，与sdp相比，它们可以减少运行时间，在某些情况下还可以更好地最小化边界。我建议从理论上和实践上进一步发展这些有前途的SONC证书。我打算加深对SONC锥的理解，以及它与阿米巴原虫和平方和等其他数学学科的关系，实现和开发更强大的适用于一般多项式优化问题的gp和rep，并使用这些方法来解决现实世界的应用问题。提出的工作是在实际代数几何，非线性优化和应用问题从科学和工程的接口。它将提高我们对非负多项式锥、SOS锥和最近开发的SONC锥的理解，以及这三者之间的相互作用，以及它们与其他数学领域的联系。在提出的工作中，我们还将通过使用几何和相对熵规划的新型非负性证明来攻击从工程和科学中得出的一般多项式优化问题。

The aim of this proposed Emmy Noether research group is to establish a new type of certificate for nonnegativity which is independent of sums of squares and to apply this new type of certificate in practice.The investigation of nonnegativity of real multivariate polynomials and of sums of squares (SOS) is a classical subject. Initial results by Hilbert and others were already achieved in the 19th century and culminated in the solution of Hilbert's 17th problem. The subject remains a highly active field of research, particularly due to its close connection to polynomial optimization. A polynomial can be certified to be nonnegative via an SOS certificate if and only if a certain semidefinite optimization problem (SDP) is feasible. SDPs can be solved efficiently in practice and are known to be solvable up to an epsilon-error in polynomial time complexity. SDP methods, however, have natural limits as shown in theory by Blekherman in 2006 as well as shown in practice. Therefore, new certificates of nonnegativity which are independent of SOS and SDPs are strongly desired.Sums of nonnegative circuit polynomials (SONC) are such a new type of nonnegativity certificate. They were recently developed by Iliman and myself in 2013. We have already shown that these certificates are highly applicable in practice via geometric programming (GP) and relative entropy programing (REP), resulting in both reduced runtime and in certain cases better minimization bounds compared to SDPs.I propose to further develop these promising SONC certificates both in theory in practice. I intend to deepen the understanding of the SONC cone, its relation to other mathematical subjects as amoebas and sums of squares, to implement existing and develop stronger GPs and REPs applicable to general polynomial optimization problems as well as to use these methods to attack real world application problems.The proposed work lies at the interface of real algebraic geometry, nonlinear optimization and applied problems from science and engineering. It will improve our understanding of the cones of nonnegative polynomials, the SOS cone and the recently developed SONC cone as well as the interplay between those three, and their connection to other areas of mathematics. During the proposed work we will moreover attack general polynomial optimization problems drawn from engineering and science via our new type of nonnegativity certificate using geometric and relative entropy programming.