Distributed Optimization of Constraint-Coupled Systems via Approximations of the Dual Function
- This thesis deals with the distributed optimization of constraint-coupled systems. This problem class is often encountered in systems consisting of multiple individual subsystems, which are coupled through shared limited resources. The goal is to optimize each subsystem in a distributed manner while still ensuring that system-wide constraints are satisfied. By introducing dual variables for the system-wide constraints the system-wide problem can be decomposed into individual subproblems. These resulting subproblems can then be coordinated by iteratively adapting the dual variables. This thesis presents two new algorithms that exploit the properties of the dual optimization problem. Both algorithms compute a quadratic surrogate function of the dual function in each iteration, which is optimized to adapt the dual variables. The Quadratically Approximated Dual Ascent (QADA) algorithm computes the surrogate function by solving a regression problem, while the Quasi-Newton Dual Ascent (QNDA) algorithm updates the surrogate function iteratively via a quasi-Newton scheme. Both algorithms employ cutting planes to take the nonsmoothness of the dual function into account. The proposed algorithms are compared to algorithms from the literature on a large number of different benchmark problems, showing superior performance in most cases. In addition to general convex and mixed-integer optimization problems, dual decomposition-based distributed optimization is applied to distributed model predictive control and distributed K-means clustering problems.
- Diese Arbeit befasst sich mit der verteilten Optimierung von Restriktions-gekoppelten Systemen. Diese Problemklasse tritt häufig in Systemen auf, die aus mehreren einzelnen Teilsystemen bestehen, die durch geteilte begrenzte Ressourcen gekoppelt sind. Das Ziel ist es, jedes Teilsystem verteilt zu optimieren und gleichzeitig sicherzustellen, dass die systemübergreifenden Restriktionen eingehalten werden. Durch die Einführung dualer Variablen für die systemübergreifenden Restriktionen kann das systemweite Problem in seine einzelne Teilprobleme zerlegt werden. Diese resultierenden Teilprobleme können dann durch iterative Anpassung der dualen Variablen koordiniert werden. In dieser Arbeit werden zwei neue Algorithmen vorgestellt, die die Eigenschaften des dualen Optimierungsproblems ausnutzen. Beide Algorithmen bestimmen in jeder Iteration eine quadratische Surrogatfunktion der dualen Funktion, die zur Anpassung der dualen Variablen optimiert wird. Der Quadratically Approximated Dual Ascent (QADA) Algorithmus bestimmt die Surrogatfunktion durch die Lösung eines Regressionsproblems, während der Quasi-Newton Dual Ascent (QNDA) Algorithmus die Surrogatfunktion iterativ über ein Quasi-Newton-Schema aktualisiert. Beide Algorithmen verwenden Schnittebenen, um die Nichtdifferenzierbarkeit der dualen Funktion zu berücksichtigen. Die vorgeschlagenen Algorithmen werden mit Algorithmen aus der Literatur für eine große Anzahl verschiedener Benchmark-Probleme verglichen und zeigen in den meisten Fällen ein besseres Konvergenzverhalten. Zusätzlich zu generischen konvexen und gemischt-ganzzahligen Optimierungsproblemen wird die verteilte Optimierung basierend auf dualer Zerlegung auf verteilte modellprädiktive Regelungs- und verteilte K-Means Clustering-Probleme angewendet.
Author: | Vassilios YfantisORCiD |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-76992 |
DOI: | https://doi.org/10.26204/KLUEDO/7699 |
Advisor: | Martin RuskowskiORCiD, Sebastian EngellORCiD |
Document Type: | Doctoral Thesis |
Cumulative document: | No |
Language of publication: | English |
Date of Publication (online): | 2024/02/26 |
Year of first Publication: | 2024 |
Publishing Institution: | Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau |
Granting Institution: | Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau |
Acceptance Date of the Thesis: | 2024/02/20 |
Date of the Publication (Server): | 2024/02/27 |
Tag: | ADMM; Bundle Methods; Constraint-Coupled Systems; Convex Optimization; Distributed Optimization; Dual Decomposition; Federated Learning; Mixed-integer Programming; Model Predictive Control; Nonsmooth Optimization; Quadratic Approximation; Quasi-Newton Methods; Subgradient |
Page Number: | XVI, 183 |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Maschinenbau und Verfahrenstechnik |
CCS-Classification (computer science): | G. Mathematics of Computing |
DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
MSC-Classification (mathematics): | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
PACS-Classification (physics): | 00.00.00 GENERAL |
Licence (German): | Creative Commons 4.0 - Namensnennung (CC BY 4.0) |