Optimisation Problems with Sparsity Terms: Theory and Algorithms

Optimierungsprobleme mit Dünnbesetzten Termen: Theorie und Algorithmen

Please always quote using this URN: urn:nbn:de:bvb:20-opus-241955
  • The present thesis deals with optimisation problems with sparsity terms, either in the constraints which lead to cardinality-constrained problems or in the objective function which in turn lead to sparse optimisation problems. One of the primary aims of this work is to extend the so-called sequential optimality conditions to these two classes of problems. In recent years sequential optimality conditions have become increasingly popular in the realm of standard nonlinear programming. In contrast to the more well-known Karush-Kuhn-TuckerThe present thesis deals with optimisation problems with sparsity terms, either in the constraints which lead to cardinality-constrained problems or in the objective function which in turn lead to sparse optimisation problems. One of the primary aims of this work is to extend the so-called sequential optimality conditions to these two classes of problems. In recent years sequential optimality conditions have become increasingly popular in the realm of standard nonlinear programming. In contrast to the more well-known Karush-Kuhn-Tucker condition, they are genuine optimality conditions in the sense that every local minimiser satisfies these conditions without any further assumption. Lately they have also been extended to mathematical programmes with complementarity constraints. At around the same time it was also shown that optimisation problems with sparsity terms can be reformulated into problems which possess similar structures to mathematical programmes with complementarity constraints. These recent developments have become the impetus of the present work. But rather than working with the aforementioned reformulations which involve an artifical variable we shall first directly look at the problems themselves and derive sequential optimality conditions which are independent of any artificial variable. Afterwards we shall derive the weakest constraint qualifications associated with these conditions which relate them to the Karush-Kuhn-Tucker-type conditions. Another equally important aim of this work is to then consider the practicability of the derived sequential optimality conditions. The previously mentioned reformulations open up the possibilities to adapt methods which have been proven successful to handle mathematical programmes with complementarity constraints. We will show that the safeguarded augmented Lagrangian method and some regularisation methods may generate a point satisfying the derived conditions.show moreshow less
  • Die vorliegende Arbeit beschäftigt sich mit Optimierungsproblemen mit dünnbesetzten Termen, und zwar entweder in der Restriktionsmenge, was zu kardinalitätsrestringierten Problemen führen, oder in der Zielfunktion, was zu Optimierungsproblemen mit dünnbesetzten Lösungen führen. Die Herleitung der sogenannten sequentiellen Optimalitätsbedingungen für diese Problemklassen ist eines der Hauptziele dieser Arbeit. Im Bereich der nichtlinearen Optimierung gibt es in jüngster Zeit immer mehr Interesse an diesen Bedingungen. Im Gegensatz zu der mehrDie vorliegende Arbeit beschäftigt sich mit Optimierungsproblemen mit dünnbesetzten Termen, und zwar entweder in der Restriktionsmenge, was zu kardinalitätsrestringierten Problemen führen, oder in der Zielfunktion, was zu Optimierungsproblemen mit dünnbesetzten Lösungen führen. Die Herleitung der sogenannten sequentiellen Optimalitätsbedingungen für diese Problemklassen ist eines der Hauptziele dieser Arbeit. Im Bereich der nichtlinearen Optimierung gibt es in jüngster Zeit immer mehr Interesse an diesen Bedingungen. Im Gegensatz zu der mehr bekannten Karush-Kuhn-Tucker Bedingung sind diese Bedingungen echte Optimalitätsbedingungen. Sie sind also in jedem lokalen Minimum ohne weitere Voraussetzung erfüllt. Vor Kurzem wurden solche Bedingungen auch für mathematische Programme mit Komplementaritätsbedingungen hergeleitet. Zum gleichen Zeitpunkt wurde es auch gezeigt, dass Optimierungsproblemen mit dünnbesetzten Termen sich als Problemen, die ähnliche Strukturen wie mathematische Programme mit Komplementaritätsbedingungen besitzen, umformulieren lassen. Diese jüngsten Entwicklungen motivieren die vorliegende Arbeit. Hier werden wir zunächst die ursprunglichen Problemen direkt betrachten anstatt mit den Umformulierungen, die eine künstliche Variable enthalten, zu arbeiten. Dies ermöglicht uns, um Optimalitätsbedingungen, die von künstlichen Variablen unabhängig sind, zu gewinnen. Danach werden wir die entsprechenden schwächsten Constraint Qualifikationen, die diese Bedingungen mit Karush-Kuhn-Tucker-ähnlichen Bedingungen verknüpfen, herleiten. Als ein weiteres Hauptziel der Arbeit werden wir dann untersuchen, ob die gerade hergeleiteten Bedingungen eine praktische Bedeutung haben. Die vor Kurzem eingeführten Umformulierungen bieten die Möglichkeiten, um die für mathematische Programme mit Komplementaritätsbedingungen gut funktionierenden Methoden hier auch anzuwenden. Wir werden zeigen, dass das safeguarded augmented Lagrangian Method und einige Regularisierungsmethoden theoretisch in der Lage sind, um einen Punkt, der den hergeleiteten Bedingungen genügt, zu generieren.show moreshow less

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author: Andreas Budi Raharja
URN:urn:nbn:de:bvb:20-opus-241955
Document Type:Doctoral Thesis
Granting Institution:Universität Würzburg, Fakultät für Mathematik und Informatik
Faculties:Fakultät für Mathematik und Informatik / Institut für Mathematik
Referee:Prof. Dr. Christian Kanzow, Prof. Dr. Tim Hoheisel
Date of final exam:2021/06/14
Language:English
Year of Completion:2021
DOI:https://doi.org/10.25972/OPUS-24195
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
GND Keyword:Optimierungsproblem; Regularisierungsverfahren
Tag:Augmented Lagrangian; Cardinality Constraints; Regularisation Methods
MSC-Classification:49-XX CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Release Date:2021/07/28
Licence (German):License LogoCC BY-NC-SA: Creative-Commons-Lizenz: Namensnennung, Nicht kommerziell, Weitergabe unter gleichen Bedingungen 4.0 International