Dokument: Lösung großer konischer Programme mit Hilfe primal-dualer Methoden
| Titel: | Lösung großer konischer Programme mit Hilfe primal-dualer Methoden | |||||||
| Weiterer Titel: | Solving large-scale conic programs using primal-dual methods | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=21826 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20120709-111243-8 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Deutsch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Davi, Thomas [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Jarre, Florian [Gutachter] Univ.-Prof. Dipl.-Ing. Dr. Rendl, Franz [Gutachter] | |||||||
| Dewey Dezimal-Klassifikation: | 500 Naturwissenschaften und Mathematik » 510 Mathematik | |||||||
| Beschreibungen: | Sei ein reeller endlichdimensionaler Hilbertraum $(E,\langle . , . \rangle )$ gegeben.
Wir betrachten ein konisches Programm von der Form $$ \textrm{minimiere} \ \ \langle c,x \rangle \mid x \in (\calL + b) \cap \calK. \leqno(P) $$ Hierbei seien $\calL\subseteq E$ ein Unterraum, $\calK \subseteq E$ ein nicht-leerer, konvexer und abgeschlossener Kegel und $b,c \in E$ . Eine Vielzahl von Problemstellungen in Wirtschaft und Wissenschaft kann durch konische Programme beschrieben werden. Wichtige Spezialf\"alle sind lineare (mit $E=\re^n$ und $\calK=\re_+^n$) und semidefinite Programme (mit $E=\calS^n$ und $\calK=\calSp^n$). F\"ur beide Klassen existieren viele effiziente L\"osungsmethoden, solange die Dimension der Probleme nicht zu gro\ss \ wird. Eine schwieriger zu handhabende Klasse sind die doppelt nichtnegativen Programme (mit $E=\calS^n$ und $\calK=\calSp^n\cap\{X \geq 0\}$). Mit ihnen werden u.a. Probleme in der Graphentheorie gel\"ost. Im Gegensatz zu linearen und semidefiniten Programmen ist der Kegel in diesem Fall nicht selbstdual. Zun\"achst widmet sich die Arbeit allgemeinen konischen Programmen der Form $(P)$ und den zugeh\"origen dualen Programmen $(D)$. Es wird eine Umformulierung der beiden Programme betrachtet, die es erm\"oglicht alle L\"osungen des Paares $(P)$ und $(D)$ als Schnittmenge eines affinen Raumes $\bfA$ und eines Kegels $\bfK$ im Raum $E\times E$ darzustellen. Anschlie\ss end \ wird die APD-Methode zur L\"osung von konischen Programmen besprochen. Im Wesentlichen wird bei dieser Methode ausgehend von $\bfA$ der Abstand zum Kegel $\bfK$ minimiert. Der Spezialfall der semidefiniten Programme wird genauer untersucht: Die APD-Methode wird f\"ur diese Problemklasse analysiert. Weiterhin wird auf eine Regularisierung eingegangen, welche das Konvergenzverhalten des APD-Verfah- rens verbessern soll. Schlie\ss lich werden hochdimensionale Programme in Bezug auf Speicherbedarf und Rechenaufwand besprochen. Es werden zwei Erweiterungen des APD-Verfahrens betrachtet: Zun\"achst wird das verallgemeinerte Newton-Verfahren diskutiert. Danach wird das AHO-QMR-Verfahren beschrieben. Dabei handelt es sich um ein iteratives Verfahren, welches mit Hilfe der QMR-Methode die aus den Innere-Punkte-Methoden bekannte AHO-Richtung approximiert. Hierbei wird das zu l\"osende Gleichungssystem zun\"achst symmetrisiert. Neben einer ausf\"uhrlichen Beschreibung der notwendigen Umformulierungsschritte werden auch numerische Ergebnisse pr\"asentiert. Schlie\ss lich wird auf den doppelt nichtnegativen Kegel und die zugeh\"origen konischen Programme eingegangen. Es wird zun\"achst eine \"aquivalente selbstduale Formulierung angegeben und untersucht, wie sich die APD- und die AHO-QMR-Methode auf diese Formulierung anwenden lassen. Anschlie\ss end werden Regularit\"atsbedingungen f\"ur das Ausgangsproblem betrachtet, die die Konvergenz der APD- und AHO-QMR-Methode zur L\"osung der selbstudalen Programme verbessern. Abschlie\ss end werden numerische Ergebnisse angegeben.Let $(E,\langle . , . \rangle )$ be a real finite-dimensional Hilbert space. Consider a conic program of the form $$ \textrm{minimize} \ \ \langle c,x \rangle \mid x \in (\calL + b) \cap \calK. \leqno(P) $$ Here, $\calL\subseteq E$ is a linear subspace, $\calK \subseteq E$ a non-empty, convex and closed cone and $b,c \in E$ given data. A broad variety of economic and scientific problems can be described by conic programs. Important special cases are linear ($E=\re^n$ and $\calK=\re_+^n$) and semidefinite programs ($E=\calS^n$ and $\calK=\calSp^n$). For both cases, when the problem size is not ''too large'', there are many efficient problem-solving approaches. A somewhat more difficult case are doubly nonnegative programs ($E=\calS^n$ and $\calK=\calSp^n\cap\{X \geq 0\}$). They are used for solving problems in graph theory, for example. In contrary to linear and semidefinite programs, the cone is not selfdual in this case. First, the thesis focuses on general conic programs of the form $(P)$ and the corresponding dual programs $(D)$. A reformulation of both programs, which allows to represent the solution of the pair $(P)$ and $(D)$ as the intersection of an affine space $\bfA$ and a cone $\bfK$ in $E\times E$, is considered. Next, the APD-Method for solving conic programs is discussed. Basically, starting from $\bfA$ the distance to $\bfK$ is minimized in this method. The special case of semidefinite programs is investigated. The APD-Method is analyzed for this problem class. Furthermore, a regularization to speed up convergence of the APD-Method is discussed. Finally, high dimensional programs are considered. Following, two extensions of the APD-Method are examined: An application of the generalized Newton-Method and the AHO-QMR-Method. The latter one is an iterative method, which uses the QMR-algorithm to approximate the AHO-direction known from interior point methods. Here, the system of equations to be solved is symmetrized at first. A detailed description of all necessary reformulation steps and numerical results are reported. Finally, the thesis focuses on the doubly nonnegative cone and the corresponding conic programs. First, an equivalent selfdual formulation is described. Then, a generalization of the APD- and AHO-QMR-Method for this formulation is considered. Furthermore, regularization conditions for the initial problem are presented, which guarantee an improved convergence of the APD- and AHO-QMR-Method for solving the selfdual formulation. Concluding, several numerical results are stated. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Mathematik » Mathematische Optimierung | |||||||
| Dokument erstellt am: | 09.07.2012 | |||||||
| Dateien geändert am: | 09.07.2012 | |||||||
| Promotionsantrag am: | 26.04.2012 | |||||||
| Datum der Promotion: | 05.07.2012 |
