Detailansicht

Numerical algorithms for structured nonsmooth and nonconvex optimization problems

Dang-Khoa Nguyen

Art der Arbeit

Dissertation

Universität

Universität Wien

Fakultät

Fakultät für Mathematik

Studiumsbezeichnung bzw. Universitätlehrgang (ULG)

Doktoratsstudium NAWI aus dem Bereich Naturwissenschaften (DissG: Mathematik)

Betreuer*in

Radu Ioan Bot

Volltext herunterladen
Volltext in Browser öffnen

DOI

10.25365/thesis.69688

URN

urn:nbn:at:at-ubw:1-11111.62824.566971-1

Link zu u:search

(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract

(Deutsch)

Viele Anwendungen können als Optimierungsprobleme formuliert werden. Diese Modelle sind in der Regel hochdimensional, komplex strukturiert und weisen Merkmale wie Nichtglattheit und Nichtkonvexität auf, für deren Behandlung spezielle Lösungsmethoden erforderlich sind. Solche numerische Algorithmen sind, aufgrund ihrer Einfachheit und geringen Iterations- und Speicherkosten, vorzugsweise Verfahren erster Ordnung. Des weitern liegt unser Hauptaugenmerk auf sogenannten full splitting Verfahren, was bedeutet, dass jedes Element, das an der Formulierung des zugrunde liegenden Optimierungsproblems beteiligt ist, separat und auf effiziente Weise ausgewertet wird. Der Hauptzweck dieser Arbeit ist die Formulierung und Untersuchung der Konvergenzeigenschaften solcher Algorithmen für verschiedene nicht glatte Optimierungsprobleme, die von konvexen bilevel bis hin zu strukturierten nicht-konvexen Problemen reichen. Wir konzentrieren uns insbesondere auf die Untersuchung des Konvergenzverhaltens der entwickelten Algorithmen und in einigen Situationen auf ihre Konvergenzrate. Nach einer Einleitung stellen wir Grundbegriffe und Ergebnisse der konvexen Analysis, der maximalmonotonen Operatoren, der Variations- und der nicht-glatten Analysis vor, die für die Arbeit relevant sind. Ferner schlagen wir ein Forward-Backward-Splitting Verfahren der penalty Art mit Inertialeffekten für ein komplex strukturiertes monotones Inklusionsproblem vor. Dies bietet einen allgemeine Rahmen zur Lösung konvexer bilevel Minimierungsprobleme. Die letzten drei Kapitel der Arbeit befassen sich mit dem Entwurf und der Analyse von Algorithmen für nicht-glatte und nicht-konvexe Optimierungsprobleme. Sie teilen das Merkmal, dass zusammen mit der Konvergenzanalyse der Teilfolgen die globalen Konvergenz- und Konvergenzraten unter der Kurdyka- Lojasiewicz-Eigenschaft diskutiert werden. In diesem Zusammenhang schlagen wir zunächst einen projizierten Gradientenalgorithmus zur Faktorisierung einer vollständig positiven Matrix mit Parametern vor, die die Auswirkungen von Relaxation und Inertia berücksichtigen. Dann betrachten wir die proximale und die proximale linearisierte Version der alternating direction method of multipliers für ein nicht-glattes und nicht-konvexes Optimierungsproblem, das Hintereinanderausführungen mit linearen Operatoren beinhaltet. Schließlich entwickeln wir einen proximalen Ansatz für nicht glatte Probleme mit Blockstruktur, die durch eine glatte Funktion gekoppelt sind.

Abstract

(Englisch)

A large number of applications in real-world can be formulated and designed as optimization problems. These models are usually large-scale, complexly structured, and exhibit features like nonsmoothness and nonconvexity, which require specific solution methods when addressing them. Such numerical algorithms are preferable first-order methods, due to their simplicity and low iteration and memory storage costs, but also to be formulated in a full splitting spirit, meaning that every element involved in the formulation of the underlying optimization problem is evaluated separately and in an efficient way. The main purpose of this thesis is to formulate and investigate the convergence properties of full splitting algorithms for different nonsmooth optimization problems, ranging from bilevel convex to structured nonconvex. We focus in particular on the study of the convergence behavior of the developed algorithms and, in some situations, on their rate of convergence. In the preliminaries, we introduce basic notions and results of convex analysis, maximal monotone operators, variational and nonsmooth analysis, which are of relevance for the thesis. Further, we propose a forward-backward splitting algorithm of penalty type with inertial effects for a complexly structured monotone inclusion problem, which provides a general setting for solving convex bilevel minimization problems. The last three chapters of the thesis are dedicated to the design and analysis of algorithms for nonsmooth and nonconvex optimization problems. They share the feature that, along with the subsequence convergence analysis, the global convergence and converge rates are discussed in the setting of the Kurdyka- Lojasiewicz property. In this context, we first propose a projected gradient algorithm for the factorization of a completely positive matrix with parameters that take into account the effects of relaxation and inertia. Then we consider the proximal and the proximal linearized alternating direct on method of multipliers for a nonsmooth and nonconvex optimization problem involving compositions with linear operators. Finally, we develop a proximal approach for nonsmooth problems with block structure coupled by a smooth function.

Autor*innen

Dang-Khoa Nguyen

Haupttitel (Englisch)

Numerical algorithms for structured nonsmooth and nonconvex optimization problems

Paralleltitel (Deutsch)

Numerische Algorithmen für strukturierte nicht-glatte und nicht-konvexe Optimierungsprobleme

Publikationsjahr

2020

Umfangsangabe

132 Seiten

Sprache

Englisch

Beurteiler*innen

Guoyin Li ,

Hedy Attouch

Klassifikationen

31 Mathematik > 31.76 Numerische Mathematik ,

31 Mathematik > 31.80 Angewandte Mathematik

AC Nummer

AC16260545

Utheses ID

59247

Studienkennzahl

UA | 796 | 605 | 405 |

Detailansicht

Abstracts

Schlagwörter