Halbglatte Newton-Verfahren für ausgewählte Anwendungen

Kürzlich haben wir zwei Strategien zur Globalisierung von halbglatten Newton-Verfahren für konvex- quadratische Optimierungsprobleme mit Box-Bedingungen entwickelt. Diese Probleme treten als eine wesentliche Basiskomponente in vielen Anwendungen auf, beispielsweise im Kontext sequentieller quadratischer Optimierungsverfahren oder auch in den Bereichen mathematische Physik und Informatik. Unsere neuen Ansätze haben eine Reihe von wünschenswerten Eigenschaften wie Einfachheit (keine Tuning- Parameter, einfache Implementierung) und das Finden der exakten numerischen Lösung. Wir demonstrierten, dass unsere Methoden auf einem vielfältigen Benchmark-Set bessere Rechenzeiten liefern als andere verfügbare Verfahren und somit aktuell die besten Methoden für diese Problemklasse darstellen. Mit dem Erwin-Schrödinger-Auslandsstipendium möchten wir unsere Algorithmen in mehrere Richtungen erweitern. Während unseres Forschungsaufenthalts bei Prof. Pablo Parrilo am Institut für Technologie Massachusetts planen wir unsere Verfahren auf nicht-negative Matrixfaktorisierung, L1-Norm Minimierung und deren Kombination, die nicht-negativen dünnen Verschlüsselung, anzuwenden. Unsere Hauptforschungsfrage lautet: Kann die starke praktische Leistung unserer Methoden auf Ansätze zur Lösung dieser Anwendungen übertragen werden? Erste Tests zeigen, dass eine erfolgreiche Erweiterung unserer Verfahren für diese Anwendungen sehr wahrscheinlich und auf Grund der Wichtigkeit der Anwendungen auch sehr wertvoll ist. Kürzlich haben wir auch eine Kombination von erweiterten Langrange-Verfahren mit unseren oben beschriebenen neuen Methoden zur Lösung von allgemeinen konvex-quadratischen Optimierungsproblemen untersucht. Diese sind neben den linearen Optimierungsproblemen wohl eine der wichtigsten Klassen von Optimierungsproblemen. Erste Experimente zeigen eine sehr vielversprechende Performance unseres Verfahrens auf großen Instanzen. Aber bisher fehlt unserer Methode eine vollständige Konvergenztheorie, das heißt ein Beweis, dass unser Ansatz für alle Instanzen immer die optimale Lösung liefert. Die detaillierte Untersuchung von Projektionen auf Polytope ist für die Entwicklung einer solchen Konvergenzheorie notwendig. Während die Entwicklung einer Konvergenztheorie sehr anspruchsvoll ist, wäre die Bedeutung einer Erweiterung unserer sehr schnellen Methode auf allgemeine konvex-quadratische Probleme sehr hoch. Pablo Parrilo ist ein Experte in den oben beschriebenen Gebieten. Daher profitiert die Umsetzung der vorgeschlagenen Forschungsideen von seiner Expertise. Im Rahmen des Forschungsvorhabens sollen also einerseits unsere neuen Methoden in vorhandene Frameworks eingebaut werden und somit zur schnelleren Lösung vieler relevanter Anwendungen in den Bereichen Compressed Sensing, Gesichtserkennung, Clustering, Computer Vision, Signalverarbeitung und Bioinformatik beitragen. Der Komplexitätsgrad dieses Vorhabens ist gut abschätzbar und die erfolgreiche Umsetzung ist sehr wahrscheinlich. Andererseits wollen wir unsere Verfahren für allgemeine konvex-quadratische Optimierungsprobleme erweitern. Die Komplexität der dafür notwendigen theoretischen mathematischen Resultate ist sehr hoch. Gelingt jedoch die Erweiterung ist es gut möglich, dass unsere Methoden Innere-Punkte-Verfahren als Standardansatz für allgemeine konvex-quadratische Optimierungsprobleme ablösen könnten. Dies wäre eine bedeutende Errungenschaft mit sehr hohem Neuigkeitsgrad.

Wir haben zwei Strategien zur Globalisierung von halbglatten Newton-Verfahren für konvex- quadratische Optimierungsprobleme mit Box-Bedingungen entwickelt. Diese Probleme treten als eine wesentliche Basiskomponente in vielen Anwendungen auf, beispielsweise im Kontext sequentieller quadratischer Optimierungsverfahren zur Lösung allgemeiner nicht- linearer Probleme oder auch in den Bereichen mathematische Physik und Informatik. Unsere neuen Ansätze sind rein kombinatorisch und haben eine Reihe von wünschenswerten Eigenschaften wie Einfachheit (keine Tuning-Parameter), das Finden der exakten numerischen Lösung, Unempfindlichkeit bezüglich Initialisierung und einfache Implementierung. Wir demonstrierten, dass unsere halbglatten Newton-Verfahren auf einem großen und vielfältigen Benchmark-Set bessere Rechenzeiten liefern als projizierte Gradienten-Verfahren, projizierte Quasi-Newton-Verfahren und verschiedene Aktive- Mengen-Methoden. Im Rahmen meines Erwin-Schrödinger-Auslandsstipendium bei Prof. Pablo Parrilo am Institut für Technologie Massachusetts haben wir versucht unsere Algorithmen für konvex-quadratische Optimierungsprobleme mit Box-Bedingungen in einige Richtungen erweitern. Zunächst haben wir unsere Verfahren (mit notwendigen Anpassungen, z.B. Strategien zum Ausnützen der speziellen Struktur der Zielfunktion) auf nicht-negative Matrixfaktorisierung und L1-Norm Minimierung angewandt. Wenn man L1-Regularisierung mit nicht-negativer Matrixfaktorisierung kombiniert, erhält man das Problem der nicht- negativen dünnen Verschlüsselung. Zur Lösung dieses Problem kann eine Kombination von halbglatten Newton-Verfahren für nicht-negative Matrixfaktorisierung und L1-Norm Minimierung genutzt werden. Wir mussten jedoch für alle drei Problemklassen anhand einer Reihe von computergestützten Experimenten auf entsprechenden Testinstanzen feststellen, dass unsere Methoden keine Verbesserungen gegenüber den besten, für die jeweiligen Problemklassen spezialisierten Algorithmen darstellen konnten. Stattdessen konnten wir jedoch zeigen, dass sich unsere Methoden, inklusive ihrer Konvergenztheorie, auf das Lineare Komplementaritätsproblem (mit beidseitigen Schranken),daseine Verallgemeinerungvon konvex-quadratischen Optimierungsproblemen mit Box-Bedingungen darstellt, erweitern lassen und für diese Problemklasse die benötigte Rechenzeit gegenüber den besten bisher in der Literatur bekannten Algorithmen auf einer großen, vielfältigen Menge an Testinstanzen deutlich reduzieren. Linearer Komplementaritätsprobleme sind für die Lösung vieler Anwendungen essentiell, wiebeispielsweise beiBimatrixspielen, Markt- und Verkehrsgleichgewichtsmodellen, Optionsbewertungen, Portfoliomodellenund elastoplastischen Strukturanalysen.