Konvexe Optimierung

Konvexe Optimierung ist die Untersuchung der Minimierung konvexer Funktionen über konvexen Mengen, einer Klasse von Problemen, für die lokale Optima global sind und effiziente Algorithmen existieren.

Definition

Ein konvexes Optimierungsproblem minimiert eine konvexe Zielfunktion unter konvexen Ungleichheitsbeschränkungen und affinen Gleichheitsbeschränkungen; die zulässige Menge ist konvex, was sicherstellt, dass jedes lokale Minimum auch ein globales Minimum ist.

Scope

Dieses Thema behandelt konvexe Mengen und Funktionen, die Erkennung und Modellierung konvexer Probleme, lineare, quadratische, Kegel-zweiter-Ordnung- und semidefinierte Programme, die Lagrange-Dualität und die Karush-Kuhn-Tucker-Bedingungen für konvexe Probleme sowie Innere-Punkte- und Erst-Ordnungs-Algorithmen mit ihren Komplexitätsgarantien.

Core questions

• Wie kann ein Problem als konvex erkannt oder reformuliert werden?
• Warum garantiert Konvexität, dass lokale Optima global sind?
• Was verrät die Dualität über ein konvexes Problem und seine Lösung?
• Welche Algorithmen lösen konvexe Probleme effizient und mit welchen Garantien?

Key theories

Globale Optimalität konvexer Probleme

Da eine konvexe Funktion über einer konvexen Menge keine falschen lokalen Minima aufweist, ist jeder lokal optimale Punkt global optimal, was konvexe Probleme zuverlässig lösbar macht.

Lagrange-Dualität und KKT-Bedingungen

Jedes konvexe Problem hat ein zugehöriges duales Problem, das Optimalitätszertifikate liefert, und unter Constraint Qualifications sind die Karush-Kuhn-Tucker-Bedingungen notwendig und hinreichend für Optimalität.

Innere-Punkte-Methoden

Innere-Punkte-Methoden folgen einem zentralen Pfad durch das Innere des zulässigen Bereichs und lösen konvexe Probleme, einschließlich semidefiniter Programme, in nachweislich polynomialer Zeit.

Clinical relevance

Konvexe Optimierung ist in den Bereichen maschinelles Lernen, Signal- und Bildverarbeitung, Steuerung, Finanzen und Ingenieurdesign weit verbreitet, da viele Schätz- und Entscheidungsprobleme als konvexe Programme formuliert und zuverlässig in großem Maßstab gelöst werden können.

History

Das Feld basiert auf der konvexen Analyse, die Rockafellar um 1970 systematisierte. Karmarkars Innere-Punkte-Methode von 1984 und die nachfolgende Theorie von Nesterov und Nemirovski zeigten, dass breite Klassen konvexer Probleme in polynomialer Zeit lösbar sind, was den modernen, modellgetriebenen Ansatz zur konvexen Optimierung auslöste.

Key figures

• R. Tyrrell Rockafellar
• Stephen Boyd
• Yurii Nesterov
• Narendra Karmarkar

Seminal works

• boyd2004
• rockafellar1970

Frequently asked questions

Warum sollte man, wenn möglich, konvexe Modelle bevorzugen?

Konvexe Probleme bieten die Garantie, dass jede gefundene Lösung global optimal ist, und verfügen über ausgereifte, effiziente Algorithmen. Nicht-konvexe Modelle können Solver in minderwertigen lokalen Optima gefangen halten, weshalb ein Großteil der angewandten Arbeit darauf abzielt, Probleme konvex zu reformulieren.

Ist lineare Programmierung eine Art konvexer Optimierung?

Ja. Ein lineares Programm minimiert eine lineare Zielfunktion über einem Polyeder, und sowohl lineare Funktionen als auch Polyeder sind konvex, daher ist die lineare Programmierung ein spezieller, besonders gut verstandener Fall der konvexen Optimierung.