MultistageSP

Mehrstufige stochastische Optimierung

Beschreibung

Dieses Projekt verfolgt einen neuen Ansatz zur Lösung großer mehrstufiger stochastischer Optimierungsprobleme. Der Zugang verallgemeinert bereits bestehende Algorithmen, die sich in der nichtlinearen optimalen Steuerung als sehr effizient erwiesen haben.

Die üblichen primalen und dualen Dekompositionsmethoden zerlegen mehrstufige Probleme in kleinere Optimierungsprobleme, die den Knoten oder Pfaden des Szenario-Baumes zugeordnet sind. Die entstehenden vertikalen oder horizontalen Kopplungsbedingungen werden iterativ behandelt, wobei in jeder Iteration die lokalen Probleme unabhängig gelöst werden.

Der neue rekursive Ansatz behandelt das Optimierungsproblem global durch primal-duale Innere-Punkt-Methoden (ggf. als QP-Löser in SQP-Methoden) und nutzt die Struktur des Szenario-Baumes auf der Ebene der linearen Algebra durch rekursives Lösen der linear-indefiniten KKT-Systeme. Bei iterativer Behandlung der Ungleichungsrestriktionen und ggf. weiterer Nichtlinearitäten wird hier die vertikale und horizontale Kopplung der einzelnen Knoten stets explizit berücksichtigt. Eine Beschleunigung der Konvergenz wird erreicht durch eine Warm-Start-Technik, die zunächst eine grobe Approximation des Problems löst und den Szenario-Baum dann sukzessive verfeinert.

Verschiedene Varianten des Algorithmus sind als Klassenbibliotheken in C++ implementiert. Eine problemspezifische Implementierung wird erfolgreich zur Lösung quadratischer finanzmathematischer Probleme bei einer Schweizer Versicherungsgesellschaft eingesetzt. Schließlich wurde ein Softwaretool zur automatischen Erzeugung problemspezifischer Solver-Implementierungen entwickelt.

Ansprechpartner

• Dr. Marc C. Steinbach

Mitarbeiter

• Dr. Marc C. Steinbach

Dauer