# Computational and algebraic aspects of sums of nonnegative circuit polynomials

## Seidler, Henning

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.
Is Supplemented By