Eine neuartige Ableitung und Lösungsmethodik zweiter Ordnung für nichtglatte Optimierung

• Antragsteller: Dr. Bennet Gebken
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 545166481

In vielen Anwendungen treten Optimierungsprobleme mit nichtglatten Zielfunktionen auf. Es gibt mehrere gängige Methoden für die Lösung solcher Probleme, die auf Ableitungsinformationen erster Ordnung, wie dem Clarke Subdifferential, und linearen Modellen der Zielfunktion basieren. Da sie allerdings nur lineare Modelle verwenden, besitzen diese Verfahren höchstens lineare Konvergenzordnung. In der glatten Optimierung gibt es bekannte Lösungsverfahren basierend auf zweiten Ableitungen (wie das Newton-Verfahren), die eine höhere Konvergenzordnung erreichen. Es stellt sich daher die Frage, ob solche Verfahren auch für nichtglatte Probleme konstruiert werden können. Zwar gibt es schon Verfahren, die das Verhalten des Newton-Verfahrens im nichtglatten Fall nachahmen und die in numerischen Beispielen Spuren superlinearer Konvergenz zeigen, allerdings sind theoretische Aussagen über deren Konvergenzordnung fast nicht existent. Das Ziel dieses Projekts ist die Entwicklung einer neuen Lösungsmethodik zweiter Ordnung für nichtglatte Optimierungsprobleme, die die schnelle Konvergenz existierender Methoden höherer Ordnung mit einem theoretischen Fundament in der nichtglatten Analysis verbindet. Als Ableitung zweiter Ordnung wird der Second-order Epsilon-Jet genutzt, der die Koeffizienten aller (existierender) Taylor-Entwicklungen zweiter Ordnung in einem Epsilon-Ball um einen gegebenen Punkt enthält. Basierend darauf wird das Maximum dieser Taylor-Entwicklungen als Modell der Zielfunktion verwendet. Durch iteratives Konstruieren und Minimieren dieses Modells wird ein simples, abstraktes Lösungsverfahren für nichtglatte Optimierung erzeugt. Um eine praktisch implementierbare Methode zu erhalten, wird der Epsilon-Jet durch ein deterministisches Sampling-Verfahren approximiert. Die Methode kann daher als Second-order Gradient Sampling Methode interpretiert werden. In einem kürzlichen Preprint habe ich bereits die Idee dieses Verfahrens und numerische Tests präsentiert, die darauf hindeuten, dass es oft schneller ist, gemessen in Anzahl an Funktionsauswertungen, als andere Verfahren höherer Ordnung. Die entscheidenden theoretischen und praktischen Fragen wurden allerdings noch nicht behandelt, was das Ziel dieses Projekts ist. Allem voran muss die Theorie des Verfahrens weiterentwickelt werden. Insbesondere werden ein Konvergenzbeweis für den nichtkonvexen Fall und eine theoretische Analyse zur Konvergenzordnung benötigt. Darüber hinaus muss die Effizienz des Verfahrens verbessert werden. Momentan benötigt die Methode exakte Hessematrizen, die in der Praxis oft schwer zu berechnen sind. Die Effizienz wird auch dadurch geschwächt, dass bisher kein spezialisierter Löser für die Minimierung des quadratischen Modells konstruiert wurde. Schlussendlich muss die Praxistauglichkeit des Verfahrens untersucht werden. Dazu gehören ein gründlicherer Vergleich zu anderen Verfahren höherer Ordnung und die Anwendung auf praxisnahe Problemklassen.

• DFG-Verfahren: WBP Stelle