Golden Section Search < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:43 Fr 06.08.2010 | | Autor: | conman |
Wenn ich nach "Golden Section Search" suche, dann wird diese immer als eine Methode zur eindimensionalen-Optimierung einer konvexen Funktion angeführt.
Kann ich die Golden-Section-Search auch bei einer mehrdimensionalen konvexen Funktion anwenden?
Ich stelle mir das so vor, dass jede Dimension einzeln betrachtet wird und immer eine eindimensionale Golden-Section-Search durchgeführt wird. Das Ergebnis wäre eine mehrdimensionale Optimierung.
Intuitiv leuchtet mir das ein, aber ob das tatsächlich immer konvergiert...?
Kann mir jemand etwas dazu sagen, warum die GS-Suche anscheinend nie im mehrdimensionalen Fall eingesetzt wird?
Grüße
Constantin
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:43 Mo 09.08.2010 | | Autor: | felixf |
Moin Constantin!
> Wenn ich nach "Golden Section Search" suche, dann wird
> diese immer als eine Methode zur
> eindimensionalen-Optimierung einer konvexen Funktion
> angeführt.
>
> Kann ich die Golden-Section-Search auch bei einer
> mehrdimensionalen konvexen Funktion anwenden?
Nicht das ich wuesste. Und ehrlich gesagt bezweifle ich es stark.
Das Verfahren im Eindimensionalen funktioniert deswegen, da man alle Funktionswerte auf dem Rand kennt, und alle Funktionswerte in der Mitte bzw. da wo geteilt wird.
Im Mehrdimensionalen besteht allein schon der Rand aus ueberabzaehlbar vielen Punkten. Ebenso die "Funktionswerte in der Mitte", die fuer die Sektion gebraucht werden.
Da ein Computer mit unendlich vielen Werten nicht klarkommt, wird das Verfahren vermutlich also nicht funktionieren.
> Ich stelle mir das so vor, dass jede Dimension einzeln
> betrachtet wird und immer eine eindimensionale
> Golden-Section-Search durchgeführt wird. Das Ergebnis
> wäre eine mehrdimensionale Optimierung.
>
> Intuitiv leuchtet mir das ein, aber ob das tatsächlich
> immer konvergiert...?
Beschreibe erstmal ordentlich das Verfahren, so dass man es auch nachvollziehen kann. Dann koennen wir dir helfen, mehr darueber auszusagen.
> Kann mir jemand etwas dazu sagen, warum die GS-Suche
> anscheinend nie im mehrdimensionalen Fall eingesetzt wird?
Weil bisher niemand geschafft hat, im mehrdimensionalen Fall eine funktionierende Variante hinzuschreiben.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:49 Mo 09.08.2010 | | Autor: | conman |
Hi Felix,
danke für dein Feedback. Ok, dann will ich meine "Idee" mal ordentlich Formulieren :)
Eine Iteration der 2D-Godlen Section Search würde ich wie folgt formulieren:
---
P1 = (x1,y1)
P2 = (x2,y2)
P3 = (x3,y3)
x1 < x2 < x3
y1 < y2 < x3
P3 < P1, P3 < P2
Jetzt wählt man P als Goldenen Schnitt zwischen P2 und P3:
also P = (x,y) mit
x = x2 + GS(x3 - x2)
y = y2 + GS(y3 - y2)
Wenn nun P < P2, dann liegt das Minimum im Interval [P2, P3], ansonsten in [P1, P].
---
Gibt es da ein einfaches Gegenbeispiel, wann das nicht funktioniert?
Du hast in deiner Nachricht deine Bedenken geäußerst, und ich vermute, dass du darauf hinaus wolltest, dass das Verfahren nicht konvergieren kann, da die Intervallschachtelung der GS das gesuchte Minimum immer einschließen muss - und das könnte im mehrdimensionalen nicht mehr der Fall sein... habe ich dich da richtig verstanden?
Mit der Beschreibung oben, müsste das aber der Fall sein, oder?
Grüße
Constantin
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:18 Mo 09.08.2010 | | Autor: | felixf |
Moin,
> danke für dein Feedback. Ok, dann will ich meine "Idee"
> mal ordentlich Formulieren :)
>
> Eine Iteration der 2D-Godlen Section Search würde ich wie
> folgt formulieren:
>
> ---
>
> P1 = (x1,y1)
> P2 = (x2,y2)
> P3 = (x3,y3)
>
> x1 < x2 < x3
> y1 < y2 < x3
>
> P3 < P1, P3 < P2
>
> Jetzt wählt man P als Goldenen Schnitt zwischen P2 und
> P3:
> also P = (x,y) mit
>
> x = x2 + GS(x3 - x2)
> y = y2 + GS(y3 - y2)
>
> Wenn nun P < P2, dann liegt das Minimum im Interval [P2,
> P3], ansonsten in [P1, P].
da fehlen Funktionswerte.
Aber mal allgemein: mit dieser Methode kannst du nur Punkte erreichen, die in einer (im Vergleich zur Ebene) sehr sehr kleinen Menge liegen -- evt. eine Menge von Mass 0. Warum sollte die Extremstelle der Funktion auch nur irgendwo in der Naehe dieser Menge liegen?
> Gibt es da ein einfaches Gegenbeispiel, wann das nicht
> funktioniert?
Man kann sicher eins finden. Wenn [mm] $P_1, P_2, P_3$ [/mm] auf einer Gerade liegen, liegen alle generierten Punkte auf dieser Geraden. Falls $f$ z.B. auf dieser Gerade Konstant den Wert 1 annimmt, aber daneben kleiner oder groesser wird, wird dein Algorithmus in diesem Fall nicht konvergieren.
> Du hast in deiner Nachricht deine Bedenken geäußerst, und
> ich vermute, dass du darauf hinaus wolltest, dass das
> Verfahren nicht konvergieren kann, da die
> Intervallschachtelung der GS das gesuchte Minimum immer
> einschließen muss - und das könnte im mehrdimensionalen
> nicht mehr der Fall sein... habe ich dich da richtig
> verstanden?
Ja, so kann man es auch sagen.
> Mit der Beschreibung oben, müsste das aber der Fall sein,
> oder?
Nein. Wieso sollte es?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:31 Mo 09.08.2010 | | Autor: | conman |
Hi
da fehlen Funktionswerte.
Oha, sorry: eigentlich sollte es heißen:
Wenn nun f(P) < f(P2), dann liegt das Minimum im Interval [P2, P3], ansonsten in [P1, P].
Aber du hast Recht, mit meinem Vorschlag werden nur Punkte auf einer Geraden zwischen P1 und P3 untersucht... liegt das Minimum woanders, kann die Methode nicht zu diesem Minimum konvergieren.
Danke für den Gedankenaustausch und schöne Grüße!
Constantin
|
|
|
|
