Dokument: Erweiterte Primal-Duale Verfahren für Lineare Programme und SOC Probleme
| Titel: | Erweiterte Primal-Duale Verfahren für Lineare Programme und SOC Probleme | |||||||
| Weiterer Titel: | Augmented Primal-Dual Methods for Linear Programs and SOC Problems | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=8335 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20080715-105322-0 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Schmallowsky, Katrin [Autor] | |||||||
| Dateien: |
| |||||||
| Dewey Dezimal-Klassifikation: | 500 Naturwissenschaften und Mathematik » 510 Mathematik | |||||||
| Beschreibung: | This thesis deals with linear conic programs
$$\hbox{minimize} \ \ c^Tx \ \ \hbox{s.t.} \ \ x\in\mathcal{K}\cap (\mathcal{L}+b), \leqno (P)$$ where $\mathcal{L}$ is an affine set and $\mathcal{K}$ is a closed, convex cone. We consider two choices for the cone $\mathcal{K}$, first the case that $\mathcal{K}$ is given by the positive orthant, i.e. $\mathcal{K}=\mathbb{R}^n_+$ and secondly that $\mathcal{K}$ is given as the second order cone $\mathcal{K}=\mathcal{Q}_n$. These problems are special cases of convex optimization problems.\\ In the first part, the equivalence of solving a linear program and the minimization of a convex, differentiable function $f$, which is piecewise quadratic on the space $\mathbb{R}^{n+m}$, is discussed. In this approach the affine set and the cone $\mathbb{R}^n_+$ are modelled by the function $f$. For the minimization of this function a generalized Newton method is used. To bound the number of iterations for this method, the properties of the conjugate function of $f$ are exploited.\\ This approach establishes a basis for the next part of this thesis. By linear transformations the function $f$ can be converted to a piecewise quadratic function in the primal-dual space. A closely related version of this function is considered in later chapters. First, the solution of perturbed linear second order cone programs is investigated, when the data is subject to arbitrary, but small changes. We then show that primal and dual nondegeneracy of linear second order cone programs is equivalent to uniqueness and strict complementarity of the optimal solution. Furthermore, the augmented primal-dual method is extended to linear second order cone programs.\\ In the third part of this thesis the implementation of the augmented primal-dual method is discussed. For large scale problems we have to observe the limited memory capacity, hence, a limited memory BFGS method is used. Finally, in an application of the preceeding results, we consider the cone of completely positive matrices $$\mathcal{C}_n^*=\left\{X\in\mathbb{R}^{n\times n}| X=\sum_{k\in K} v^k(v^k)^T \mbox{ for some finite }\{v^k\}_{k\in K}\in\mathbb{R}^n_+\right\}.$$ The question, whether a given matrix $B$ is in $\mathcal{C}_n^*$ or not, is an $\cal NP$-complete problem. We propose an algorithm that either computes a certificate proving that $B\in C^*$ or converges to a matrix $\bar{S}$ in $C^*$ which in some sense is ``close'' to $B$. We further introduce a regularization approach to improve the algorithm in cases, where convergence is not satisfactory. The thesis is completed with numerical results for the algorithms presented here. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Mathematik » Mathematische Optimierung | |||||||
| Dokument erstellt am: | 09.07.2008 | |||||||
| Dateien geändert am: | 09.07.2008 | |||||||
| Promotionsantrag am: | 05.06.2008 | |||||||
| Datum der Promotion: | 02.07.2008 |
