Studentische Forschung an der Fakultät für Mathematik


Ein semiglattes Newton-Verfahren mit mehrdimensionaler Filter-Globalisierung zur Lösung von \( l_1 \)-Minimierungsproblemen

Bachelorarbeit von Andre Milzarek, SS 2010
Betreuer: Prof. Dr. Michael Ulbrich

Die \( l_1 \)-Optimierung ist ein vergleichsweise junges und sehr aktives Forschungsgebiet im Bereich der nichtlinearen Optimierung, das sich mit Problemen der Form $$\min_{x \in {\mathbb R}^n} \ \ f(x) + \mu {\|x\|}_1$$ befasst. Hierbei ist \( f: {\mathbb R}^n \to{\mathbb R} \) eine konvexe, zweimal stetig differenzierbare Funktion, \( \mu>0 \) ein Regularisierungsparameter und \( {\|\cdot\|}_1 \) bezeichnet die herkömmliche (namensgebende) \( l_1 \)-Norm im \( {\mathbb R}^n \).

debl.jpg
Abbildung 1: Bildrekonstruktion für ein Deblurring-Problem
Probleme dieser Bauart sind in vielerlei Hinsicht interessant. So stellt sich aus algorithmischer und theoretisch orientierter Sicht die Frage nach Verfahren, die mit der Nichtglattheit der Zielfunktion umgehen und das Problem numerisch effizient lösen können. Andererseits besitzt das obige Modellproblem auch aus praktischer Sicht eine enorme Vielfalt an Anwendungen und Einsatzmöglichkeiten, was in erster Linie auf den Regularisierungseffekt der \( l_1 \)-Norm zurückzuführen ist. Da \( l_1 \)-Minimierungsprobleme im besonderen Maße dünnbesetzte Lösungen, also Lösungen mit vielen Nullkomponenten, bevorzugen, sind entsprechende Lösungsverfahren vor allem in Bereichen der Signalerfassung, Signalverarbeitung und der Datenkomprimierung, die primär mit dünnbesetzten Objekten arbeiten, sehr beliebt geworden.

Einer dieser Bereiche umfasst Bildrekonstruktionsprobleme und hat das Ziel, verrauschte, verschwommene oder fehlerhafte Bilder zu rekonstruieren -- man spricht von Denoising-, Deblurring- und Inpainting-Problemen. In Abbildungen 1 und 2 sind Beispiele für solche gestörten Bilder und ihre durch Anwendung des semiglatten Newton-Verfahrens für \( l_1 \)-Probleme entstandenen Rekonstruktionen zu sehen.

impaint.jpg
Abbildung 2: Rekonstruktion von Impainting durch das globalisierte, semiglatte Newton-Verfahren
Ausgangspunkt der meisten \( l_1 \)-Optimierungsverfahren ist die Herleitung einer notwendigen Optimalitätsbedingung für das \( l_1 \)-Problem. Durch Splitting-Techniken, Diskussion der Richtungsableitung der Zielfunktion oder weitere, alternative Ansätze lässt sich eine solche Bedingung in Form einer Gleichung $$x^* \ \text{löst das \( l_1 \)-Problem} \ \ \ \Leftrightarrow \ \ \ F(x^*) = 0$$ angeben, wobei \( F: {\mathbb R}^n \to {\mathbb R}^n \) stückweise stetig differenzierbar und somit wieder nichtglatt ist. Zusammen mit weiteren, äquivalenten Formulierungen bildet diese nichtglatte Gleichung einen grundlegenden Bestandteil vieler state-of-the-art Algorithmen und fließt in die Konstruktion vieler Verfahren ein.

Die grundsätzliche Idee des semiglatten, Filter-globalisierten Newton-Verfahrens lautet nun:$$\text{``Löse das $l_1$-Problem durch Lösen der Gleichung $F(x^*) = 0$.´´}$$ Wegen der Nichtdifferenzierbarkeit von \( F \) kann hierzu allerdings kein herkömmliches Newton-Verfahren verwendet werden und es muss auf eine spezielle Variante, das sogenannte semiglatte Newton-Verfahren, zurückgegriffen werden. Das semiglatte Newton-Verfahren verallgemeinert Anwendbarkeit und theoretische Resultate des Newton-Verfahrens auf die Klasse der semiglatten Funktionen, zu der \( F \) als stückweise stetig differenzierbare Funktion ebenfalls gehört, und zeigt unter ganz ähnlichen Voraussetzungen schnelle, lokale Konvergenz. Dies macht es für unterschiedlichste Problemklassen der nichtlinearen Optimierung, in denen nichtglatte Strukturen auftreten, sehr attraktiv.

Anders als beim herkömmlichen Newton-Verfahren existieren für das semiglatte Newton-Verfahren jedoch keine einheitlichen, allgemeinen Globalisierungstrategien und Globalisierungen müssen üblicherweise problemabhängig entwickelt oder angepasst werden. In meiner Bachelorarbeit schlagen wir eine Globalisierung für \( l_1 \)-Probleme vor, bei der vom Newton-Verfahren erzeugte Iterierte durch ein mehrdimensionales Filter-Framework auf Zulässigkeit getestet werden. Sollte eine Iterierte nicht zulässig sein, so wird sie verworfen und stattdessen ein Schritt eines alternativen, global konvergenten Abstiegsverfahren durchgeführt. In der Arbeit wird außerdem gezeigt, dass diese Strategie zu einem global konvergenten Verfahren führt, das unter gewissen Voraussetzungen in das semiglatte Newton-Verfahren übergeht und somit weiterhin schnell lokal konvergiert.

Zur vollständigen Bachelor-Arbeit von Andre Milzarek hier (PDF, 2MB).

Zurück zur Übersicht über studentische Forschung




Steckbrief des Autors

milzarek-bild.JPG

  • Andre Milzarek
  • Student an der TU seit WS 2007/08
  • B.Sc. in Mathematik (Elite-Teilstudiengang TopMath), SS 2010
  • Mathematische Interessen: nichtglatte Optimierung, \( l_1 \)-Optimierung, Optimierung bei Image Processing Problemen
  • nach dem Bachelor: Promotionsphase im Studienprogramm TopMath
  • Webseite (M1, Nichtlineare Optimierung)
 

TUM Mathematik Rutschen TUM Logo TUM Schriftzug Mathematik Logo Mathematik Schriftzug Rutsche

picture math department

Impressum  |  Datenschutzerklärung  |  AnregungenCopyright Technische Universität München