Warum sollte Nicht-Konvexität ein Problem bei der Optimierung sein?

20

Ich war sehr überrascht, als ich anfing, etwas über nicht-konvexe Optimierung im Allgemeinen zu lesen, und ich sah Aussagen wie diese:

Viele wichtige praktische Probleme sind nicht konvex, und die meisten nicht konvexen Probleme sind schwer (wenn nicht unmöglich), genau in angemessener Zeit zu lösen. ( Quelle )

oder

Im Allgemeinen ist es schwierig, ein lokales Minimum zu finden, und viele Algorithmen können an einem Sattelpunkt hängen bleiben. ( Quelle )

Ich mache jeden Tag eine Art nicht-konvexe Optimierung - nämlich die Entspannung der Molekülgeometrie. Ich habe es nie für etwas heikles, langsames und anfälliges gehalten. In diesem Zusammenhang haben wir deutlich mehrdimensionale nicht konvexe Oberflächen (> 1000 Freiheitsgrade). Wir verwenden hauptsächlich Techniken erster Ordnung, die aus dem steilsten Abstieg und dem dynamischen Löschen stammen, wie z. B. FIRE , die in wenigen hundert Schritten auf ein lokales Minimum (weniger als die Anzahl der DOFs) konvergieren. Ich erwarte, dass es mit dem Zusatz von stochastischem Rauschen höllisch robust sein muss. (Globale Optimierung ist eine andere Geschichte)

Ich kann mir irgendwie nicht vorstellen, wie die potenzielle Energieoberfläche aussehen sollte, um diese Optimierungsmethoden stecken zu lassen oder langsam konvergieren zu lassen. ZB sehr pathologische PES (aber nicht aufgrund von Nicht-Konvexität) ist diese Spirale , aber es ist kein so großes Problem. Können Sie ein anschauliches Beispiel für pathologische nicht konvexe PES geben?

Ich möchte mich also nicht mit den obigen Zitaten auseinandersetzen. Ich habe eher das Gefühl, dass mir hier etwas fehlt. Vielleicht der Kontext.

Prokop Hapala
quelle
4
Das Schlüsselwort hier ist "allgemein" - Sie können beliebig böse Funktionalitäten konstruieren, insbesondere in sehr hohen Dimensionen, die im Grunde "alle Sattelpunkte" sind. Bestimmte Klassen von nicht konvexen Funktionalen können sich dagegen sehr gut verhalten, insbesondere wenn Sie geeignete Globalisierungsstrategien anwenden.
Christian Clason
2
Ich denke, dass Anwendungen in den Bereichen optimale Steuerungstheorie und Ingenieurwesen / Betriebsforschung einen gewissen Schwerpunkt auf Korrektheit / Robustheit legen, wohingegen Sie der Meinung sind, dass es gut genug ist, irgendwo "gut genug" anzukommen. Es kann Leistungsgrenzen geben (Konvergenz muss garantiert sein, damit die Flugbahn eines Roboters rechtzeitig berechnet wird) oder Korrektheitsgrenzen (wenn Sie die Problemparameter ein wenig ändern, erhalten Sie nicht unerwartet ein völlig anderes Ergebnis). Es reicht also nicht aus, einige optimale Punkte zu erzielen, sondern es müssen auch einige vorgeschriebene Eigenschaften vorliegen.
Kirill

Antworten:

23

argminf(x)

  1. Eine Kandidatenlösung: Eine bestimmte Wahl der Entscheidungsvariablen und ihres entsprechenden Zielwertes , AND f ( x )xf(x)
  2. Ein Beweis der Optimalität: Ein mathematischer Beweis, dass die Wahl von global optimal ist, dh dass für jede Wahl von . f ( x ) f ( x ) xxf(x)f(x)x

Wenn konvex ist, werden beide Bestandteile leicht erhalten. Gradientenabstieg findet eine Kandidatenlösung , die den Gradienten verschwinden lässt . Der Beweis der Optimalität folgt aus einer einfachen in MATH101 gelehrten Tatsache, dass, wenn konvex ist und sein Gradient bei verschwindet , eine globale Lösung ist.x f ( x ) = 0 f f x x fxf(x)=0ffxx

