Algorithmisches Differenzieren

In den nächsten Wochen bis zum 20.2.2020 möchte Anna Hein,
Studentin der Wissenschaftskommunikation am KIT, eine Studie im
Rahmen ihrer Masterarbeit über den Podcast Modellansatz
durchführen. Dazu möchte sie gerne einige Interviews mit Ihnen,
den Hörerinnen und Hörern des Podcast Modellansatz führen, um
herauszufinden, wer den Podcast hört und wie und wofür er genutzt
wird. Die Interviews werden anonymisiert und werden jeweils circa
15 Minuten in Anspruch nehmen. Für die Teilnahme an der Studie
können Sie sich bis zum 20.2.2020 unter der Emailadresse
studie.modellansatz@web.de bei Anna Hein melden. Wir würden uns
sehr freuen, wenn sich viele Interessenten melden würden.



Gudruns Arbeitsgruppe begrüßte im Januar 2020 Andrea Walther als
Gast. Sie ist Expertin für das algorithmische Differenzieren (AD)
und ihre Arbeitsgruppe ist verantwortlich für das ADOL-C
Programmpaket zum algorithmischen Differenzieren. Zusammen mit
Andreas Griewank hat sie 2008 das Standardbuch zu AD
veröffentlicht.


Im Abitur und im mathematischen Grundstudium lernt jede und jeder
Anwendungen kennen, wo Ableitungen von Funktionen gebraucht
werden. Insbesondere beim Auffinden von Minima und Maxima von
Funktionen ist es sehr praktisch, dies als Nullstellen der
Ableitung zu finden.


Bei der Modellierung komplexer Zusammenhänge mit Hilfe von
partiellen Differentialgleichungen ist es möglich, diese Idee in
ein abstrakteres Setting zu Übertragen. Eine sogenannte
Kostenfunktion misst, wie gut Lösungen von partiellen
Differentialgleichungen einer vorgegebenen Bedingung genügen.


Man kann sich beispielsweise einen Backofen vorstellen, der
aufgeheizt wird, indem am oberen und unteren Rand eine
Heizspirale Wärme in den Ofen überträgt. Für den Braten wünscht
man sich eine bestimmte Endtemperaturverteilung. Die
Wärmeverteilung lässt sich mit Hilfe der Wärmeleitungsgleichung
berechnen. In der Kostenfunktion wird dann neben der gewünschten
Temperatur auch noch Energieeffizienz gemessen und die Abweichung
von der Endtemperatur wird zusammen mit der benötigten Energie
minimiert.


Auch hierzu werden Ableitungen berechnet, deren Nullstellen
helfen, diese Kosten zu minimeren. Man spricht hier von optimaler
Steuerung. Eine Möglichkeit, die abstrakte Ableitung
auszudrücken, ist das Lösen eines sogenannten adjungierten
partiellen Differenzialgleichungsproblems.


Aber hier wird es sehr schwierig, immer schnell und fehlerfrei
Ableitungen von sehr komplexen und verschachtelten Funktionen zu
berechnen, zumal sie für jedes Problem immer wieder neu und
anders aussehen. Außerdem braucht man in der numerischen
Auswertung des Algorithmus oft nur Werte dieser Ableitung an
bestimmten Stellen.


Deshalb ist die effiziente Berechnung von Funktionswerten der
Ableitung ein unverzichtbarer Baustein in zahlreichen
Anwendungen, die von Methoden zur Lösung nichtlinearer
Gleichungen bis hin zu ausgefeilten Simulationen in der
Optimierung und optimalen Kontrolle reichen. Am liebsten sollte
dies der Computer fehlerfrei oder doch mit sehr kleinen Fehlern
übernehmen können.


Auch für das Newtonverfahren braucht man die Ableitung der
Funktion. Es ist das Standardverfahren zur Lösung nichtlinearer
Gleichungen und Gleichungssysteme.


Das algorithmische Differenzieren (AD) liefert genaue Werte für
jede Funktion, die in einer höheren Programmiersprache gegeben
ist, und zwar mit einer zeitlichen und räumlichen Komplexität,
die durch die Komplexität der Auswertung der Funktion beschränkt
ist.


