Investigating Degenerate Preconditioners for Proximal Point Algorithms
In this thesis, we consider and study fixed point iterations to solve monotone inclusion problems. Specifically, we consider proximal point algorithms that make use of preconditioners. We allow the preconditioners to be degenerate, which means that they might have a non-trivial kernel. The introduction of degenerate preconditioners raises various theoretical questions, some of which we address in this work. To establish the convergence of the sequence generated by the degenerate preconditioned proximal point algorithm, we adapt classical analysis to the degenerate case, imposing mild additional assumptions that do not hinder the practical applications of the method. Additionally, we demonstrate that the degeneracy of the preconditioner enables the reduction of the dimension of the space where the algorithm is defined, without loss of information between an iterate and the next. Furthermore, we provide a characterization of the involved operator for this new reduced scheme. In recent years, many classical proximal splitting schemes designed to tackle monotone inclusion problems featuring sums of multiple operators, have been identified as proximal point iterations. For this reason, we show the main application of the framework in the context of splitting algorithms. By incorporating degenerate preconditioners, we can encompass a broader range of splitting schemes, offering new insights and a unified convergence analysis for these methods. Examples of such algorithms include the Douglas- Rachford method, the Peaceman-Rachford method, the Chambolle-Pock algorithm, and the Davis-Yin method. As a further step, we leverage the generality of the framework to propose new generalizations for these splitting schemes. Specifically, we introduce graph extensions for both the Douglas-Rachford method and the Davis-Yin algorithm, studying their behavior, and drawing interesting relations between their performance and the structures of the employed graphs. In the last part of the thesis, we consider possible generalizations of the degenerate preconditioned proximal point algorithm. We first study a proximal point iteration with non-stationary degenerate preconditioners and investigate a specific application to the primal-dual Douglas-Rachford splitting. We thus introduce an inexact version of the algorithm, providing convergence analysis for scenarios where each iteration introduces an error generating a summable sequence, as well as for a novel degenerate inexact method with relative errors. We conclude by analyzing an inertial version of the method, providing some examples and a new restart strategy. These expansions of the algorithm result in generalizations for all the splitting schemes that are encompassed in the framework. We demonstrate the practical applications of these extensions and highlight their advantages.
In dieser Arbeit betrachten und untersuchen wir Fixpunktiterationen zur Lösung monotoner Inklusionsprobleme. Konkret betrachten wir Proximalpunkt-Algorithmen, die Präkonditionierer verwenden. Wir lassen zu, dass die Vorkonditionierer degeneriert sind, was bedeutet, dass sie einen Kern haben können. Die Einführung von degenerierten Vorkonditionierern wirft verschiedene theoretische Fragen auf, von denen wir einige in dieser Arbeit behandeln. Um die Konvergenz der Iterierten des degenerierten präkonditionierten Proximalpunkt-Algorithmus nachzuweisen, passen wir die klassische Analyse an den degenerierten Fall an, indem wir relativ schwache zusätzliche Annahmen, die die praktischen Anwendungen der Methode nicht behindern. Darüber hinaus zeigen wir, dass die Degeneriertheit des Vorkonditionierers die Verringerung der Dimension des Raums, in dem der Algorithmus definiert ist, ohne Informationsverlust zwischen einer Iteration und der nächsten ermöglicht. Darüber hinaus liefern wir eine Charakterisierung des beteiligten Operators für dieses neue reduzierte Verfahren. In den letzten Jahren wurden viele klassische Proximalsplitting-Verfahren, die zur Lösung von monotonen Inklusionsproblemen mit Summen mehrerer Operatoren entwickelt wurden, als Proximalpunkt-Iterationen identifiziert. Aus diesem Grund zeigen wir die Hauptanwendung
des Rahmens im Kontext von Splitting-Verfahren. Durch die Einbeziehung von degenerierten Vorkonditionierern können wir eine breitere Klasse von Splitting-Verfahren einbeziehen und so neue Einsichten und eine einheitliche Konvergenzanalyse für diese Verfahren bieten. Beispiele für solche Algorithmen sind das Douglas-Rachford-Verfahren, das Peaceman-Rachford-Verfahren, der Chambolle-Pock-Algorithmus und das Davis-Yin-Verfahren. In einem weiteren Schritt nutzen wir die Allgemeingültigkeit des Rahmens, um neue Verallgemeinerungen für diese Splitting-Verfahren vorzuschlagen. Insbesondere führen wir graphenbasierte Erweiterungen sowohl für die Douglas-Rachford-Methode als auch für den Davis-Yin-Algorithmus ein, untersuchen ihr Verhalten und stellen interessante Beziehungen zwischen ihrer Performance und den Strukturen der verwendeten Graphen her. Im letzten Teil der Arbeit betrachten wir mögliche Verallgemeinerungen des degenerierten vorkonditionierten Proximalpunkt-Algorithmus. Wir untersuchen zunächst eine Proximalpunktiteration mit nicht-stationären degenerierten Vorkonditionierern und untersuchen eine spezifische Anwendung auf das primal-duale Douglas-Rachford-Splitting. Wir führen dann eine inexakte Version des Algorithmus ein und liefern eine Konvergenzanalyse für Szenarien, in denen jede Iteration einen Fehler einführt, der eine summierbare Sequenz erzeugt, sowie für eine neuartige entartete inexakte Methode mit relativen Fehlern. Abschließend analysieren wir eine inertiale Version des Verfahrens mit einigen Beispielen und einer neuen Restart-Strategie. Diese Erweiterungen des Algorithmus führen folglich zu Verallgemeinerungen für alle Splitting-Verfahren, die in dem Rahmenwerk enthalten sind. Wir demonstrieren die praktischen Anwendungen dieser Erweiterungen und heben ihre Vorteile hervor.
Preview
Rights
Use and reproduction:
Access Statistic
