Kann die Gradientenabsenkung auf nicht konvexe Funktionen angewendet werden?

Ich lerne nur etwas über Optimierung und habe Probleme, den Unterschied zwischen konvexer und nichtkonvexer Optimierung zu verstehen. Nach meinem Verständnis ist eine konvexe Funktion eine, bei der "das Liniensegment zwischen zwei beliebigen Punkten im Diagramm der Funktion über oder im Diagramm liegt". In diesem Fall könnte ein Algorithmus für den Gradientenabstieg verwendet werden, da es nur ein einziges Minimum gibt und die Gradienten Sie immer zu diesem Minimum führen.

Was ist jedoch mit der Funktion in dieser Abbildung:

Hier kreuzt sich das blaue Liniensegment unter der roten Funktion. Die Funktion hat jedoch immer noch ein einzelnes Minimum, sodass Sie bei einem Gefälle immer noch zu diesem Minimum gelangen.

Meine Fragen sind also:

1) Ist die Funktion in dieser Figur konvex oder nicht konvex?

2) Wenn es nicht konvex ist, können dann noch konvexe Optimierungsmethoden (Gradientenabfall) angewendet werden?

Die von Ihnen grafisch dargestellte Funktion ist in der Tat nicht konvex. Wie auch immer es ist quasikonvex .

$x_1, x_2, \ldots$$f(x_1) > f(x_2) > \ldots$

Der Gradientenabstieg konvergiert schließlich unabhängig von der Konvexität zu einem stationären Punkt der Funktion. Wenn die Funktion konvex ist, ist dies ein globales Minimum, aber wenn nicht, kann es ein lokales Minimum oder sogar ein Sattelpunkt sein.

Quasiconvex-Funktionen sind ein interessanter Fall. Jedes lokale Minimum einer quasikonvexen Funktion ist auch ein globales Minimum, aber quasikonvexe Funktionen können auch stationäre Punkte haben, die keine lokalen Minima sind (take$f(x) = x^3$

Paulus erwähnte bereits einen wichtigen Punkt:

• Wenn f konvex ist, gibt es keine Sattelpunkte und alle lokalen Minima sind auch global. Somit ist GD (mit einer geeigneten Schrittgröße) garantiert, einen globalen Minimierer zu finden.

Was die nicht-konvexe Optimierung schwierig macht, ist das Vorhandensein von Sattelpunkten und lokalen Minima, bei denen der Gradient (0, ..., 0) ist und die einen willkürlich schlechten Zielwert haben.

Das Auffinden des globalen Minimierers in einer solchen Umgebung ist in der Regel nicht einfach. Stattdessen versucht man, einen lokalen Minimierer zu finden.

Beachten Sie jedoch Folgendes:

• Die Wahrscheinlichkeit, dass GD an einem Sattel hängen bleibt, ist 0 ( siehe hier) ).
• Das Vorhandensein von Sattelpunkten kann jedoch das Fortschreiten der GD erheblich verlangsamen, da Richtungen mit geringer Krümmung zu langsam ausgenutzt werden ( siehe hier ).

Abhängig von der Dimensionierung Ihres Problems kann es daher ratsam sein, eine Optimierungsroutine zweiter Ordnung zu wählen.