Nichtkonvexe Quadratische Minimierung: Theorie und Algorithmen

• Antragsteller: Professor Dr. David Russell Luke
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2019 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 434554779

Ziel der vorgeschlagenen Forschung ist es, eine vollständige Analyse des Verhaltens - von lokal bis global - von Algorithmen erster Ordnung für nicht konvexe und nicht glatte Optimierung mit quadratischer Struktur zu entwickeln. Die größere Wirkung der Forschung ist eine Synthese von zwei Stämmen der Analyse an der Quelle der wichtigsten Fortschritte in der Analyse von Algorithmen für nicht konvexe und nicht glatte Optimierung in den letzten zehn Jahren. Der erste ist die Verwendung der so genannten Kurdyka-Loyasiewicz (KL) Eigenschaft, die zentral ist, um globale Konvergenzergebnisse mit Komplexitätsschätzungen basierend auf Funktionswerten darzustellen. Die zweite ist basiert auf einer Verallgemeinerung der Prox-Regularität (Super-Regularität), zusammen mit der Regularität der Bedingungen an der Lösungsmenge (Transversalität) und wurde verwendet, lokale lineare Konvergenz der Fixpunkt Folge zu zeigen. Die erste Strategie, die global ist und auf jedes Optimierungsproblem mit semi-algebraischer Struktur angewendet werden kann, beginnt mit dem Zieloptimierungsproblem und geht weiter zu Algorithmen als Diskretisierungen dynamischer Systeme, deren stationäre Zustände die Lösung des Optimierungsproblems sind. Die zweite Strategie, die lokal ist, beginnt mit einem vorgeschlagenen Algorithmus zur Lösung eines Optimierungsproblems und wendet fixpunkttheoretische Werkzeuge an, um das Verhalten der entsprechenden Picard-Iterationen zu charakterisieren. Die beiden Arten der Regularität - Semi-Algebraizität auf der einen Seite und Superregularität auf der anderen Seite - führen zu unterschiedlichen Kategorien der Nichtkonvexität, die nicht immer kompatibel sind. Dies führt zu einer Lücke in der Analyse von Algorithmen, nämlich der Übergang vom globalen Verhalten zum lokalen Verhalten und die Charakterisierung des Grenzverhaltens von Algorithmen im Kontext des gewünschten Optimierungsproblems. Unser Fokus auf Probleme mit dem quadratischen Format ermöglicht es uns, die beiden Analysestämme an einem gemeinsamen Schnittpunkt zusammenzuführen. Ausgehend von diesen beiden Hauptstämmen der Analyse und unseren jüngsten Erfolgen in diesen Bereichen werden mehrere herausfordernde Fragen im Zusammenhang mit dem Entwurf von Algorithmen und ihrer Konvergenz-/Komplexitätsanalyse behandelt, insbesondere im Hinblick auf den Mechanismus der quantifizierbaren Konvergenz neuer Methoden für Probleme, die keine Standardglätte und Skalierbarkeit aufweisen. Unsere theoretischen Erkenntnisse werden in die Implementierung neuer, praktischer und effizienter Algorithmen zur Lösung wirkungsvoller angewandter Probleme umgesetzt.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Israel
• ausländische Mitantragsteller: Professor Shoham Sabach, Ph.D.; Professor Dr. Marc Teboulle