The SONC Cone : Primal and Dual Perspectives
The central task of this thesis sounds simple at first glance: Given a real, multivariate polynomial, decide whether it is nonnegative. But the brevity of this question is deceiving, as the problem of deciding nonnegativity of such functions is NP-hard in general. In fact, polynomial nonnegativity has fascinated mathematicians since at least the 19th century. Particularly, it is a fundamental topic in real algebraic geometry. The earliest approaches to determining the nonnegativity of a polynomial rely on the question whether the polynomial can be written as a sum of squares (SOS) of other polynomials. However, not every nonnegative polynomial can also be written as a sum of squares. The first concrete example of a nonnegative polynomial without an SOS representation was proven to be nonnegative by use of the arithmetic mean - geometric mean (AM-GM) inequality. Based on the idea of using the AM-GM inequality, we can construct a new certificate of nonnegativity. These so-called sums of nonnegative circuit polynomials (SONC) are the central object of this thesis. We look for ways to extend the existing results on circuit-based certificates and to better understand the structure underlying the SONC cone. We further develop a way to apply the SONC theory in order to help computations surrounding Lyapunov stability of polynomial dynamical systems. First, we investigate the extension of circuit-based certificates to symmetric polynomials using a symmetric generalization of the AM-GM inequality called the Muirhead inequality. We prove a generalized version of Muirhead's inequality which extends the classical inequality from comparing symmetric sums of monomials to also allowing certain scalar coefficients. We then use this generalized Muirhead inequality to derive conditions for nonnegativity of real symmetric polynomials. Next, we investigate the role of the dual of the SONC cone in the context of nonngeativity abd polynomial optimization. We use the dual SONC cone to construct a new subcone of the SONC cone, and prove that optimizing a polynomial using our new certificate of nonnegativity can be carried out via linear programming. We then generalize our results to a larger set of signomials by taking the conic closure of the subset of nonnegative circuit functions we defined previously. We call this cone the DSONC cone. It is, to the best of our knowledge, a previously unstudied object. Hence, we provide a fundamental analysis of its basic properties. We continue by also providing an abstract algebraic viewpoint of this new cone. Furthermore, we provide an algorithm for optimizing over the DSONC cone. Finally, we investigate an application of the theory of certificates of nonnegativity to the field of dynamical systems. Specifically, we investigate the Lyapunov stability of equilibrium points of such systems. Determining the Lyapunov stability of equilibria is a highly challenging problem, since, in general, there do not exist systematic algorithms for finding Lyapunov functions. We show that Lyapunov's stability theorem opens the door to applying algebraic methods for deciding nonnegativity. While this holds for arbitrary certificates of nonnegativity, we especially focus on the case of the SONC cone and present an algorithm for finding Lyapunov functions using the SONC cone.
Die zentrale Problemstellung dieser Arbeit erscheint auf den ersten Blick einfach: Für ein gegebenes reelles, multivariates Polynom, entschiede ob dieses Polynom nichtnegativ ist. Doch die Kürze dieser Frage täuscht, denn das Problem, die Nichtnegativität solcher Funktionen zu entscheiden, ist im Allgemeinen NP-schwer. Tatsächlich fasziniert das Gebiet der Nichtnegativität von Polynomen Mathematiker seit mindestens dem 19. Jahrhundert. Insbesondere ist sie ein zentrales Problem im Gebiet der reellen algebraischen Geometrie. Die frühesten Ansätze zur Entscheidung der Nichtnegativität von Polynomen basieren auf der Frage, ob ein Polynom als Summe von Quadraten (SOS) anderer Polynome geschrieben werden kann. Allerdings besitzt nicht jedes nichtnegative Polynom eine solche Darstellung. Die Nichtnegativität des ersten konkrete Beispiels eines nichtnegativen Polynoms ohne SOS-Repräsentation wurde mithilfe der Ungleichung vom arithmetischen und geometrischen Mittel (AM-GM) nachgewiesen. Basierend auf der Idee der Verwendung der AM-GM-Ungleichung können wir ein neues Zertifikat für Nichtnegativität konstruieren. Diese sogenannten Summen nichtnegativer Circuit-Polynome (SONC) sind die zentralen Objekte dieser Arbeit. Wir suchen nach Wegen, existierende Resultate aus dem Bereich der Circuit-basierten Zertifikate zu erweitern und die Struktur, die dem SONC-Kegel zugrunde liegt, besser zu verstehen. Darüber hinaus entwickeln wir eine Methode zur Anwendung der SONC-Theorie, welche Berechnungen im Zusammenhang mit der Lyapunov-Stabilität von polynomiellen dynamischen Systemen unterstützt. Zunächst untersuchen wir die Erweiterung von Circuit-basierten Zertifikaten auf symmetrische Polynome unter Verwendung einer symmetrischen Verallgemeinerung der AM-GM-Ungleichung, welche als Muirhead-Ungleichung bekannt ist. Wir beweisen zunächst eine verallgemeinerte Version der Muirhead-Ungleichung. Anschließend verwenden wir diese verallgemeinerte Muirhead-Ungleichung, um Bedingungen für die Nichtnegativität von reelen symmetrischen Polynomen herzuleiten. Als nächstes untersuchen wir die Rolle des dualen SONC-Kegels im Kontext Nichtnegativität und polynomiellen Optimierung. Wir verwenden den dualen SONC-Kegel, um einen neuen Teilkegel des SONC-Kegels zu konstruieren und beweisen, dass mithilfe dieses neuen Zertifikats untere Schranken an Polynome mittels eines linearen Optimierungsproblems berechnet werden können. Dann generalisieren wir unsere Ergebnisse auf eine größere Menge von Polynomen, indem wir den konischen Abschluss der zuvor definierten Teilmenge von nichtnegativen Circuit-Polynomen bilden. Wir nennen diesen Kegel den DSONC-Kegel. Es handelt sich hierbei um ein neues mathematisches Objekt. Daher liefern wir zunächst eine Übersicht über die grundlegenden Eigenschaften dieses Kegels. Anschließend betrachten wir den DSONC-Kegel aus einem abstrakten algebraischen Blickwinkel. Darüber hinaus leiten wir einen Algorithmus zur Optimierung über den DSONC-Kegel her. Abschließend untersuchen wir eine Anwendung der Theorie der Nichtnegativitätszertifikate auf das Gebiet der dynamischen Systeme. Insbesondere untersuchen wir die Lyapunov-Stabilität von Equilibriumspunkten solcher Systeme. Die Bestimmung der Lyapunov-Stabilität von Equilibriumspunkten stellt eine Herausforderung dar, da im Allgemeinen keine systematischen Algorithmen für das Finden von Lyapunov-Funktionen existieren. Wir zeigen, dass Lyapunovs Direkte Methode den Weg für die Anwendung algebraischer Methoden zur Entscheidung der Nichtnegativität auf dieses zentrale Problem öffnet. Dies gilt für beliebige Zertifikate für Nichtnegativität. Wir konzentrieren uns hier besonders auf den Fall des SONC-Kegels und präsentieren einen Algorithmus zum Finden von Lyapunov-Funktionen unter Verwendung des SONC-Kegels.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
