Glättungsverfahren für semidefinite Programme
In dieser Arbeit werden Algorithmen zur Lösung von linearen semidefiniten Programmen beschrieben. Unter einer geeigneten Regularitätsvoraussetzung ist ein semidefinites Programm äquivalent zu seinen Optimalitätsbedingungen. Die Optimalitätsbedingungen bzw. die Zentralen-Pfad-Bedingungen überführen wir zunächst durch matrixwertige NCP-Funktionen in ein nichtlineares Gleichungssystem. Dieses nichtlineare und teilweise nicht differenzierbare Gleichungssystem lösen wir dann mit einem Newton-ähnlichen Verfahren. Durch die Umformulierung in ein nichtlineares Gleichungssystem muss während der Iteration nicht mehr explizit die positive (Semi-)Definitheit der beteiligten Matrizen beachtet werden. Weiter wird gezeigt, dass dieser Ansatz im Gegensatz zu Inneren-Punkte-Methoden sofort symmetrische Suchrichtungen erzeugt. Um globale Konvergenz zu erhalten, werden verschiedene Globalisierungsstrategien (Schrittweitenbestimmung, Trust-Region-Ansatz) untersucht. Für das betrachtete Prädiktor-Korrektor-Verfahren und das Trust-Region-Verfahren wird lokal superlineare Konvergenz unter strikter Komplementarität und Nichtdegeneriertheit gezeigt. Die theoretische Untersuchung eines nichtglatten Newton-Verfahrens liefert ein lokal quadratisches Konvergenzverhalten ohne strikte Komplementarität, wenn die Nichtdegeneriertheitsvoraussetzung geeignet modifiziert wird.
Semidefinite Programme, Newton-Verfahren, Glättungsverfahren, NCP-Funktionen, semidefinite programming, Newton's method, smoothing-type methods, NCP-functions
Networked Digital Library of Theses and Dissertations