Computational and algebraic aspects of sums of nonnegative circuit polynomials
| Autor: | Seidler, Henning |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| DOI: | 10.14279/depositonce-16145 |
| Popis: | In this thesis we introduce a new method how to algorithmically determine lower bounds for multivariate polynomials. It is based on Circuit Polynomials, a class of sparse polynomials, whose nonnegativity is easily checked. The algorithm tries to decompose the given polynomial into a Sum of Nonnegative Circuit Polynomials (SONC) and a constant, therefore providing a lower bound in the majority of cases. Opposed to the established method Sums of Squares (SOS), the complexity of our method does not depend on the degree of the polynomial, but is mainly determined by the number of terms. In fact, our algorithm has a polynomial running time, even when polynomials are given in sparse notation. Hence, our approach is especially suited for sparse polynomials of high degree. Furthermore, we present two extensions of this method. The first one improves the lower bounds by performing a branch-and-bound over the signs of the variables. The running time is FPT in the number of variables, so it remains feasible for a moderate amount of them. In the second extension, we provide a method how, under some additional assumptions, the numerical results of our computations can be transformed into certificates in exact arithmetic. All of our methods are implemented in the free software POEM in Python and extensively tested. We end with a detailed evaluation, in particular comparing running time and quality of the lower bounds with SOS. In dieser Arbeit stellen wir eine neuartige Methode vor, um algorithmisch untere Schranken für multivariate Polynome zu bestimmen. Die Methode basiert auf Circuit-Polynomen, einer Klasse dünn besetzter Polynome, deren Nichtnegativität einfach überprüft werden kann. Der Algorithmus versucht, ein gegebenes Polynom in eine Summe nichtnegativer Circuit-Polynome und eine Konstante zu zerlegen, wodurch sich im Erfolgsfall eine untere Schranke für die Funktionswerte ergibt. Im Gegensatz zu der etablierten Methode Sums of Squares (SOS), hängt die Komplexität unserer Methode nicht vom Grad des Polynoms ab, sondern hauptsächlich von der Anzahl der Terme. Dadurch hat unser Algorithmus eine polynomielle Laufzeit, selbst wenn das Polynom in dünn besetzter Notation gegeben ist. Somit ist der Algorithmus besonders gut geeignet für dünn besetzte Polynome hohen Grades. Weiterhin stellen wir zwei Erweiterungen dieser Methode vor. Die erste verbessert die unteren Schranken mittels eines branch-and-bound-Ansatzes, bei welchem die Vorzeichen der Variablen betrachtet werden. Die Laufzeit ist nicht mehr polynomiell, sondern FPT in der Anzahl der Variablen. Damit bleibt das Verfahren anwendbar für moderate Größenordnungen. Die zweite Erweiterung ist ein post-processing, welches unter gewissen zusätzlichen Annahmen in der Lage ist, die numerischen Lösungen umzuwandeln innachweisbare untere Schranken in exakter Arithmetik. Alle unsere Methoden sind in der freien Software POEM implementiert und ausgiebig getestet. Wir schließen die Arbeit mit einer detaillierten Evaluation dieser Software, wobei wir insbesondere die praktischen Laufzeiten, die Qualität der gefundenen Schranken und den Vergleich mit SOS untersuchen. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|