Warum sind konvexe Probleme einfach zu optimieren?

Motiviert durch diese Top-Antwort auf die Frage: Warum ist Konvexität bei der Optimierung wichtiger als Quasikonvexität ? Ich hoffe jetzt zu verstehen, warum konvexe Probleme leicht zu optimieren sind (oder zumindest einfacher als quasikonvexe Probleme).

Was sind einige der effizientesten Algorithmen zur konvexen Optimierung und warum können sie bei quasikonvexen Problemen nicht effektiv eingesetzt werden?

optimization convex-optimization Amelio Vazquez-Reina
quelle

Eine äußerst schöne Eigenschaft ist, dass beim Zeichnen einer Linie / Ebene / Hyperebene, die den Graphen einer konvexen Funktion tangiert, der gesamte Graph auf einer Seite der Linie liegt, was für quasikonvexe Funktionen nicht funktioniert.

Kirill

Antworten:

Die meisten der besten modernen Methoden zur Optimierung in großem Maßstab umfassen eine lokale quadratische Annäherung an die Zielfunktion, die sich dem kritischen Punkt dieser Annäherung nähert und dann wiederholt. Dies schließt Newtons Methode, L-BFGS usw. ein.

Eine Funktion kann nur dann lokal durch ein Quadrat mit einem Minimum gut angenähert werden, wenn der Hessische am aktuellen Punkt positiv bestimmt ist. Wenn der Hessische unbestimmt ist, dann auch nicht

Die lokale quadratische Näherung ist eine gute lokale Annäherung an die Zielfunktion und daher eine Satteloberfläche. Die Verwendung dieser quadratischen Näherung würde dann vorschlagen, sich in Richtung eines Sattelpunkts zu bewegen, der wahrscheinlich in die falsche Richtung weist, oder
Die lokale quadratische Näherung muss konstruktionsbedingt ein Minimum haben. In diesem Fall ist es wahrscheinlich eine schlechte Annäherung an die ursprüngliche Zielfunktion.

(Die gleiche Art von Problemen tritt auf, wenn der Hessische negativ bestimmt ist. In diesem Fall sieht er lokal wie eine umgedrehte Schüssel aus.)

Diese Methoden funktionieren also am besten, wenn der Hessische überall positiv positiv ist, was der Konvexität für glatte Funktionen entspricht.

Natürlich verfügen alle guten modernen Methoden über Sicherheitsvorkehrungen, um die Konvergenz zu gewährleisten, wenn Sie sich durch Regionen bewegen, in denen das Hessische unbestimmt ist - z. B. Liniensuche, Vertrauensbereiche, Stoppen einer linearen Lösung, wenn eine Richtung negativer Krümmung auftritt usw. In solchen unbestimmten Bereichen ist die Konvergenz im Allgemeinen viel langsamer, da keine vollständigen Krümmungsinformationen über die Zielfunktion verwendet werden können.

Nick Alger
quelle

Nicht zustimmen. Vertrauensbereiche können mit unbestimmten Quadraten umgehen. Sogar Liniensuchmethoden können durch Suchen und Durchführen einer Liniensuche nach Richtungen negativer Krümmung. Wenn Ihr Algorithmus jedoch nackt ist und keine Vertrauensregion oder geeignete Zeilensuche zum Schutz vorhanden ist, sind Sie in Schwierigkeiten. Aber Sie können auch mit einer solchen Rücksichtslosigkeit in Schwierigkeiten geraten, selbst wenn Sie eine streng konvexe Funktion haben.

Mark L. Stone

@ MarkL.Stone Natürlich ist das wahr und ich habe darüber diskutiert, es beim Schreiben des Beitrags zu erwähnen. Der Punkt ist jedoch, dass Sie die Methode zwar konvergieren lassen können, indem Sie eine spezielle Behandlung durchführen (wie es alle guten modernen Codes tun), aber die Konvergenz ist erheblich langsamer. Beispielsweise entspricht eine Vertrauensbereichsmethode einem Gradientenabstieg, wenn der Vertrauensbereich klein ist.

