Name eines Optimierungsansatzes zur Reduzierung der Größe des variablen Raums

8

Ich habe es mit einem Optimierungsproblem zu tun, bei dem eine große Anzahl von Variablen optimiert werden muss. Nennen wir beispielsweise diese Variablen , y und z, und ich möchte die Funktion f ( x , y , z ) minimieren . Die von mir verwendete Optimierungsmethode kann nicht alle Variablen gleichzeitig optimieren. Ich vereinfache stattdessen das Problem, indem ich jeweils nur eine Variable optimiere und dabei die anderen Variablen festhalte.xyzf(x,y,z)

Dh ich fixiere und z = z 0 und optimiere dann die Funktion nur über x . Diese 1D-Optimierung ergibt einen optimalen Wert x . Ich fixiere dann x = x , z = z 0 und optimiere dann über y . Mir ist klar, dass dies nicht unbedingt eine global optimale Lösung bietet, sondern ein lokales Minimum ergeben sollte.y=y0z=z0xxx=xz=z0y

Ich frage mich, wie diese Methode heißt und wo ich Informationen dazu finden kann. Auch wenn es eine passendere Community gibt, lassen Sie es mich bitte wissen. Vielen Dank

Bearbeiten: Die Optimierung wird über , dann y , dann z , dann x usw. durchgeführt, bis die Lösung konvergiert.xyzx

user69813
quelle

Antworten:

9

Dies ist ein Koordinatenabstieg . Ich glaube, es wird bei sehr großen Problemen verwendet, wenn andere Methoden wie der Gradientenabstieg möglicherweise zu langsam sind (z . B. http://epubs.siam.org/doi/abs/10.1137/100802001 ). Es sollte zu einem lokalen Minimum konvergieren, aber es würde auch mehr Schritte erfordern als so etwas wie Gradientenabstieg oder Newton-Typ-Methoden.

Kirill
quelle
4

Der ursprünglich beschriebene Ansatz (nur eine Iterationsoptimierung in jeder der drei Variablen x, y, z) konvergiert nicht garantiert zur optimalen Lösung, es sei denn, F (x, yz) ist variabel in univariate Funktionen trennbar. Daher ist das, was Sie beschreiben, technisch gesehen keine Optimierungs- "Methode", sondern eine Optimierungs- "Heuristik", ähnlich einer Operator-Aufteilungsmethode oder ADI-Methoden (Alternating Direction Implicit).

Paul
quelle
Sie haben Recht, es ist nicht garantiert, dass diese Methode die optimale Lösung erreicht. Die Funktion, die ich zu minimieren versuche, ist nicht konvex mit mehreren lokalen Minima. Daher bin ich zufrieden damit, ein lokales Minimum zu finden und nicht unbedingt die optimale Lösung. Ich bin immer noch gespannt, ob diese Heuristik schon einmal in der Literatur verwendet wurde
user69813
Es ist nicht einmal garantiert, ein lokales Minimum oder irgendetwas in der Nähe zu finden.
Paul
@Paul, ich denke, dass die Methoden für glatte Funktionen konvergieren: "Es kann gezeigt werden, dass diese Sequenz ähnliche Konvergenzeigenschaften wie der steilste Abstieg aufweist. Keine Verbesserung nach einem Zyklus der Liniensuche entlang der Koordinatenrichtungen impliziert, dass ein stationärer Punkt erreicht wird." Diese Referenz diskutieren darüber.
Nicoguaro
3
@nicoguaro Ich denke, vor der Bearbeitung von OP klang es so, als hätte die Methode nur eine Iteration durchgeführt und dann gestoppt. Ich war auch ein bisschen verwirrt.
Kirill
@Kirill, ich verstehe. Ich werde dann meinen Kommentar löschen. Auf der anderen Seite, wenn sich die Frage geändert hat, sollte dies auch die Antwort sein, nein?
Nicoguaro