Dokument: Numerical Treatment of Nonlinear Semidefinite Programs

Titel:	Numerical Treatment of Nonlinear Semidefinite Programs
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=3652
URN (NBN):	urn:nbn:de:hbz:061-20070227-135547-3
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Vogelbusch, Christoph [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 759,6 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 09.02.2007 / geändert 09.02.2007
Beitragende:	Prof. Dr. Jarre, Florian [Gutachter] Prof. Dr. Ratschek, Helmut [Gutachter]
Stichwörter:	nichtlinear, semidefinit, SDP, NLSDP, SSP, , IPM, Innere Punkte Methodenonlinear, semidefinite, SDP, NLSDP, SSP, SQP,
Dewey Dezimal-Klassifikation:	500 Naturwissenschaften und Mathematik » 510 Mathematik
Beschreibungen:	Die Arbeit behandelt das Lösen von nichtlinearen Semidefiniten Programmen (SDP). Wir Analysieren ein Verfahren namens SSP, das von dem SQP-Verfahren abgeleitet wurde. Dieses Verfahren approximiert ein nichtlineares SDP durch eine Reihe von quadratischen Programmen (im Englischen sequential quadratic programming = SSP). In der Anwendung werden für diese quadratischen Programme mit lineare SDP Lösern verwendet. Der quadratische Term kann als semidefinite Kegelbedingung aufgefasst werden, wenn dieser Term positive semidefinit ist. In dieser Arbeit wird gezeigt, dass der Term in nicht notwendiger weise positiv semidefinit sein muss und dass für eine positiv semidefinite Approximation das SSP Verfahren nur noch linear konvergiert. Die Implementierung, die zu dieser Arbeit erstellt wurde, zeigt, das das SSP Verfahren trotz der schlechten lokalen Konvergenz eine gute globale Konvergenz hat. Das weitere ziel der Arbeit ist es, diese Implementierung um einen schnellen lokalen Löser zu ergänzen. Als schnellen lokalen Löser stellen wir eine Innere Punkte Methode (IPM) vor. Der vorgestellte Prädiktor-Korrektor Algorithmus löst die gleiche klasse von Problemen, wie das SSP Verfahren. Wir zeigen die Ähnlichkeiten zwischen dem SSP und dem IPM Ansatz und die Unterschiede, die es ermöglichen, dass die IPM lokal quadratisch Konvergieren kann. Zusätzlich zu den theoretischen Untersuchungen, wird im Kapitel über die Implementierung eine neue Schrittweitenkontrolle vorgestellt, der „erweiterte Filter“. In this thesis we consider nonlinear SDP (semidefinite programs). We analyze a SQP-like approach called SSP. This approach approximates the solution by a sequence of simpler quadratic semidefinite programs. Thus the name sequential semidefinite programs (SSP). In practical applications the subproblems of this approach are solved with linear semidefinite problem solvers. Such solvers need a positive semidefinite approximation of the Hessian of the Lagrangian. We prove local linear convergence when using such a positive semidefinite approximation. Our SSP implementation showed a fast global convergence behavior for the examples we focused on. This implementation also enables us to build a hybrid global/local solver. As a fast local solver for a hybrid approach we present an IPM (interior point method) algorithm. This predictor-corrector approach solves the same class of problems as the SSP algorithm. We show similarities between the SSP and IPM steps and that local quadratic convergence is possible with this algorithm. In addition to the discussion of the two solvers, this thesis also introduces a new step length control called augmented filter. In our numerical experiments this approach converged in less steps than the standard filter approach and does not discard any search steps. Using the calculated search step is highly desirable as for nonlinear SDPs search steps are often very expensive to calculate.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Mathematik
Dokument erstellt am:	02.02.2007
Dateien geändert am:	12.02.2007
Promotionsantrag am:	31.01.2007
Datum der Promotion:	31.01.2007