Nick Alger

Sie können versuchen, einen konvexen Optimierungsalgorithmus auf ein nicht konvexes Optimierungsproblem anzuwenden, und es kann sogar zu einem lokalen Minimum konvergieren. Wenn Sie jedoch nur lokale Informationen über die Funktion haben, können Sie niemals den Schluss ziehen, dass Sie tatsächlich sind fand das globale Minimum. Die wichtigste theoretische Eigenschaft konvexer Optimierungsprobleme ist, dass jedes lokale Minimum (tatsächlich jeder stationäre Punkt) auch ein globales Minimum ist.

Algorithmen zur globalen Optimierung nichtkonvexer Probleme müssen eine Art globale Information enthalten (z. B. Lipschitz-Kontinuität der Funktion), um zu beweisen, dass eine Lösung ein globales Minimum ist.

Um Ihre spezifische Frage zu beantworten, warum ein konvexer Optimierungsalgorithmus bei einem quasi-konvexen Problem fehlschlagen könnte, nehmen wir an, dass Ihr konvexer Optimierungsalgorithmus zufällig an einer "flachen Stelle" im Diagramm der Zielfunktion gestartet wird. Der Farbverlauf enthält keine lokalen Informationen, die Ihnen sagen, wohin Sie als Nächstes gehen sollen. Bei einem konvexen Problem können Sie einfach aufhören und wissen, dass Sie sich bereits an einem lokalen (und damit globalen) Mindestpunkt befinden.

Brian Borchers
quelle

Ich denke nicht, dass dies die Frage nach Konvexität und Quasikonvexität beantwortet. Wenn das Problem nur darin besteht, flache Gradienten zu vermeiden, könnte man annehmen, dass effiziente konvexe Methoden für streng quasikonvexe Funktionen gleich gut funktionieren, was meiner Meinung nach nicht der Fall ist.

Amelio Vazquez-Reina

y = x^{3}

$y=x^{3}$

x = 0

$x=0$

x = 0

$x=0$

Es gibt einen Standardsatz, der besagt, dass wenn eine Abstiegsmethode mit einer Liniensuche verwendet wird, die die Armijo-Bedingungen erfüllt, die globale Konvergenz auf ein lokales Minimum gebracht wird. (Ich habe hier einige technische Hypothesen ausgelassen.) Ja, Sie könnten also die globale Konvergenz für Ihre Klasse von quasikonvexen Funktionen ohne nicht optimale kritische Punkte auf ein Minimum bringen. Siehe zum Beispiel Satz 3.2 in der zweiten Ausgabe des Textes von Nocedal und Wright.

Brian Borchers

In Bezug auf "so einfach zu optimieren" müssen Sie über das Problem der globalen Konvergenz hinaus zu einem Minimierer gehen und Konvergenzraten berücksichtigen. Die Analyse vieler Methoden zur konvexen Optimierung (z. B. quadratische Konvergenz der Newtonschen Methode oder schnelle Konvergenz einiger neuerer beschleunigter Methoden erster Ordnung zur konvexen Optimierung) hängt von der Konvexität ab, sodass diese Methoden für Ihre Klasse quasikonvexer Funktionen fehlschlagen können. Zum Beispiel könnte eine quasikonvexe Funktion einen eindeutigen kritischen Punkt haben, aber Punkte, an denen das Hessische singulär ist, und dies könnte Newtons Methode brechen.

Brian Borchers

Denken Sie auch daran, dass Menschen, die von konvexen Optimierungsproblemen als "leicht zu lösen" sprechen, im Allgemeinen über einige Klassen von konvexen Optimierungsproblemen (LP, konvexes QP, SOCP, SDP usw.) sprechen, für die ein Polynom vorliegt Zeitalgorithmen existieren und das kann in der Praxis leicht gelöst werden. Allgemeinere konvexe Optimierungsprobleme können in der Praxis viel schwieriger zu lösen sein.

Brian Borchers