Lösung großer konischer Programme mithilfe augmentierter primal-dualer Funktionen
Fachliche Zuordnung
Mathematik
Förderung
Förderung von 2007 bis 2011
Projektkennung
Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 60557008
Erstellungsjahr
2011
Zusammenfassung der Projektergebnisse
Ausgangspunkt des Projektes war die Beobachtung, dass die Lösung eines hochdimensionalen konvexen konischen Programms
(P ) minimiere | Ax = b¯, x ∈ K,
welches die Slaterbedingung erfüllt, als Schnitt einer affinen Mannigfaltigkeit L+z^0 mit einem konvexen Kegel K = K × K^D im primal-dualen Raum dargestellt werden kann, wobei die Projektionen auf L und K oft wesentlich billiger zu berechnen sind, als eine Iteration eines Innere-Punkte-Verfahrens.
Schränkt man die primal-duale Variable z = (x, s) auf den Grundraum L + z^0 ein, so ergibt sich die Lösung zopt von (P ) durch Minimierung des Quadrats φ des Abstandes zu K (in L + z^0 ). Dabei lässt sich der Gradient von φ mit obigen Projektionen berechnen. Für semidefinite Programme konnte eine Funktion f identifiziert werden, die ebenfalls in zopt ihr globales Minimum annimmt, und für die φ + f eine quadratische Wachstumsbedingung (“second order growth condition”) in zopt erfüllt. Es zeigte sich, dass dies aber nicht bedeutet, dass die verallgemeinerte Hessematrix im Minimalpunkt positiv definit ist. Für eine modifizierte Funktion f konnte die positive Definitheit in diesem Projekt in einem allgemeineren Rahmen nachgewiesen werden.
Ein wichtiger Teil des Projektes war die Implementierung, die wesentlich verbessert und auf Optimierungsprobleme über dem doppelt nichtnegativen Kegel erweitert wurde. Als überzeugendste Variante stellte sich ein Ansatz heraus, bei dem zunächst via des obigen Zugangs eine Näherungslösung ermittelt wird und ausgehend von dort mit dem QMR-Verfahren das linearisierte System (nach AHO) der Optimalitätsbedingungen gelöst wird. Wesentlich dabei ist, dass die Gleichungen so eliminiert und umgestellt werden können, dass sich ein strukturiertes indefinites aber symmetrisches System ergibt. Durch Umgehung eines nichtnormalen Systems konnte so die Anzahl der Iterationen reduziert werden; gleichzeitig halbierte sich der Aufwand pro Iteration durch Ausnutzung der Symmetrie ohne dass (wie bei den sonst üblichen Normalengleichungen) die Konditionszahl quadriert wurde.
Es gibt nach unserem Wissen derzeit weder Implementierungen, die hochdimensionale Programme über dem doppelt nichtnegativen Kegel befriedigend lösen können noch solche, die hochdimensionale semidefinite Programme mit hoher Rechengenauigkeit lösen können. Die hier entwickelte Software füllt diese Lücke.
Projektbezogene Publikationen (Auswahl)
- On the computation of C* certificates. Journal of Global Optimization Volume 45 Issue 2, October 2009
Katrin Schmallowsky, Florian Jarre
