Global derivatives

Deussen, Jens; Naumann, Uwe; Mitsos, Alexander

doi:HT021182377

Global derivatives = Globale Ableitungen

Deussen, Jens^RWTH*

2021 & 2022

Verantwortlichkeitsangabevorgelegt von M.Sc. Jens Deussen

ImpressumAachen : RWTH Aachen University 2021

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2021

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2022

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Naumann, Uwe (Thesis advisor)^RWTH* ; Mitsos, Alexander (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2021-12-13

Online
DOI: 10.18154/RWTH-2021-11739
URL: https://publications.rwth-aachen.de/record/837052/files/837052.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
McCormick relaxations (frei) ; algorithmic differentiation (frei) ; global optimization (frei) ; graph coloring (frei) ; higher derivatives (frei) ; interval arithmetic (frei) ; significance-based approximate computing (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Die Berechnung von Ableitungsinformation numerischer Simulationen ist eine wichtige Aufgabe für die Quantifizierung von Parametersensitivitäten und für Optimierungszwecke. Algorithmisches Differenzieren (AD) bietet exakte Ableitungen bei geringem Implementierungsaufwand für den Benutzer und hoher Wartbarkeit des Computerprogramms. Die rekursive Anwendung von AD-Methoden ermöglicht die Berechnung von höheren Ableitungen. Diese Arbeit demonstriert wie AD-Modelle höherer Ordnung durch Ausnutzung von Symmetrie und Dünnbesetztheit effizient zur Berechnung höherer Ableitungen eingesetzt werden können. Zu diesem Zweck werden Algorithmen zur Graphenfärbung eingesetzt. Während herkömmliche AD-Methoden Ableitungsinformation berechnet, die nur lokal an einem bestimmten Punkt gültig ist, werden in dieser Arbeit Methoden vorgeschlagen, die einen garantierten Einschluss der Ableitungsinformation auf einem bestimmten Definitionsbereich berechnet. Diese Einschlüsse werden als globale Ableitungen (engl.\ global derivatives) bezeichnet. Die Globalisierung der Ableitungsinformation kann durch die Anwendung der Intervallarithmetik, z.B. der natürlichen Intervallerweiterung, erreicht werden. Naive Intervallberechnungen sind anfällig für eine Überschätzung der tatsächlichen Wertebereiche. Es werden Sonderfälle identifiziert, in denen die natürliche Intervallerweiterung der AD-Methoden die exakten Wertebereiche der globalen Ableitungen berechnet. Darüber hinaus werden mit der Mittelwertform und McCormick Einschließungen von AD-Methoden besser konvergierende Alternativen angeboten. Es werden zwei Anwendungen diskutiert, die von globalen Ableitungen profitieren: Deterministische globale Optimierung mittels Branch-and-Bound-Methoden und Signifikanz-getriebene Approximationsberechnungen. Im Rahmen der Fallstudie zur globalen Optimierung wird die Teilbereichsseparierbarkeit eingeführt. Diese lokale Eigenschaft ermöglicht die Aufteilung eines Optimierungsproblems auf Teilbereichen, auf denen eine bestimmte Monotoniebedingung erfüllt ist. Sowohl die Verwendung globaler Ableitungen, als auch die Teilbereichsseparierbarkeit beschleunigen die Konvergenzgeschwindigkeit des globalen Lösers enorm. Eine zweite Fallstudie zeigt, wie künstliche neuronale Netzwerke mit Hilfe von Signifikanzwerten automatisch ausgedünnt werden können. Die Ergebnisse illustrieren den Nutzen von globalen Ableitungen für Approximationsberechnungen.

The computation of derivative information of numerical simulations is an important task for the quantification of parameter sensitivities and for optimization purposes. Algorithmic differentiation (AD) methods offer exact derivatives at low implementation overhead for users and high maintainability of the computer program. Recursive application of AD methods enables the computation of higher derivatives. This thesis demonstrates how to efficiently use higher-order AD models to compute higher derivatives by exploiting symmetry and sparsity. Graph coloring algorithms are applied for this purpose. While vanilla AD methods compute derivative information that is only valid locally at a specified point, this thesis proposes methods to obtain a guaranteed enclosure of the derivative information on a specified domain. These enclosures are called global derivatives. The globalization of the derivative information can be achieved by application of interval arithmetic, e.g., the natural interval extension. Naive interval computations are prone to overestimation of actual value ranges. Special cases are identified for which the natural interval extension applied to the AD methods compute exact value ranges for the global derivatives. Furthermore, better converging methods as alternatives with the mean value form and McCormick relaxations of the AD modes are offered. Two applications that benefit from global derivatives are provided: deterministic global optimization by branch-and-bound methods, and significance-driven unreliable and approximate computing. Within the framework of the global optimization case study, subdomain separability is introduced. This local property enables the partitioning of the optimization problem on subdomains that fulfill a certain monotonicity condition. The usage of global derivatives as well as the application of subdomain separability accelerate the convergence speed of the global solver enormously for the presented problems. A second case study demonstrates how to automatically prune artificial neural networks by using significance values. The results illustrate the benefit of global derivatives for approximate computing.

OpenAccess:
PDF
(additional files)