Christian Nagel

• 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 einIn 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.…
• In this thesis we consider algorithms to compute a solution of linear semidefinite programs. Under a suitable regularity condition a semidefinite program is equivalent to its optimality conditions. These optimality conditions, or central-path-conditions, are reformulated as a nonlinear system of equations via matrix-valued NCP-functions. This nonlinear and partly nonsmooth system of equations is solved with a Newton-type method. Because of the reformulation as a nonlinear system of equations, we do not need the iterates to be positiveIn this thesis we consider algorithms to compute a solution of linear semidefinite programs. Under a suitable regularity condition a semidefinite program is equivalent to its optimality conditions. These optimality conditions, or central-path-conditions, are reformulated as a nonlinear system of equations via matrix-valued NCP-functions. This nonlinear and partly nonsmooth system of equations is solved with a Newton-type method. Because of the reformulation as a nonlinear system of equations, we do not need the iterates to be positive (semi-)definite. Moreover, this reformulation automatically computes symmetric search directions, in contrast to interior point methods. To obtain global convergence, different globalizations (line search, trust-region) are considered. For the predictor-corrector method and the trust-region-method global and local superlinear convergence is shown under strikt complementarity and nondegeneracy. The theoretical investigation of a nonsmooth version of Newton's methods yields locally quadratic convergence without strict complementarity if the nondegeneracy conditon is modified in a suitable way.…