nichtkonvex

Nichtkonvex bezeichnet in der Geometrie und verwandten Bereichen die Eigenschaft einer Menge, die nicht konvex ist. Eine Teilmenge C eines Vektorraums, typischerweise R^n, ist konvex, wenn für alle x und y in C sowie alle t im Intervall [0,1] der Punkt t x + (1−t) y ebenfalls in C liegt. Fehlt diese Bedingung, spricht man von Nichtkonvexität oder davon, dass C nicht konvex ist.

Anschauliches Beispiel: Ein Ring (Annulus) oder eine L-förmige Region zeigen deutlich, dass zwei Punkte in der Menge liegen können, deren Verbindungsstrecke teilweise außerhalb liegt. Konvexe Mengen haben dagegen stets die Eigenschaft, dass jede Verbindungsstrecke zwischen zwei Punkten in der Menge bleibt. Der konvexe Abschluss (Hull) der Menge ist die kleinste konvexe Menge, die die ursprüngliche Menge einschließt.

In der Optimierung ist Nichtkonvexität eine häufige Ursache für mehrere lokale Optima. Nicht konvexe Funktionen oder Problemstellungen erschweren die Suche nach dem globalen Optimum. Folgende Ansätze kommen zum Einsatz: heuristische und metaheuristische Suchverfahren, Relaxationen, Convexificationstechniken sowie spezielle globale Optimierungsverfahren (zum Beispiel semidefinite Programmierung).

Anwendungsbereiche reichen von Geometrie und Computergrafik über Operations Research bis hin zu maschinellem Lernen. Dort sind Nichtkonvexität und deren Behandlung entscheidend für Modellierung, Berechnung und Leistungsfähigkeit von Algorithmen.