Wenn nicht konvex ist, ist eine mögliche Lösung zwar immer noch leicht zu finden, der Beweis der Optimalität wird jedoch äußerst schwierig. Zum Beispiel können wir einen Gradientenabstieg durchführen und einen Punkt finden . Aber wenn nicht konvex ist, ist die Bedingung notwendig, aber für die globale Optimalität nicht mehr ausreichend. Tatsächlich reicht es nicht einmal für die lokale Optimalität aus, dh wir können nicht einmal garantieren, dass allein aufgrund seiner Gradienteninformationen ein lokales Minimum ist. Ein Ansatz besteht darin, alle Punkte aufzulisten, die erfüllen , und dies kann auch über nur eine oder zwei Dimensionen hinweg eine gewaltige Aufgabe sein.f ( x ) = 0 f f ( x ) = 0 x f ( x ) = 0ff(x)=0ff(x)=0xf(x)=0

Wenn Mathematiker sagen, dass die meisten Probleme nicht zu lösen sind, sagen sie wirklich, dass der Beweis der (auch lokalen) Optimalität nicht zu konstruieren ist . In der realen Welt sind wir jedoch oft nur daran interessiert, eine "ausreichend gute" Lösung zu berechnen, und diese kann auf unendlich viele Arten gefunden werden. Für viele hochgradig nicht konvexe Probleme zeigt uns unsere Intuition, dass die "gut genug" -Lösungen tatsächlich global optimal sind, auch wenn wir dies nicht vollständig beweisen können!

