Die effiziente Lösung von Optimierungsproblemen ist eine zentrale Aufgabe im maschinellen Lernen und im größeren Gebiet der Datenwissenschaften. Deshalb entwickeln wir GENO (generic optimization), eine domänenspezifische Sprache (DSL) zur Generierung von Lösungssoftware für verschiedene Optimierungsprobleme aus einfachen Spezifikationen. Eine wichtige Komponente von GENO ist ein Matrixkalkül zur Berechnung von symbolischen Ableitungen mathematischer Ausdrücke. 

Aufbauend auf dem Matrixcalculus haben wir jetzt einen Algorithmus zur Überprüfung der Konvexität von Optimierungsproblemen entwickelt. Für konvexe Optimierungsprobleme sind alle lokalen Minima auch globale Minima. Die Information, ob ein Problem konvex ist oder nicht, ist von Interesse, da die von GENO erzeugte Lösungssoftware nur für konvexe Probleme immer ein globales Minimum berechnet. Für nicht-konvexe Probleme wird ein lokales Minimum berechnet, von dem man nicht sagen kann, wie viel schlechter es ist als das globale Minimum. 

Links: Eine konvexe Funktion mit einem eindeutigen lokalen Minimum, das einfach zu berechnen ist, z.B. durch lokale Suchstrategien. Rechts: Eine nicht-konvexe Funktion mit zwei lokalen Minima. Das globale Minimum ist im Allgemeinen nicht einfach zu berechnen.    

Der neue Algorithmus ist aber nicht nur für GENO interessant. Mithilfe des Algorithmus konnten wir neue Klassen von Funktionen als konvex zertifizieren, die jetzt in Anwendungen verwendet werden können. 

Veröffentlichung: J. Klaus, N. Merk, K. Wiedom, S. Laue and J. Giesen. Convexity Certificates from Hessians. Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS 2022)