Effiziente Algoorithmen für nicht-glatte Optimierungsprobleme in der Bildverarbeitung

Dieses gemeinsame französisch-österreichische Wissenschaftsprojekt beschäftigt sich mit der Entwicklung von effizienten Algorithmen zum Lösen von nicht-glatten Optimierungsproblemen in der Bildverarbeitung. Das Lösen solcher Probleme ist äußerst schwierig da die Zielfunktion sehr oft nicht-differenzierbar und die Anzahl der Unbekannten üblicherweise sehr groß ist. Standardalgorithmen wie zum beispiel Gradientenabstieg oder Newton fallen daher aus. In letzter Zeit sah man ein vermehrtes Interesse an so-genannten proximal-artigen Methoden. Obwohl bereits in den Siebzigerjahren entwickelt, wurden diese Methoden revitalisiert, gerade weil sie sehr gut mit großen nicht-glatten Problemen umgehen können. Obwohl im Prinzip langsamer als zum Beispiel hochegezüchtete Innere Punkte Methoden, erlaubt Ihre Einfachheit eine Implementierung auf hochgradig parallelen Architekturen wie zum Beispiel GPUs. Dies kann zu einer drastischen Leistungssteigerung führen, üblicherweise ein Faktor von 30 oder mehr. Kürzlich veröffentlichte Ergebnisse deuten darauf hin, dass eine spezielle Klasse von proximal- artigen Methoden - so genannte primal-duale Algorithmen der ersten Ordnung - sehr vielversprechend sind. Zum einen sind diese Algorithmen auf eine vernünftig große Klasse von strukturierten konvexen Problemen anwendbar und zum anderen scheinen diese Algorithmen besonders gut geeignet zum Lösen von großen nicht-glatten Problemen zu sein. Trotz ihrer guten Leistung gibt es aber immer noch viele offene Probleme, welche gelöst werden müssen um die Algorithmen weiter verbessern zu können. Interessante Fragestellungen beinhalten die optimale Vorkonditionierung, die optimale Beschleunigung auf glatteren Problemen und die Anwendbarkeit auf sehr große Probleme. Das Beantworten dieser Fragestellungen würde bedeuten dass man noch größere Probleme in noch kürzerer Zeit lösen kann, was wiederum bedeuten würde, dass Wissenschaftler noch komplexere und daher realistischere Modelle untersuchen können.

Das Hauptziel des EANOI-Projekts bestand darin, eine langjährige Forschungskooperation zwischen den beiden Gruppen von Thomas Pock an der Technischen Universität Graz und Antonin Chambolle an der Ecole Polytechnique, Palaiseau, Frankreich, weiter zu etablieren und zu stärken. Die Hauptforschungsrichtung war die Entwicklung von numerischen Optimierungsalgorithmen für verschiedene Probleme in der Bildverarbeitung und Computer Vision. Dazu gehören wichtige Probleme wie Bildrestauration, Bildsegmentierung, Bildrekonstruktion, Stereo, optischer Fluss und vieles mehr. Das Ziel des Projekts war es, diese Felder weiter zu beforschen sowie auch Studenten in diesen Bereichen auszubilden. Optimierung ist ein weit verbreitetes Thema, aber ihre Anwendung auf bildbezogene Probleme erfordert die Entwicklung spezialisierter Methoden, die mit der großen Anzahl von Optimierungsvariablen (Sehr oft im Bereich von vielen Millionen) und mit der nicht glatten Struktur der Optimierungsprobleme umgehen können. In solchen Fällen ist es einfach unmöglich, hochgezüchtete Löser aus kommerziellen Softwarepaketen anzuwenden, und daher muss man auf einfachere Methoden wie gradientenbasierte Algorithmen zurückgreifen. Ein wichtiges und "heißes" Thema in der Large-Scale Optimierung ist daher, solche einfachen gradientenbasierten Verfahren hinsichtlich ihrer numerischen Effizienz zu verbessern (oder zu beschleunigen). Die Hauptergebnisse des EANOI-Projekts sind wie folgt: (i) Wir analysierten das allgemeine Konvergenzverhalten eines Primal-DualAlgorithmus erster Ordnung zur Lösung von nicht glatten Optimierungsproblemen mit bekannter Sattelpunktstruktur. (ii) Wir bewiesen Konvergenz der Iterationen einer wichtigen beschleunigten proximalen Gradientenmethode, bekannt als FISTA. (iii) Wir analysierten sogenannte inertiale Gradientenmethoden sowohl für konvexen als auch für nicht-konvexe Optimierungsprobleme, die zu einer wesentlich schnelleren Konvergenz führen, während die Komplexität des Algorithmus im Wesentlichen unverändert bleibt. (iv) Wir veröffentlichten in der Zeitschrift "Acta Numerica", die eine der renommiertesten Zeitschriften auf dem Gebiet der numerischen Mathematik ist, eine langes Review über kontinuierliche Optimierung in der Bildverarbeitung.