New Certificates of Nonnegativity and Their Application in Science and Engineering

• Applicant: Professor Dr. Timo de Wolff
• Subject Area: Mathematics
• Term: from 2017 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 341488811

• Final Report Year: 2024

Final Report Abstract

This Emmy Noether project concerns a new certificate of nonnegativity called sums of nonnegative circuit polynomials (SONC). Nonnegativity of real polynomials is a central problem in real algebraic geometry since the 19th century. As nonnegativity problems are both NP-hard, and notoriously hard to solve in practice, one attacks such problems using certificates of nonnegativity. These are conditions that imply nonnegativity, are easier to test than nonnegativity, and hold for an ample amount of nonnegative polynomials. A classical certificate of nonnegativity are sums of squares (SOS), which can be computed using semidefinite programming. In 2014, Iliman and I suggested a new certificate of nonnegativity called sums of nonnegative circuit polynomials (SONC), which can be computed via relative entropy programming. SONCs are not SOS in general and form a full-dimensional cone in the cone of nonnegative polynomials (over any support A). In this Emmy Noether project we achieve various milestones to establish SONCs as a certificate of nonnegativity. Among other results, we give a description of the algebraic boundary of the SONC cone via regular functions called Λ-discriminants, which are closely related to classical A-discriminants. We extend a known correspondence between nonnegativity of SONCs and amoebas. We show combinatorial properties of maximal mediated sets, a subset of the lattice points in the Newton polytope of a polynomial, which determine whether a circuit polynomial is an SOS. We prove a that the dual version of SONC certificates can be tackled via linear programs. Moreover, we introduce the DSONC cone, a subcone of the SONC cone, which unifies strengths of the primal and the dual cone, and show several structural properties about it. We provide an implementation of initial algorithms for SONC computations and show experimentally on a large set of random polynomials that it provides fast runtimes in practice with moderately worse bounds than SOS. Finally, we apply SONCs to various problems in sciences and engineering: We use SONC to establish new bounds on parameter spaces for 2- and n-site phosphorylation, an important class in chemical reaction networks. We show that SONCs are a meaningful certificate in terms of proof systems analyzing algorithms in theoretical computer science, and show various results regarding containment and comparison of such proof systems. Moreover, we show that SONCs do not admit a Putinar-like Positivstellensatz. As a third application, we provide initial results for applying SONCs to compute Lyapunov functions for certifying stability in dynamical systems. Furthermore, we contribute to creating a 3D tensegrity that is auxetic in material science, we give algorithms for certifying correctness of SONCs symbolically, and we show that nonnegativity of symmetric SONCs can be shown via the classical Muirhead inequality.

Publications

• An Experimental Comparison of SONC and SOS Certificates for Unconstrained Optimization
  H. Seidler & T. de Wolff
  
• Exact Optimization via Sums of Nonnegative Circuits and Arithmetic-geometric-mean-exponentials. Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation, 291-298.
  Magron, Victor; Seidler, Henning & de Wolff, Timo
  
• New Dependencies of Hierarchies in Polynomial Optimization. Proceedings of the 2019 International Symposium on Symbolic and Algebraic Computation, 251-258.
  Kurpisz, Adam & de Wolff, Timo
  
• POEM: Effective Methods in Polynomial Optimization, version 0.2.1.0
  H. Seidler & T. de Wolff
  
• Computing the real isolated points of an algebraic hypersurface. Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, 297-304.
  Le, Huu Phuoc; Din, Mohab Safey El & de Wolff, Timo
  
• Global optimization via the dual SONC cone and linear programming. Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, 138-145.
  Dressler, Mareike; Heuer, Janin; Naumann, Helen & de Wolff, Timo
  
• The Kinetic Space of Multistationarity in Dual Phosphorylation. Journal of Dynamics and Differential Equations, 34(2), 825-852.
  Feliu, Elisenda; Kaihnsa, Nidhi; de Wolff, Timo & Yürük, Oğuzhan
  
• On the Maximal Mediated Set Structure and the Applications of Nonnegative Circuit Polynomials, Ph.D. thesis, Technische Universität Braunscheig, 2021
  O. Yuruk
  
• Optimization Over the Boolean Hypercube Via Sums of Nonnegative Circuit Polynomials. Foundations of Computational Mathematics, 22(2), 365-387.
  Dressler, Mareike; Kurpisz, Adam & de Wolff, Timo
  
• Reentrant tensegrity: A three-periodic, chiral, tensegrity structure that is auxetic. Science Advances, 7(50).
  Oster, Mathias; Dias, Marcelo A.; de Wolff, Timo & Evans, Myfanwy E.
  
• Initial steps in the classification of maximal mediated sets. Journal of Symbolic Computation, 109, 404-425.
  Hartzer, Jacob; Röhrig, Olivia; de Wolff, Timo & Yürük, Oğuzhan
  
• The Algebraic Boundary of the Sonc-Cone. SIAM Journal on Applied Algebra and Geometry, 6(3), 468-502.
  Forsgård, Jens & de Wolff, Timo
  
• The Duality of SONC: Advances in Circuit-based Certificates
  J. Heuer & T. de Wolff
  
• Parameter Region for Multistationarity in \({\boldsymbol{n-}}\)Site Phosphorylation Networks. SIAM Journal on Applied Dynamical Systems, 22(3), 2024-2053.
  Feliu, Elisenda; Kaihnsa, Nidhi; de Wolff, Timo & Yürük, Oğuzhan
  
• Initial Application of SONC to Lyapunov Stability of Dynamical Systems. Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, 361-370.
  de Wolff, Timo & Heuer, Janin
  
• The SONC Cone: Primal and Dual Perspectives, Ph.D. thesis, Technische Universität Braunscheig, 2024
  J. Heuer