Problembeschreibung

Bei Verfahren der Globalen Optimierung geht man immer davon aus, dass neben lokalen (analytischen) Informationen, wie der Wert einer Funktion an einem Punkt oder deren Ableitung an einem auch globale Informationen zur Verfügung stehen. Eine aus praktischen Gesichtspunkten sehr flexiblere und daher häufige Annahme ist, dass für eine Funktion f:\mathbb{R}^n \rightarrow \mathbb{R}^m zu jedem Intervall I \in\mathbb{R}^n ein Intervall J(I)\in \mathbb{R}^m angegeben werden kann, so dass f(I)\subseteq f(J(I)) ist und dass für \lim_{\mathrm{vol}(I)\rightarrow 0} \mathrm{vol}( J(I) ) = 0 gilt. Die einfachste Form der Auswertung die diese Voraussetzungen erfüllt, ist die Intervallarithmetik, falls die Grundoperationen stetig sind.

In den vergangen Jahrzehnten hat es bereits zahlreiche Anstrengungen gegeben, sowohl bezüglich der Auswertungsmöglichkeiten, z. B. die Intervallauswertung gewöhnlicher Differentialgleichungen, als auch die Optimierung. Bei der Optimierung haben sich zwei Verfahren als geeignet erwiesen. Zum einen, Intervall-Newton Verfahren als auch direkte Bisektionsverfahren. Erstere versuchen im Gegensatz zum normalen Newton-Verfahren, welches gegen genau eine Nullstelle einer Funktion konvergieren, gegen die Menge aller Nullstellen zu konvergieren. Hierzu wird, statt \nabla f(x) = 0 die lineare Intervallgleichung \nabla f(I) = 0 gelöst. Um eine Konvergenz des Verfahrens zu garantieren, kommt dieses Verfahren natürlich auch nicht ohne Bisektion aus. Diese wird ausgeführt, wenn das Intervall der Schrittrichtungen zu groß wird.

Neben dem Intervall-Newton Verfahren wurden in den 1990 Jahren auch die Forschung an direkten Bisektionsverfahren vorangetrieben. Hierbei wird, die Funktion am Anfang über dem Gesamtintervall ausgewertet, dieses in zwei Teilintervalle zerlegt usw. Entscheidend ist hierbei natürlich, in welche Teilintervalle das Gesamtintervall zerlegt wird und in welcher Reihenfolge die Teilintervalle abgearbeitet werden.

Anwendung

Die globale Optimierung unrestringierter Funktionen in niedrigen Dimensionen tritt häufig als Teilproblem der restringierten globalen Optimierung auf. Eine häufig benötigte Anwendung ist die Berechnung von oberen und unteren Schranken von Einträgen der Hessematrix einer Funktion auf einem Intervall, woraus sich Schranken für die Eigenwerte der Hessematrix bestimmen lassen. Aus solchen Werten wiederum lassen sich mittlerweile recht gute Unterschätzer für beliebige, zweifach-differenzierbare Funktionen bestimmen.

Ziel einer Diplomarbeit

Sowohl beim Intervall-Newton-Verfahren, als auch beim Bisektionsverfahren gibt es zahlreiche Möglichkeiten, wann und wie, Intervalle unterteilt werden sollen und in welcher Reihenfolge die Teilprobleme abgearbeitet werden. In der Literatur finden sich einige Möglichkeiten, wie dies geschehen kann.

Ziel der Diplomarbeit ist es, mindestens eine, der beiden angegebenen ,,Meta’‘-Verfahren umzusetzen und Such- bzw. Bisektionstrategien aus der Literatur zu vergleichen und evtl. eigene Ideen mit einzubringen.

Voraussetzungen und Bewertung nach AG-Leitfaden

  • Vorkenntnisse und Bewertung
    • Programmierkentnisse in C
    • Kenntnisse in diskreter oder nichtlineare Optimierung sind von Vorteil
  • <b>Kentnisse aus Lehrvaranstaltungen </b> Das Thema wird in Lehrveranstaltungen kaum behandelt. Die Grundlagen sind jedoch in kurzer Zeit lernbar. Anknüpfungspunkte gibt es in der diskreten Optimierung (Branch & Bound) und der nichtlinearen Optimierung (Newton Verfahren).
  • <b>Bewertung von Zwischenschritte </b> Die Grundlegenden Algorithmen sind sehr einfach implementierbar. Das Problem liegt in der konkreten Ausgestaltung. Somit scheinen Zwischenschritte gut zu bewerten sein.
  • <b>Literatur</b> Es gibt zahlreiche Literatur zu dem Thema. Die für die konkrete Fragestellung relevanten Teile sind jedoch überschaubar.
  • <b>Implementierungsaufwand</b> Da es sich um eine empirische Arbeit handelt, welche hauptsächlich bewertenden Charakter hat, ist ein wesentlicher Teil der Arbeit die Implementierung und der Vergleich bestehender Algorithmen
  • <b>Kommunikation mit weiteren Anwendern </b> keine
  • <b>Innovation</b> Auch wenn keine Innovation vom Studenten ausgeht, kann das Ziel der Arbeit problemlos erreicht werden.

Einführende Literatur

  • T. Csendes, D. Ratz, Subdivision direction selection in interval methods for global optimization, 1997, SIAM J. Numerical Analysis 34, 922-938 (Artikel auf SIAM)
  • T. Csendes, R. Klatte, D. Ratz, A Posteriori Direction Selection Rules for Interval Optimization Methods, 2000, CEJOR Central European J. Operations Research 8, 225-236 (Preprint)
  • M.Cs. Markót, J. Fernández, L.G. Casado, T. Csendes, New interval methods for constrained global optimization, 2006, Math. Programming Vol. 106 Nr. 2 (Artikel auf Springer)

Kontakt

undefinedThorsten Gellermann