Dokument: Projection Based Methods for Conic Linear Programming — Optimal First Order Complexities and Norm Constrained Quasi Newton Methods
| Titel: | Projection Based Methods for Conic Linear Programming — Optimal First Order Complexities and Norm Constrained Quasi Newton Methods | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=46942 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20180906-082702-8 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Lieder, Felix [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Jarre, Florian [Gutachter] Prof. Dr. Dür, Mirjam [Gutachter] Prof. Dr. Kanzow, Christian [Gutachter] | |||||||
| Stichwörter: | conic programs, Krasnoselski-Mann iteration, tight worst-case complexity, norm constrained quasi Newton method | |||||||
| Dewey Dezimal-Klassifikation: | 500 Naturwissenschaften und Mathematik » 510 Mathematik | |||||||
| Beschreibung: | This thesis is devoted to solving linear conic optimization problems via (accelerated) projection based algorithms. Making use of the existing duality theory and Moreau’s theorem, we reformulate the sufficient optimality conditions via the nonexpansive gradient of a reduced Lagrangian function, whose zeros are in a one to one relationship with the optimal solutions of the initial problem. The reduced Lagrangian is nonconvex and therefore the zeros generally are saddle points. We proceed by investigating first order methods to tackle this saddle point problem: A simple unitary transformation of the gradient is firmly nonexpansive allowing the application of standard fixed point methods. The analysis of these methods leads to the first main contribution of this thesis, which is the development of a general concept for analyzing convergence rates of fixed point methods for Lipschitz continuous mappings in an optimal fashion, resulting in unimprovable complexity estimates. Specifically we derive a novel mathematical toolbox for obtaining optimal worst-case complexities, which is exemplarily used to establish the optimal worst-case complexity of the so-called Krasnoselski-Mann (KM) iteration with fixed step length in real Hilbert spaces. Furthermore we address applications in designing fixed step methods with optimized worst-case or average-case complexity as well as extensions to complex spaces. These first order methods are then complemented by second order methods, leading to the second main contribution of this thesis: The design of a norm constrained limited memory quasi Newton method, which in combination with the KM iteration resulted in a competitive software package written in MATLAB. This limited memory quasi Newton method uses a (low dimensional) semidefiniteness constraint for the correction and a least-squares approach to determine the information to be dropped from memory. We perform numerical experiments on a variety of problems, including semidefinite (SDP) and doubly non-negative (DNN) programs, which mostly arise from relaxations of NP-hard problems. First the fixed point approach is applied to about 80 large scale SDP/DNN test problems and it proves to be very competitive for these problems. Finally a combination with the novel norm constrained limited memory quasi Newton method leads to a further acceleration of our implementation. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Mathematik » Mathematische Optimierung | |||||||
| Dokument erstellt am: | 06.09.2018 | |||||||
| Dateien geändert am: | 06.09.2018 | |||||||
| Promotionsantrag am: | 01.06.2018 | |||||||
| Datum der Promotion: | 31.08.2018 |
