# Computational and algebraic aspects of sums of nonnegative circuit polynomials

 dc.contributor.author Seidler, Henning dc.contributor.grantor Technische UniversitÃ¤t Berlin en dc.contributor.referee Seifert, Jean-Pierre dc.contributor.referee Papp, DÃ¡vid dc.contributor.referee Koch, Thorsten dc.date.accepted 2022-02-14 dc.date.accessioned 2022-09-21T12:23:31Z dc.date.available 2022-09-21T12:23:31Z dc.date.issued 2022 dc.description.abstract 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. en dc.description.abstract 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. de dc.identifier.uri https://depositonce.tu-berlin.de/handle/11303/17364 dc.identifier.uri http://dx.doi.org/10.14279/depositonce-16145 dc.language.iso en en dc.relation.issupplementedby http://dx.doi.org/10.14279/depositonce-16146 dc.rights.uri https://creativecommons.org/licenses/by/4.0/ en dc.subject.ddc 519 Wahrscheinlichkeiten, angewandte Mathematik de dc.subject.other polynomial optimisation en dc.subject.other SONC en dc.subject.other POEM en dc.subject.other software en dc.subject.other polynomielle Optimierung de dc.title Computational and algebraic aspects of sums of nonnegative circuit polynomials en dc.title.translated Algorithmische und algebraische Betrachtungen nichtnegativer Circuit-Polynome de dc.type Doctoral Thesis en dc.type.version acceptedVersion en tub.accessrights.dnb free en tub.affiliation Fak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatik::FG Security in Telecommunications de tub.affiliation.faculty Fak. 4 Elektrotechnik und Informatik de tub.affiliation.group FG Security in Telecommunications de tub.affiliation.institute Inst. Softwaretechnik und Theoretische Informatik de tub.publisher.universityorinstitution Technische UniversitÃ¤t Berlin en

## Files

##### Original bundle
Now showing 1 - 1 of 1
Name:
seidler_henning.pdf
Size:
725.06 KB
Format: