Computational and algebraic aspects of sums of nonnegative circuit polynomials

dc.contributor.authorSeidler, Henning
dc.contributor.grantorTechnische Universität Berlinen
dc.contributor.refereeSeifert, Jean-Pierre
dc.contributor.refereePapp, Dávid
dc.contributor.refereeKoch, Thorsten
dc.date.accepted2022-02-14
dc.date.accessioned2022-09-21T12:23:31Z
dc.date.available2022-09-21T12:23:31Z
dc.date.issued2022
dc.description.abstractIn 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.abstractIn 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.urihttps://depositonce.tu-berlin.de/handle/11303/17364
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-16145
dc.language.isoenen
dc.relation.issupplementedbyhttp://dx.doi.org/10.14279/depositonce-16146
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.subject.ddc519 Wahrscheinlichkeiten, angewandte Mathematikde
dc.subject.otherpolynomial optimisationen
dc.subject.otherSONCen
dc.subject.otherPOEMen
dc.subject.othersoftwareen
dc.subject.otherpolynomielle Optimierungde
dc.titleComputational and algebraic aspects of sums of nonnegative circuit polynomialsen
dc.title.translatedAlgorithmische und algebraische Betrachtungen nichtnegativer Circuit-Polynomede
dc.typeDoctoral Thesisen
dc.type.versionacceptedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 4 Elektrotechnik und Informatik>Inst. Softwaretechnik und Theoretische Informatik>FG Security in Telecommunicationsde
tub.affiliation.facultyFak. 4 Elektrotechnik und Informatikde
tub.affiliation.groupFG Security in Telecommunicationsde
tub.affiliation.instituteInst. Softwaretechnik und Theoretische Informatikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
Files
Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
seidler_henning.pdf
Size:
725.06 KB
Format:
Adobe Portable Document Format
Description:
Collections