Der Kerngedanke der AD ist die systematische Anwendung der
Kettenregel der Analysis. Zu diesem Zweck wird die Berechnung der
Funktion in eine (typischerweise lange) Folge einfacher
Auswertungen zerlegt, z.B. Additionen, Multiplikationen und
Aufrufe von elementaren Funktionen wie zum Beispiel
Exponentialfunktion oder Potenzen. Die Ableitungen bezüglich der
Argumente dieser einfachen Operationen können leicht berechnet
werden. Eine systematische Anwendung der Kettenregel ergibt dann
die Ableitungen der gesamten Sequenz in Bezug auf die
Eingangsvariablen


Man unterscheidet zwei Verfahren: den Vorwärts- und den
Rückwärtsmodus. Im Vorwärtsmodus berechnet man das
Matrizenprodukt der Jacobi-Matrix mit einer beliebigen Matrix
(sogenannte Seedmatrix), ohne vorher die Komponenten der
Jacobi-Matrix zu bestimmen. Der Rückwärtsmodus besteht aus zwei
Phasen. Die Originalfunktion wird zunächst ausgeführt und gewisse
Daten abgespeichert. Anschließend rechnet man rückwärts. Dabei
werden Richtungsableitungen übergeben und es werden die im ersten
Schritt gespeicherten Daten verwendet.


Mit dem Rückwärtsmodus von AD ist es möglich, den Gradienten
einer skalarwertigen Funktion mit Laufzeitkosten von weniger als
vier Funktionsauswertungen zu berechnen. Diese Grenze ist auch
noch völlig unabhängig von der Anzahl der Eingangsvariablen. Das
ist phänomenal effektiv, aber er ist mit einem erhöhten
Speicherbedarf verbunden. Im Laufe der Jahre wurden
Checkpointing-Strategien entwickelt, um einen goldenen Mittelweg
zu finden.


Die Methoden sind für viele und sehr unterschiedliche Anwendungen
interessant. In DFG-Projekten an denen Andrea beteiligt war und
ist, wurde das unter anderem für die Modellierung von
Piezokeramiken und für die Maxwellsche Wellengleichung umgesetzt.
Außerdem sprechen Gudrun und Andrea über die Optimierung der Form
einer Turbinenschaufel.


Andrea begann ihre berufliche Laufbahn mit einer Ausbildung zur
Bankkauffrau in Bremerhaven. Sie entschied sich anschließend für
ein Studium der Wirtschaftsmathematik, um Mathematik und ihren
erlernten Beruf zusammen zu halten. Unter den wenigen verfügbaren
Standorten für so ein Studium in Deutschland entschied sie sich
für die Universität Bayreuth. Nach Abschluss des Diploms gab es
die Chance, an der TU Dresden im Optimierungsfeld zu arbeiten.
Dort promovierte sie, wurde es später Leiterin der selbständigen
Nachwuchsgruppe "Analyse und Optimierung von Computermodellen",
Juniorprofessorin für "Analyse und Optimierung von
Computermodellen" und habilitierte sich. 2009-2019 war sie als
Professorin für "Mathematik und ihre Anwendungen" an der
Universität Paderborn tätig. Seit Oktober 2019 ist sie
Professorin für "Mathematische Optimierung", Humboldt-Universität
zu Berlin.



Literatur und weiterführende Informationen

A. Griewank und A. Walther: Evaluating Derivatives:
Principles and Techniques of Algorithmic Differentiation, Second
Edition. SIAM (2008).

A. Gebremedhin und A. Walther: An Introduction to Algorithmic
Differentiation. in WIREs Data Mining and Knowledge Discovery.

S. Fiege, A. Walther und A. Griewank: An algorithm for
nonsmooth optimization by successive piecewise linearization.
Mathematical Programming 177(1-2):343-370 (2019).

A. Walther und A. Griewank: Characterizing and testing
subdifferential regularity for piecewise smooth objective
functions. SIAM Journal on Optimization 29(2):1473-1501 (2019).




Podcasts

G. Thäter, A. Zarth: Automatic Differentiation, Gespräch im
Modellansatz Podcast, Folge 167, Fakultät für Mathematik,
Karlsruher Institut für Technologie (KIT), 2018.

G. Thäter, P. Allinger und N. Stockelkamp:
Strukturoptimierung, Gespräch im Modellansatz Podcast, Folge 053,
Fakultät für Mathematik, Karlsruher Institut für Technologie
(KIT), 2015.