Algorithm Engineering für Generische Löser für Konvexe Optimierungsprobleme
Zusammenfassung der Projektergebnisse
Ziel dieses Projekts war es einen Solver Generator zu entwickeln, der basierend auf der mathematischen Beschreibung eines Optmierungsproblems, automatisch einen Solver für diese Klasse von Optimierungsproblemen erzeugt. Dafür haben wir eine einfache und allgemeine Theorie für das Berechnen von Ableitungen für Matrix- und Tensorfunktionen entwickelt, die darüber hinaus auch noch praktisch nutzbar ist. Obwohl dieses ein sehr fundamentales Problem ist, existierte eine solche Theorie bisher nicht. Der sich daraus ergebende Algorithmus ist zentraler Bestandteil dieses Projekts. Da wir der Meinung waren, dass diese Methode auch für andere Wissenschaftler von Interesse ist, haben wir sie unter www.MatrixCalculus.org als ein Webtool öffentlich zugänglich gemacht. Die Ausdrücke für Ableitungen von vektor- und matrixwertigen Funktionen, die unser Ansatz erzeugt, können im Vergleich zu anderen aktuellen Methoden bis zu drei Größenordnungen schneller ausgewertet werden. Mit diesem Ansatz kann das von uns in diesem Projekt entwickelte Modellierungsmodul kompakte Ausdrücke für Gradienten, Jacobi- und Hesse-Matrizen generieren, die von generischen Solvern für Optimierungsprobleme genutzt werden können. In einem Proof of Concept konnten wir den Solver Generator GENO (GENeric Optimization) entwickeln. Die automatisch erzeugten Solver zeigen großes Potential für erhebliche Effizienzsteigerungen im Vergleich zum aktuellen Stand der Forschung. Eine online Version ist unter www.geno-project.org nutzbar.
Projektbezogene Publikationen (Auswahl)
-
Deducing individual driving preferences for user-aware navigation. International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL), 2016
Stefan Funke, Sören Laue, Sabine Storandt
-
Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees. Symposium on Experimental Algorithms (SEA), 2017
Stefan Funke, Sören Laue, Sabine Storandt
-
Computing Higher Order Derivatives of Matrix and Tensor Expressions. Advances in Neural Information Processing Systems (NeurIPS), 2018
Sören Laue, Matthias Mitterreiter, Joachim Giesen
-
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. IEEE/ACM Trans. Netw. 26(2): 920-933, 2018
Thomas Bläsius, Tobias Friedrich, Anton Krohmer, Sören Laue
-
Dynamic pseudo-time warping of complex single-cell trajectories. International Conference on Research in Computational Molecular Biology (RECOMB), 2019
Van Hoan Do, Mislav Blazevic, Pablo Monteagudo, Luka Borozan, Khaled Elbassioni, Sören Laue, Francisca Rojas Ringeling, Domagoj Matijevic and Stefan Canzar
-
GENO – GENeric Optimization for Classical Machine Learning. Advances in Neural Information Processing Systems (NeurIPS), 2019
Sören Laue, Matthias Mitterreiter, Joaching Giesen
-
MatrixCalculus.org – Computing Derivatives of Matrix and Tensor Expressions. European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML), 2019
Sören Laue, Matthias Mitterreiter, Joaching Giesen
-
On the Equivalence of Forward Mode Automatic Differentiation and Symbolic Differentiation. arXiv, 2019
Sören Laue
-
Using Benson’s Algorithm for Regularization Parameter Tracking. Conference on Artificial Intelligence (AAAI), 2019
Joachim Giesen, Sören Laue, Andreas Löhne, Christopher Schneider
-
Visualization Support for Developing a Matrix Calculus Algorithm: A Case Study. EG/VGTC Conference on Visualization (EUROVIS), 2019
Joachim Giesen, Julien Klaus, Sören Laue, Ferdinand Schreck
-
A Simple and Efficient Tensor Calculus. Conference on Artificial Intelligence (AAAI), 2020
Sören Laue, Matthias Mitterreiter, Joaching Giesen
-
GENO – Optimization for Classical Machine Learning Made Fast and Easy. Conference on Artificial Intelligence (AAAI), 2020
Sören Laue, Matthias Mitterreiter, Joaching Giesen
