Algorithmisches Differenzieren

Modellansatz

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 [e-mail] 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.