Ein Optimierungsrahmen, in dem die Zielfunktion konvex ist und die zulässige Menge konvex ist, was gewährleistet, dass jedes lokale Minimum ein globales Minimum ist und effiziente Lösungsmethoden ermöglicht.

Prinzip

Nutze Konvexität, damit Strecken zwischen zulässigen Punkten zulässig bleiben und konvexe Ziele keine lokalen Minima außer dem globalen Minimum besitzen; verwende Dualität und konvexe Analyse für Algorithmen und Zertifikate.

Demonstration

Minimiere eine konvexe quadratische Funktion unter linearen Ungleichungsbedingungen: Bei strikter Konvexität besitzt das Problem ein eindeutiges globales Minimierer; Innenpunkt-Methoden oder gradientenbasierte Verfahren mit Konvergenzgarantien finden die Lösung effizient.

Fehlanwendung

Convex-Optimierungsalgorithmen auf nichtkonvexe Probleme anzuwenden und sie als konvex zu behandeln, kann zu falschen Optima führen; konvexe Relaxationen können irreführend sein, wenn die Relaxationslücke groß ist oder diskrete Struktur entscheidend ist.

Konsequenz

Richtige Anwendung liefert global optimale Lösungen mit starker Dualität unter milden Bedingungen, robustes numerisches Verhalten und skalierbare Algorithmen von Innenpunkt- bis zu First-Order-Methoden je nach Problemgröße und Struktur.

Umkehrung

Die Umkehr ist nichtkonvexe Optimierung, in der mehrere lokale Minima existieren können und lokale Methoden in lokalen Minima hängen bleiben; nichtkonvexe Probleme erfordern meist globale Heuristiken, Branch-and-Bound oder problemspezifisches Wissen.

Abgrenzung

Beschränkt auf Probleme, deren Zielfunktionen und Nebenbedingungen als konvexe Funktionen und Mengen formuliert werden können; schließt inhärent nichtkonvexe Ziele, diskrete Entscheidungsvariablen ohne Relaxation und adversariale Gleichgewichtsprobleme aus, sofern sie nicht konvexiert werden können.

Semantische Spannung

Spannung zwischen Modelltreue und Konvexität: Das Erzwingen von Konvexität vereinfacht die Rechnung, kann jedoch Approximationen erzwingen, die Genauigkeit oder kritische Struktur opfern.

Synthese

Konvexe Optimierung ist die Untersuchung und Praxis der Optimierung konvexer Ziele über konvexe zulässige Bereiche und tauscht Modellgenerität gegen Garantien globaler Optimalität und wohlverstandenes algorithmisches Verhalten ein.