Bergwandern in n Dimensionen

Christoph Pöppe

Stellen Sie sich vor, Sie werden bei einer Bergwanderung in den Alpen vom Nebel überrascht. Die Sichtweite beträgt nur noch wenige Meter, Sie kennen sich nicht aus, und andere Orientierungsmöglichkeiten wie GPS stehen nicht zur Verfügung. Da Sie sich Ihren Standort nicht gemerkt haben, hilft Ihnen auch die Wanderkarte nicht viel. Es versteht sich, dass Sie möglichst rasch, bevor es dunkel wird, ins Tal wollen – einerlei in welches Tal, denn dort findet sich mit Sicherheit ein Unterschlupf für die Nacht und vielleicht sogar eine Portion Kässpätzle, oder was das Herz sonst begehrt.

Was tun? Das scheint relativ klar. Sie schauen sich um, gehen ein paar Schritte in die Richtung, in der es am steilsten bergab geht, schauen sich wieder um – vom neuen Standpunkt aus sieht man etwas mehr vom Gelände –, wählen wieder die Richtung des steilsten Abstiegs, und so weiter. 

In den echten Alpen dürfte dieses Rezept in den meisten Fällen zum Ziel führen. Scheitern würde es allenfalls an einer hoch gelegenen Talsenke, die möglicherweise von einem abflusslosen See gefüllt ist – was in den Alpen eher selten vorkommt. Oder man trifft auf eine senkrecht abfallende Wand, und der nächste Schritt führt einen zwar ein gutes Stück abwärts, aber die Nebenbedingung, dass man die Wanderung überleben soll, ist nicht erfüllt.

Am Ziel angekommen, stellen Sie fest, dass Sie einen ziemlich großen Umweg gelaufen sind. Das Ende Ihrer Wanderung liegt nämlich an der Mündung eines kleinen Flusses, der sich eine einigermaßen geradlinige Schlucht ins Gebirge gegraben hat. Als der Nebel kam, waren Sie an einem der Hänge dieses schmalen Tals, sind zunächst steil bergab bis zum Fluss gelaufen und dann dessen Lauf gefolgt. Mit dem richtigen Überblick wären Sie ganz allmählich schräg am Hang mäßig abwärts gewandert und hätten eine Menge Weg gespart.

Na gut. Natürlich schreibe ich in diesem Mathematik-Blog nicht wirklich übers Bergwandern. Aber das ist eine geeignete Krücke zum Verständnis abstrakter Probleme, die unserer Vorstellung nicht so ohne weiteres zugänglich sind.

Eine Wanderung, mathematisch modelliert

Das Bergwandererproblem in Mathematik umzusetzen ist nicht besonders schwer. Als Koordinatensystem bieten sich Längen- und Breitengrade an. Es gibt eine Funktion, nennen wir sie f(x), die gibt zu jedem Punkt x dessen Höhe über dem Meeresspiegel an. (Wohlgemerkt: x besteht aus zwei reellen Zahlen, eine für die geografische Länge, die andere für die Breite.) Gesucht wird ein Punkt, für den f(x) minimal wird. 

Wenn es richtig zur Sache geht, besteht x aus n Komponenten, und n ist wesentlich größer als zwei: so viele Größen, wie man braucht, um ein zu modellierendes physikalisches oder auch chemisches System vollständig zu beschreiben. Die Funktion f kennzeichnet dann etwas, das man gerne möglichst klein hätte: den Aufwand zur Herstellung eines Produkts, das Gewicht einer Maschine, die Menge an Abfall, die der Prozess produziert, oder die Abweichung zwischen einer Prognose und der Realität. Oder man hätte f gerne möglichst groß, was dasselbe Problem mit umgekehrtem Vorzeichen ist.

Ein kundiger Wanderer würde seinen Blick über eine Landkarte schweifen lassen und dabei ohne größere Schwierigkeiten den tiefsten Punkt der Landschaft finden. Unsere Funktion f verschafft uns ebenfalls eine vollständige Kenntnis der Landschaft – aber eben nicht in Form einer Landkarte! 

Abgesehen davon, dass die Karte n Dimensionen haben müsste, gibt uns die Funktion f keinen adlergleichen Überblick. Vielmehr sagt sie uns nur, wie hoch es an jedem Punkt x ist, den wir ihr vorlegen. Daraus eine Landkarte zu machen, indem wir die Funktion an lauter dicht gepackten Punkten unseres Rechengebiets auswerten, sagen wir 100 Punkte entlang jeder Koordinatenachse, ist im Allgemeinen keine gute Idee. Eine Funktionsauswertung kann nämlich den Computer eine ganze Weile beschäftigen, und 100ⁿ Punkte sind schon für mäßig große n sehr viel. 

Aber vielleicht ist unsere Funktion f ja differenzierbar, hat also in jedem Punkt eine Ableitung; im mehrdimensionalen Fall nennt man sie den Gradienten. Das Gelände ist irgendwie sanft gewellt, es gibt keine scharfen Kanten, sondern in jedem Punkt eine Tangentialebene, die beschreibt in der unmittelbaren Umgebung dieses Punktes das Gelände mit großer Genauigkeit und zeigt einem nebenbei noch genau, in welcher Richtung es am steilsten abwärts geht. Wenn man gerade auf einem Geröllfeld steht, will dieses Bild nicht so recht passen, kann aber dennoch eine brauchbare Näherung der Situation darstellen. Allerdings gibt der Gradient von f eine brauchbare Auskunft nur über die unmittelbare Umgebung; man steht also tatsächlich im Nebel. Und die Sichtweite? Darüber gibt es keine allgemeine Aussage. Das ist die Tücke der Analysis: Wie weit die Auskunft, die man durch Ableiten erhält, brauchbar ist, stellt sich, wenn überhaupt, erst im Nachhinein heraus.

