Detailansicht
Accelerated schemes via an asymptotically vanishing damping for convex optimization and monotone inclusions
David Alexander Hulett
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doktoratsstudium Naturwissenschaften: Mathematik
Betreuer*in
Radu Ioan Bot
DOI
10.25365/thesis.80803
URN
urn:nbn:at:at-ubw:1-12914.23565.364613-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In dieser Arbeit untersuchen wir die asymptotischen Eigenschaften bestimmter dynamischer Systeme (d. h. zeitkontinuierlicher Methoden oder Verfahren) und bestimmter numerischer Algorithmen (d. h. zeitdiskreter Methoden oder Verfahren) im Zusammenhang mit konvexen Optimierungsproblemen und monotonen Inklusionsproblemen. Genauer gesagt untersuchen wir im Rahmen eines realen Hilbert-Raums: i) die Verbindung zwischen der Heavy-Ball-Dynamik und der beschleunigten Nesterov-Gradientendynamik sowohl im Optimierungs- als auch im monotonen Operator-Kontext; ii) ein System zweiter Ordnung im Zusammenhang mit einem Inklusionsproblem mit maximal monotoner+kokoerzitiver Struktur; iii) ein primalduales dynamisches System zweiter Ordnung im Zusammenhang mit einem linear beschränkten konvexen Minimierungsproblem; und iv) zwei Algorithmen zur Lösung eines hierarchischen Minimierungsproblems, d. h. der Minimierung einer äußeren Funktion in Abhängigkeit von der Menge der Minimierer einer inneren Funktion, wobei sowohl die innere als auch die äußere Funktion konvex sind und eine glatte+nichtglatte Struktur aufweisen. In jedem Fall leiten wir Konvergenzraten für die entsprechenden Objekte ab (z. B. die Norm des maßgeblichen Operators entlang der generierten Trajektorien oder Iterationen im monotonen Operator-Setting und die Funktionswerte entlang der Trajektorien oder Iterationen im Optimierungs-Setting) und stellen eine schwache Konvergenz der Trajektorien oder Iterationen in Richtung der Lösung des entsprechenden Problems fest. Schwache Konvergenz ist oft das Beste, was wir im Kontext eines (möglicherweise) unendlichdimensionalen Hilbert-Raums erwarten können. Im Mittelpunkt unserer Arbeit steht ein sogenannter asymptotisch verschwindender Koeffizient, der die Geschwindigkeit in unseren zeitkontinuierlichen Verfahren zweiter Ordnung dämpft. Werden solche Verfahren diskretisiert, resultieren sie in numerischen Algorithmen mit Impuls, d. h., wir berücksichtigen die durch das aktuelle und das vorherige Iterationsmuster definierte Richtung bei der Definition des neuen Iterationsmusters. Seit der bahnbrechenden Arbeit von Y. Nesterov aus dem Jahr 1983 ist bekannt, dass diese verschwindende Dämpfung nicht nur in der konvexen Optimierung, sondern auch in der monotonen Operatortheorie beschleunigende Effekte hat. Die von uns untersuchten Systeme und Algorithmen ergänzen die bereits vorhandenen Belege für die Nützlichkeit der Berücksichtigung einer solchen Dämpfung.
Abstract
(Englisch)
In this work, we explore the asymptotic properties of certain dynamical systems (i.e., continuous-time methods or schemes) and of certain numerical algorithms (i.e., discrete-time methods or schemes) attached to convex optimization problems and to monotone inclusion problems. More precisely, in the framework of a real Hilbert space, we study: i) the link which exists between the Heavy Ball dynamics and the Nesterov accelerated gradient dynamics, both in the optimization setting and in the monotone operator setting; ii) a second-order system attached to an inclusion problem with a maximally monotone+cocoercive structure; iii) a second-order primal-dual dynamical system attached to a linearly constrained convex minimization problem; and iv) two algorithms devised to solve a hierarchical minimization problem, that is, minimizing and outer function subject to the set of minimizers of an inner function, where both inner and outer functions are convex and have a smooth+nonsmooth structure. In every case, we derive convergence rates for the appropriate objects (e.g., the norm of the governing operator along the generated trajectories or iterates in the monotone operator setting, and the functional values along the trajectories or iterates in the optimization setting) and establish weak convergence of the trajectories or iterates towards solution of the corresponding problem. Weak convergence is often the best we can expect, in the context of a (possibly) infinite-dimensional Hilbert space. At the core of our work lies a so-called asymptotically vanishing coefficient which damps the velocity in our second-order continuous-time schemes. When such schemes are discretized, they result in numerical algorithms with momentum, that is, where we take into account the direction defined by the current and the previous iterate to define the new iterate. Ever since the seminal 1983 paper by Y. Nesterov, it has observed that this vanishing damping has accelerating effects not only in convex optimization, but also reaching into monotone operator theory. The systems and algorithms which we study add to the already considerable amount of evidence on the usefulness of considering such a damping.
Schlagwörter
Schlagwörter
(Deutsch)
Monotone Einschlüsse Konvexe Optimierung Konvergenzraten Konvergenz von Trajektorien Ljapunow-Analyse Asymptotisch verschwindende Dämpfung Aufspaltungssysteme Nesterow-beschleunigter Gradient Heavy Ball mit Reibung Bilevel-Optimierung
Schlagwörter
(Englisch)
Monotone inclusions Convex optimization Convergence rates Convergence of trajectories Lyapunov analysis Asymptotically vanishing damping Splitting systems Nesterov accelerated gradient Heavy Ball with friction Bilevel optimization
Autor*innen
David Alexander Hulett 
Haupttitel (Englisch)
Accelerated schemes via an asymptotically vanishing damping for convex optimization and monotone inclusions
Publikationsjahr
2025
Umfangsangabe
107 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*innen
Edouard Pauwels ,
Juan Peypouquet
Klassifikation
31 Mathematik > 31.49 Analysis. Sonstiges
AC Nummer
AC17827077
Utheses ID
78451
Studienkennzahl
UA | 796 | 605 | 405 |