Diskrete Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:19 Do 15.04.2010 | | Autor: | conman |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich bin auf der Suche nach einem iterativen Verfahren, das mir das folgende Optimierungsproblem löst:
f(x) [mm] \to [/mm] min
mit x [mm] \in \IN.
[/mm]
Ich kenne f nur an den Stellen, an denen ich es auswerte aber ich weiß, dass f konvex ist. Da ich f nicht kenne, kann ich es nicht analytisch lösen und daher suche ich ein iteratives Verfahren.
Ich bin kein Mathematiker, aber für mich sieht die ![[]](/images/popup.gif) Subgradient-Methode ganz vielversprechend aus... nur wie funktioniert das auf der diskreten Menge x [mm] \in \IN?
[/mm]
Oder bin ich da auf dem falschen Weg und es gibt ein anderes Verfahren?
Beste Dank!
Constantin
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:13 Fr 16.04.2010 | | Autor: | rrgg |
Hallo!
Das Problem hat ja eine recht einfache Form: Es ist eindimensional und f ist konvex! Man kann sich zum Beispiel überlegen das man f(x)
so lange auswertet bis es größer wird!
Algorithmus:
1) k=0
2) [mm] y_k=f(k)
[/mm]
3) wenn [mm] y_{k-1}< y_k [/mm] dann ist [mm] (k-1;y_{k-1}) [/mm] ein Ergebniss
sonst k=k+1 und weiter zu Schritt 2
sollte funktionieren!
LG
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:36 Fr 16.04.2010 | | Autor: | conman |
Stimmt, das würde tatsächlich zur richtigen Lösung führen.
Der Nachteil ist, dass es die Steigung der Kurve nicht in die Suche einbezieht - man bracht als ggf. recht lange.
Toll wäre etwas in der Art des Gradientenverfahrens. Den Gradient kann ich über den vorhergehenden Iterationsschritt abschätzen:
[mm] grad(x_n) [/mm] = [mm] \bruch{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}}
[/mm]
Dann fehlt mir nur noch etwas um die Schrittweite zu bestimmen... es gibt hierfür Bedingungen z.B. von Armijo, aber ich bin mir nicht ganz sicher, ob das das richtige für meine Situation ist.
Im Netzt habe ich auch nichts auf meinem Niveau bezüglich eines diskreten Gradientenverfahrens gefunden.
Kannst du mir da weiterhelfen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:06 Fr 16.04.2010 | | Autor: | rrgg |
Ich glaube, du musst anders an die Aufgabe herangehen!
Du willst ja scheinbar eine Abstiegsmethode benutzen; die funktionieren eigentlich immer so:
1. Du suchst eine Abstiegsrichtung (Gradient, oder irgendeine Nährung davon)
2. Du bestimmst eine Schrittweite
Du hast hier allerdings ein eindimensionales Problem, weswegen der erste Punkt bereits wegfällt (du kannst ja nur in eine Richtung gehen)
D.h du musst nur "Schrittweite" bestimmen, was von Anfangan klar war!
[mm] \Rightarrow [/mm] Du musst nach eindimensionalen Minimierungsverfahren suchen!
Bekannt sind da beispielsweise: Einschachtelungsverfahren; Dreiteilung nach goldenem Schnitt;...
Mit diskreten eindimensionalen Programmen hab ich mich allerdings noch nie beschäftigt.
Lg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:16 Fr 16.04.2010 | | Autor: | conman |
Alles klar, dan suche ich mal nach Methoden in diesem Bereich. Vielen Dank für deine Hilfe!
|
|
|
|