Wie war das mit dem Finden von Extremstellen?

In vielen Anwendungsproblemen ist die Zielfunktion f in der Tat differenzierbar. Und da gab’s doch ein Rezept aus dem Schulunterricht: Im Minimum ist die Ableitung gleich null. (Wenn umgekehrt die Ableitung null ist, dann ist da noch lange kein Minimum; das will noch eigens nachgeprüft werden. Aber diese Komplikation soll uns hier nicht beschäftigen.) Dann suchen wir doch einfach nach einer Nullstelle der Ableitung. Das läuft auf die Lösung eines Systems aus n Gleichungen mit n Unbekannten hinaus.

Das kann je nach Problem ziemlich unübersichtlich werden. Aber wenn der Gradient selbst eine differenzierbare Funktion ist, dann kann man seine Nullstellen mit dem Newton-Verfahren suchen. Das wiederum basiert abermals auf der Idee, dass man eine krumme Funktion durch etwas Gerades annähert, nämlich die Tangente im gegenwärtigen Standpunkt, beziehungsweise deren Verallgemeinerung im n-dimensionalen Fall. Dann berechnet man die Nullstelle der Tangente – das ist einfach, weil die Tangente ebenso wie der Gradient etwas Gerades ist – und hofft, dass die Nullstelle der Näherung eine Näherung der Nullstelle ist, das heißt, dass der so berechnete Punkt von der eigentlich gesuchten Nullstelle der Funktion nicht allzu weit weg ist. Diesen macht man zum neuen Standpunkt, berechnet dort eine Nullstelle der Tangente und so weiter.

Wenn der gegenwärtige Standpunkt nicht allzu weit vom Ziel der Suche entfernt ist, findet das Newton-Verfahren dieses Ziel mit atemberaubender Geschwindigkeit. Wenn die Situation in der Umgebung des Standorts noch deutlich anders ist als in Zielnähe, wenn also zum Beispiel zwischen dem einsamen Wanderer und dem Ziel noch ein Höhenrücken liegt, dann kann das Verfahren gewaltig in die Irre laufen. Deswegen fängt man zweckmäßig mit verkürzter Schrittweite an und lässt die Bremsen erst los, wenn das Ziel gewissermaßen in Sichtweite ist.

Verallgemeinerte Eierbecher

Zur Lösung des ursprünglichen Problems werden gewissermaßen zwei verschiedene Prinzipien aufeinandergestapelt: Man sucht ein Minimum der Zielfunktion, indem man eine Nullstelle der Ableitung sucht. Und dieser Nullstelle versucht man mit Hilfe der Ableitung der Ableitung näherzukommen. Kann man diese zwei gedanklichen Schritte zu einem zusammenfassen?

Im Prinzip ja. In einer Dimension ist das relativ klar zu sehen. Die Nullstelle einer linearen Funktion ist dasselbe wie das Minimum einer quadratischen Funktion, also der tiefste Punkt einer nach oben offenen Parabel. In zwei Dimensionen entspricht der Parabel zunächst der verallgemeinerte Eierbecher: eine Parabel, die um ihre Symmetrieachse rotiert wird – nach oben offen, und jeder horizontale Querschnitt ist kreisförmig. Aber das ist dann doch zu speziell. Im Allgemeinen ist der Eierbecher deformiert. Der Querschnitt ist dann nicht ein Kreis, sondern eine Ellipse, und die darf sehr schmal sein und sogar schräg zu den Koordinatenachsen liegen. Und die noch höherdimensionalen, noch komplizierter deformierten Eierbecher kann und mag man sich gar nicht vorstellen.

Jedenfalls läuft die beschriebene Suche nach dem Minimum auf folgendes Verfahren hinaus: Man lege an den gegenwärtigen Standpunkt denjenigen verallgemeinerten Eierbecher an, der sich der Geländeform in der Umgebung dieses Standpunkts am besten anpasst. Dann springe man zum tiefsten Punkt des Eierbechers und setze von dort aus die Suche fort. Wenn es schwierig ist, arbeite man zunächst mit geschrumpften Eierbechern und lasse sie erst kurz vor Schluss wieder auf Originalgröße anwachsen.

An diesem Bild wird klar, dass das Verfahren den Umweg des Bergwanderers vermeidet. Wenn es am Rande eines Kraters mit elliptischem Querschnitt steht, läuft es nicht dahin, wo es am steilsten abwärts geht, sondern springt schräg, unmittelbar zum Mittelpunkt der Ellipse. In mehreren Dimensionen kann die Ersparnis durchaus dramatisch ausfallen.

Lange, schmale Täler machen dem Verfahren also nicht viel aus. Richtig schwierig wird es, wenn das Tal bananenfömig ist: lang, schmal und krumm. Dann springt ein ungebremstes Verfahren mitunter gewaltig bergauf und hat die größten Schwierigkeiten, aus der falschen Ecke wieder herauszukommen. An diesen „banana-shaped valleys“ erproben dann die Designer der Optimierungsverfahren ihre Künste.

The post Bergwandern in n Dimensionen originally appeared on the HLFF SciLogs blog.