Nichtkonvexe Quadratische Optimierung unter Unsicherheit

Optimierungsprobleme bestehen darin, Entscheidungen über bestimmte Größen (Eingaben) zu treffen, um ein bestimmtes Ergebnis (Ausgabe) zu optimieren. Um etwa ein gutes Anlageportfolio zu entwerfen, das den Ertrag (Ausgabe) maximiert, muß man wissen, wieviel man in jede einzelne Aktie investiert, zu welchem Zeitpunkt investiert wird usw., und zudem auswählen, welche Aktien in das Portfolio aufgenommen werden. Zwei große Schwierigkeiten treten bei der Optimierung hier auf: Nichtkonvexität und Unsicherheit. Konvexe Probleme sind vergleichbar mit der Suche nach dem tiefsten Punkt in einem Tal oder einer Badewanne: eine nach unten rollende Murmel wird schließlich den tiefsten Punkt finden. Nichtkonvexe Probleme hingegen sind wie die Suche nach dem tiefsten Punkt in der Sahara: Die Murmel bleibt vielleicht in einer Senke stecken, die tiefer ist als der Ausgangspunkt aber ist sie die tiefste Senke? Man müßte erst alle anderen Täler untersuchen! Deshalb sind nichtkonvexe Probleme wesentlich schwieriger als konvexe. Das klassische Portfolio-Optimierungsproblem ist ein einfaches konvexes Problem. Beschränken wir jedoch die Anzahl der Aktien im Portfolio, wird das Problem nichtkonvex: wählt man 100 Aktien aus 1000 verfügbaren aus, übersteigt die Zahl der möglichen Kombinationen bereits die Anzahl der Atome im Universum und für jede Kombination muß man die optimalen Investitionsanteile bestimmen. Die zweite Schwierigkeit ist die Unsicherheit. Kennen wir nicht alle relevanten Daten präzise, so läßt sich etwa die Rendite einer Aktie nur ungenau vorhersagen. Wenn wir ihre Verteilung (mögliche Szenarien und deren Wahrscheinlichkeiten) kennen, können wir so optimieren, daß wir im Durchschnitt gut abschneiden. In realistischen Modellen echter Unsicherheit ist die Szenarienanzahl jedoch riesig. Wenn künftige Anpassungen (unter neuen Daten) einer Entscheidung berücksichtigt werden müssen (zweistufige Entscheidungen), wird es noch schwieriger: die optimalen Entscheidungen in jedem Szenario sind wichtig, aber auch, wie sich diese auf künftige Handlungsoptionen auswirken, bei nichtkonvexen Problemen eine besondere Herausforderung. Die sogenannte kopositive Optimierungstheorie ermöglicht eine Umwandlung nichtkonvexer Probleme in konvexe allerdings um den Preis vieler zusätzlicher Variablen und weiterer Schwierigkeiten. Dadurch können wir jedoch viele Werkzeuge der konvexen Optimierung nutzen. Etwa läßt sich ein großes Problem in kleine Teilprobleme zerlegen, deren Lösung man anschließend zu einer Lösung des Gesamtproblems zusammensetzen kann ohne Konvexität im Allgemeinen unmöglich. Die Details dieses an sich einfachen Ansatzes sind komplex: problemspezifisches Wissen, die Art der Unsicherheit und die Vorteile des kopositiven Ansatzes sind zu kombinieren. Ziel dieses Projekts ist es, effiziente Algorithmen für eine schwierige Klasse unsicherer, nichtkonvexer Optimierungsmodelle zu entwickeln, flexibel genug, um viele reale Probleme zu bewältigen.