Richard Zhang
quelle
Globale oder lokale Optimalität ist ein völlig anderes Thema. Aber der Rest macht Sinn. Können Sie mehr darüber sagen, dass Sie nicht einmal garantieren können, dass x ein lokales Minimum ist, das allein auf der Gradienteninformation basiert, oder dies besser veranschaulichen?
Prokop Hapala
Nehmen wir an, wir haben die Funktionen und als schwarze Kästchen (dh wir können nur auswerten, aber wir können ihre Form nicht erkennen). Der Punkt lässt beide Gradienten verschwinden, dh und , aber der Punkt ist nur ein lokales Minimum für . Tatsächlich sind ihre zweiten Ableitungen zu diesem Zeitpunkt ebenfalls Null, sodass die beiden Szenarien mit den ersten beiden Ableitungen allein identisch sind! g ( x ) = x 4 x = 0 f ' ( x ) = 0 g ' ( x ) = 0 gf(x)=x3G(x)=x4x=0f(x)=0G(x)=0G
Richard Zhang
aha, ok, ich gehe immer automatisch von einer Trägheit aus => dass der Algorithmus überhaupt nicht dazu neigt, zum Punkt in zu konvergieren . Aber sicher, da verwenden wir zusätzliche Informationen (die Trägheit) aus vorherigen Schritten, nicht nur die Steigung in einem Punkt. g ( x ) = x 3x=0G(x)=x3
Prokop Hapala
Ich verstehe deine Meinung. Und vielleicht ist das wirklich der Grund, warum nicht-konvexe Optimierungen im strengen mathematischen Sinne als schwierig angesehen werden. Aber ich bin immer noch mehr an der praktischen Anwendung interessiert, bei der Heuristiken (die ich als natürlichen Teil des Algorithmus annehme) kläglich versagen würden.
Prokop Hapala
Was ist mit Quasikonvexität? Nach dieser Logik (( ist genug), wäre nicht quasikonvexe Probleme so einfach zu optimieren , wie konvexe Probleme ?. Mein Verständnis ist , dass letztere isn‘true (konvexe Probleme sind noch einfacher).f(x)=0
Amelio Vazquez-Reina
6

Ein Beispiel für ein kniffliges Problem mit geringen Abmessungen könnte sein:

Bildbeschreibung hier eingeben

Wenn Sie ein lokales Minimum erreicht haben, wie können Sie dann sicher sein, dass es annähernd so gut ist wie das globale Minimum? Woher wissen Sie, ob Ihr Ergebnis eine weltweit optimale, einzigartige und optimale Lösung ist? Wie können Sie einen Algorithmus erstellen, der allen Hügeln und Tälern standhält, damit er nicht irgendwo hängen bleibt?

Ein Beispiel wie dieses ist, wo die Dinge schwierig werden können. Offensichtlich sind nicht alle Probleme so, aber einige sind es. Was noch schlimmer ist, ist, dass in einem Umfeld in der Industrie die Kostenfunktion zeitaufwändig sein kann, um zu berechnen UND eine problematische Oberfläche wie die oben beschriebene zu haben.

Reales Problem Beispiel

Ein Beispiel, das ich bei der Arbeit angehen könnte, ist die Optimierung eines Flugkörperlenkungsalgorithmus, der bei vielen Startbedingungen robust sein könnte. Mit unserem Cluster konnte ich die Leistungsmessungen, die ich für eine einzelne Bedingung benötige, in etwa 10 Minuten abrufen. Um nun die Robustheit angemessen beurteilen zu können, möchten wir zumindest eine Stichprobe von Bedingungen, an denen wir uns messen lassen können. Nehmen wir also an, wir führen sechs Bedingungen aus, sodass die Auswertung dieser Kostenfunktion eine Stunde dauert.

Die nichtlineare Raketendynamik, die atmosphärische Dynamik, diskrete Zeitprozesse usw. führen zu einer ziemlich nichtlinearen Reaktion auf Änderungen des Führungsalgorithmus, wodurch die Optimierung schwer zu lösen ist. Die Tatsache, dass diese Kostenfunktion nicht konvex ist, macht es zeitaufwendig, ein großes Problem zu bewerten. Ein Beispiel wie dieses ist, wo wir uns bemühen würden, das Beste zu bekommen, was wir in der uns gegebenen Zeit können.

spektr
quelle
1
OK, ich denke, das ist ein anderes Problem ... Problem der globalen Optimierung, das eindeutig schwierig und in den meisten Situationen unlösbar ist. Aber das ist nicht das, worauf sich die Leute in Bezug auf die nicht-konvexe Optimierung beziehen, wo sie sagen, dass es für NP schwierig ist, ein lokales Minimum zu finden und viele Algorithmen an einem Sattelpunkt hängen bleiben können.
Prokop Hapala
1
@ProkopHapala Meine Kommentare beziehen sich eher auf das Zitat. Viele wichtige praktische Probleme sind nicht konvex, und die meisten nicht konvexen Probleme lassen sich nur schwer (wenn nicht unmöglich) in angemessener Zeit lösen , zumal im OP davon gesprochen wurde, wie einfach sie sind Es war ihre Aufgabe, nicht-konvexe Probleme in der Forschung anzugehen. Die Lösung genau , zu mir, ist für eine global optimale Lösung anstreben (oder etwas in der Nähe). Deshalb wollte ich ein Bild der realen Herausforderungen zeichnen, die mit diesen Kommentaren verbunden sind.
Spektrum
Ich verstehe. Genau genommen haben Sie recht, aber ich denke, es geht nicht darum, was ich meinte ... Vielleicht hätte ich es besser formulieren sollen.
Prokop Hapala
5

Das Problem sind Sattelpunkte, die in dem von Ihnen verknüpften Beitrag besprochen wurden. Aus dem Abstract eines der verlinkten Artikel :

Im Allgemeinen ist es jedoch schwierig zu garantieren, dass solche Algorithmen sogar zu einem lokalen Minimum konvergieren, da komplizierte Sattelpunktstrukturen in hohen Dimensionen vorhanden sind. Viele Funktionen haben entartete Sattelpunkte, so dass die Ableitungen erster und zweiter Ordnung sie nicht mit lokalen Optima unterscheiden können . In diesem Artikel verwenden wir Ableitungen höherer Ordnung, um diesen Sattelpunkten zu entgehen: Wir entwerfen den ersten effizienten Algorithmus, der garantiert zu einem lokalen Optimum dritter Ordnung konvergiert (während vorhandene Techniken höchstens zweiter Ordnung sind). Wir zeigen auch, dass es NP-schwierig ist, dies weiter auszudehnen, um lokale Optima vierter Ordnung zu finden.

Grundsätzlich können Sie Funktionen haben, bei denen Sie Sattelpunkte haben, die von lokalen Minima nicht zu unterscheiden sind, wenn Sie die 1., 2. und 3. Ableitung betrachten. Sie könnten dies lösen, indem Sie zu einem Optimierer höherer Ordnung gehen, aber sie zeigen, dass es NP-schwer ist, ein lokales Minimum 4. Ordnung zu finden.

x2y+y2

Sie können eine Reihe von Heuristiken verwenden, um sich solchen Punkten zu entziehen. Diese funktionieren möglicherweise für viele (die meisten?) Beispiele aus der Praxis, es kann jedoch nicht nachgewiesen werden , dass sie immer funktionieren.
In dem von Ihnen verlinkten Blog-Beitrag diskutieren sie auch die Bedingungen, unter denen Sie solchen Sattelpunkten in polynomialer Zeit entkommen können.

LKlevin
quelle
x2y+y2
2
Sie müssen es anders sehen. Es ist nicht so, dass wir wissen, dass der stochastische Gradientenabstieg scheitern wird, sondern dass wir nicht wissen, dass er erfolgreich sein wird. Bei Spielzeugproblemen ist es unwahrscheinlich, dass dies in der Praxis auftritt, aber es kann bei Problemen mit höheren Dimensionen vorkommen. Ich wette, dass dies bei Ihren Chemieproblemen niemals passieren wird, aber ich würde es schwer haben, das zu beweisen.
LKlevin