Detailansicht
High-dimensional nonsmooth convex optimization via optimal subgradient methods
Masoud Ahookhosh
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 (Dissertationsgebiet: Mathematik, IK: Computational Optimization)
Betreuer*in
Arnold Neumaier
DOI
10.25365/thesis.39947
URN
urn:nbn:at:at-ubw:1-30476.80161.436659-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In den letzten Jahrzehnten hat die konvexe Optimierung enorme Aufmerksamkeit erhalten und sich aufgrund ihres reichen theoretischen Rahmens sowie der rechnerischen Zuverlaessigkeit sehr rasch entwickelt. Die iterativen Verfahren in der konvexen Optimierung basieren typischerweise auf Informationen nullter, erster oder zweiter Ordnung ueber die Zielfunktion. Dabei bilden Informationen erster Ordnung (Funktionswerte und Subgradienten) die meistversprechenden Methoden zum Loesen von hoch dimensionalen oder big data Problemen. Unter diesen Methoden bieten sich sogenannte Subgradienten-Methoden an, da diese eine einfache Form haben und mit allgemeinen konvexen Problemen umgehen koennen, ohne dabei die Struktur des Problems zu beruecksichtigen (im Gegensatz zu Optimierungsmethoden, die auf proximalen Punkten basieren oder solchen vom Nesterov-Typ). Der Nachteil dieser Subgradienten-Verfahren ist jedoch, dass sie zu langsam sind, um reale Probleme, die in Technik oder angewandter Wissenschaft auftreten, effektiv loesen zu koennen.
Motiviert durch den Bedarf an schnellen und zuverlaessigen Methoden fuer das Loesen von allgemeinen nicht-glatten konvexen Optimierungsproblemen wurden im Zuge dieser Arbeit spezielle Subgradienten-Verfahren entwickelt, die zum einen die optimale Komplexitaet von bekannten Verfahren erster Ordnung haben und zum anderen schnell genug sind, um hoch-dimensionale und big data -Anwendungs-probleme loesen zu koennen. Das neue Subgradienten-Verfahren (OSGA) beruht auf den Loesbarkeit eines
nicht-konvexen Teilproblems. In dieser Arbeit wird gezeigt, dass man dieses Teilproblem fuer unbeschraenkte (multi-term affine zusammengesetzte Funktionen, sowie Zielfunktionen, die kostenintensive lineare Operatoren beinhalten) und einfach beschraenkte Probleme (auf einfachen Gebieten mit effektiver Projektion), sowie Probleme beschraenkt durch einfache Funktionen (Sublevel set von einfachen konvexen Funktionen) effizient loesen kann. Wenn zusaetzlich die Nicht-Glattheit der Zielfunktion in einer passenden Struktur formuliert ist, kann eine neue Subgradienten-Methode, die ebenfalls hier vorgestellt wird, eine Komplexitaet von $O(\epsilon^{-1/2})$ erreichen, welche dem optimalen Aufwand fuer glatte Probleme mit Lipschitz-stetigen Gradienten entspricht.
Numerische Ergebnisse und Vergleiche mit anderen state-of-the-art-Verfahren werden in dieser Arbeit anhand von verschiedenen interessanten Anwendungsproblemen praesentiert. OSGA wurde als Software-Paket veroeffentlicht und ist fuer die Nutzung zu akademischen Zwecken frei verfuegbar.
Abstract
(Englisch)
Over the past few decades, convex optimization has obtained tremendous attention and grown very quickly due to providing a rich theoretical framework and computationally reliable and tractable schemes. Designing iterative schemes in convex optimization are typically based of zero-, first-, or second-order information of the objective. The first-order information (function values and subgradients) has a reputation of providing the most promising schemes for solving problems involving high-dimensional or big data. Among first-order methods, the subgradient methods have a simple form and can deal with general convex optimization (without considering the structure of problems, in contrast to proximal-based and Nesterov-type optimal methods). However, they are too slow to be able handling real-life problems appearing in applied sciences and engineering.
In this thesis, motivated by the need for fast and reliable methods to solve general nonsmooth convex optimization, we develop some subgradient methods obtaining the optimal complexity of first-order methods that are known to be fast enough to deal with applications involving high-dimensional or big data. More specifically, the novel subgradient framework (OSGA) depends on solving efficiently a related nonconvex subproblem. We show that this subproblem can be solved efficiently for unconstrained (multi-term affine composite functions and objective involving costly linear operators), simply constrained (bound-constrained and simple domains with available projection), and simply functional constrained (sublevel set of simple convex function) problems. In addition, if the nonsmoothness of the objective is manifested in an appropriately structured form, a novel optimal subgradient method is presented that can attain the complexity $O(\eps^{-1/2})$, the same optimal complexity as for smooth problems with Lipschitz continuous gradients.
OSGA is released as a software package available freely for academic use. Numerical results and comparisons with state-of-the-art schemes regarding a number of interesting problems in application are reported.
Schlagwörter
Schlagwörter
(Englisch)
Convex optimization Nonsmooth optimization Sparse optimization Subgradient methods Optimal complexity First-order methods High-dimensional data
Schlagwörter
(Deutsch)
Konvexe Optimierung Nicht-glatten Optimierung Sparse Optimierung Subgradienten-Verfahren Optimale Komplexitaet Verfahren erster Ordnung hoch-dimensionale data
Autor*innen
Masoud Ahookhosh
Haupttitel (Englisch)
High-dimensional nonsmooth convex optimization via optimal subgradient methods
Paralleltitel (Deutsch)
Hoch-dimensionale nicht-glatten konvexe Optimierung über optimale Subgradienten-Verfahren
Publikationsjahr
2015
Umfangsangabe
XIV, 188 S. : Ill., graph. Darst.
Sprache
Englisch
Beurteiler*innen
Marko Mäkelä ,
Iourii Nesterov
Klassifikationen
31 Mathematik > 31.76 Numerische Mathematik ,
31 Mathematik > 31.80 Angewandte Mathematik
AC Nummer
AC12717137
Utheses ID
35392
Studienkennzahl
UA | 796 | 605 | 405 |