New Certificates of Nonnegativity and Their Application in Science and Engineering

Emmy Noether研究小组的目标是建立一种新的证明非负性的证书，这种证书与平方和无关，并将这种新的证书应用于实际中，多元多项式和平方和（SOS）的非负性研究是一个经典课题。希尔伯特和其他人在世纪已经取得了初步成果，并最终解决了希尔伯特的第17个问题。该主题仍然是一个非常活跃的研究领域，特别是由于其与多项式优化的密切联系。一个多项式可以通过SOS证书证明为非负的，当且仅当某个半定优化问题（SDP）是可行的。SDP在实践中可以有效地求解，并且已知在多项式时间复杂度中可求解到ε误差。然而，SDP方法具有自然限制，如Blekherman在2006年在理论上所示以及在实践中所示。因此，人们迫切需要一种新的不依赖于SOS和SDP的非负性证书，非负回路多项式和（SONC）就是这样一种新型的非负性证书。它们是Iliman和我在2013年开发的。我们已经表明，这些证书是高度适用于在实践中通过几何规划（GP）和相对熵编程（REP），从而减少运行时间和在某些情况下更好的最小化界限相比SDPs。我建议进一步发展这些有前途的SONC证书在理论上在实践中。我打算加深对SONC锥的理解，它与其他数学学科如变形虫和平方和的关系，实施现有的和发展更强的GP和REP适用于一般多项式优化问题，以及使用这些方法来攻击真实的世界应用problems.The拟议的工作在于接口的真实的代数几何，非线性优化和应用问题的科学和工程。它将提高我们对非负多项式的锥，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.