Verfahren in der Optimierung mit disjunktiven Restriktionen

Ziel des Projekts ist, effiziente numerische Verfahren für eine Klasse von Optimierungsproblemen mit disjunktiven Restriktionen zu entwickeln. Beispiele für solche Restriktionstypen sind Variationsungleichungen oder Gleichgewichtsnebenbedingungen bzw. sogenannte "verschwindende Nebenbedingungen". Die Konvergenz bestehender Algorithmen kann nur unter sehr starken Voraussetzungen gezeigt werden bzw. es kann nur Konvergenz zu Punkten gezeigt werden, in denen möglicherweise noch triviale Abstiegsrichtungen existieren. Basierend auf neuen Lösungskonzepten, die der Antragsteller kürzlich entwickelte und die ihre Grundlage in verallgemeinerten Differenzierungstechniken haben, sollen global konvergente Verfahren entwickelt werden, deren Konvergenz unter schwachen Voraussetzungen garantiert werden kann. Weiters sollen auch superlineare Konvergenzeigenschaften und das Verhalten im degenerierten Fall analysiert werden. Das neue Verfahren soll eine ähnlich Struktur wie die bekannten SQP-Verfahren der nichtlinearen Optimierung besitzen: In einem Iterationsschritt wird eine quadratische Zielfunktion, die aus einer Näherung der Hessematrix der Lagrangefunktion und dem Gradienten der Zielfunktion gebildet wird, über den linearisierten Restriktionen minimiert. Der bei der Lösung dieses Hilfsproblems gefundene Lösungspfad wird verfolgt, bis ein hinreichender Abstieg für eine geeignete Hilfsfunktion gefunden wurde.

In diesem Projekt wurden effiziente numerische Verfahren für eine Klasse von Optimierungsproblemen mit disjunktiven Restriktionen entwickelt. Ein Beispiel für solche Restriktionen sind Variationsungleichungen oder Gleichgewichts-nebenbedingungen, wie sie bei 2-Ebenen Optimierungsproblemen (Stackelberg-Games) vorkommen. Ein anderes typisches Beispiel sind sogenannte verschwindende Nebenbedingungen die bei der Optimierung von Fachwerken auftreten.Durch diese disjunktiven Restriktione besitzen die Optimierungsprobleme eine kombinatorische Struktur, für deren exakte Losung nur aufwändige Enumerationstechniken bekannt sind. Da der Zeitaufwand dieser Enumerationstechniken exponentiell mit der Anzahl der disjunktiven Restriktionen wächst, ist dieser Zugang nur für relativ kleine Probleme machbar.Die praktische Berechnung globaler Losungen ist ab einer gewissen Problemgröße nahezu unmöglich ist, und daher beschränkt man sich üblicherweise auf das Auffinden von lokalen Losungen bzw. stationären Punkten, d.h. Punkte, die gewisse Optimalitätsbedingungen erfüllen.Die Konvergenz bestehender Algorithmen kann nur unter sehr starken Voraussetzungen gezeigt werden bzw. es kann nur Konvergenz zu Punkten gezeigt werden, in denen möglicherweise noch triviale Abstiegsrichtungen existieren und die daher sicher keine lokalen Lösungen sind.In diesem Projekt wurden nun, basierend auf neuen Losungskonzepten, die ihre Grundlage in verallgemeinerten Differenzierungstechniken haben, global konvergente Verfahren zur Lösung von Optimierungsproblemen mit disjunktiven Restriktionen entwickelt. In jedem Iterationsschritt wird dabei ein quadratisches Hilfsproblem mit linearen disjunktiven Restriktionen mit Hilfe eines neuartigen effizienten Algorithmus gelost. Schlüsselpunkt sind dabei neuartige Optimalitätsbedingungen, die es erlauben, die inhärente kombinatorische Struktur des Hilfsproblems aufzulösen. Der neue Iterationspunkt ergibt sich dann aus einer Suche entlang eines polygonalen Pfads der sich aus der Losung des Hilfsproblems resultiert. Numerische Tests belegen die Effizienz und Zuverlässigkeit der neuen Methode.