Algorithm Engineering für Generische Löser für Konvexe Optimierungsprobleme

• Antragsteller: Professor Dr.-Ing. Sören Laue
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 253965656

• Erstellungsjahr: 2020

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
  (Siehe online unter https://doi.org/10.1145/2996913.2997004)
• Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees. Symposium on Experimental Algorithms (SEA), 2017
  Stefan Funke, Sören Laue, Sabine Storandt
  (Siehe online unter https://doi.org/10.4230/LIPIcs.SEA.2017.18)
• 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
  (Siehe online unter https://doi.org/10.1109/TNET.2018.2810186)
• 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
  (Siehe online unter https://doi.org/10.1101/522672)
• 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
  (Siehe online unter https://doi.org/10.1007/978-3-030-46133-1_48)
• 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
  (Siehe online unter https://doi.org/10.1609/aaai.v33i01.33013689)
• 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
  (Siehe online unter https://doi.org/10.1111/cgf.13694)
• A Simple and Efficient Tensor Calculus. Conference on Artificial Intelligence (AAAI), 2020
  Sören Laue, Matthias Mitterreiter, Joaching Giesen
  (Siehe online unter https://doi.org/10.1609/aaai.v34i04.5881)
• GENO – Optimization for Classical Machine Learning Made Fast and Easy. Conference on Artificial Intelligence (AAAI), 2020
  Sören Laue, Matthias Mitterreiter, Joaching Giesen
  (Siehe online unter https://doi.org/10.1609/aaai.v34i09.7097)