---

Hvis jeg kender f(x), men ikke selve funktionen, så kan jeg selvsagt ikke
differentiere den og dermed kan jeg ikke umiddelbart minimere den. Er
metoden slet og ret at estimere f'(x) som (f(x+½d)-f(x-½d))/d og bruge det
som hældningen? Tilsvarende kan man finde den anden afledte ved at bruge to
estimater for f'(x) og så fremdeles. Er det den gængse måde eller er der et
eller andet smart matematisk trick som jeg ikke kender til her?

---

Jakob Nielsen wrote:
> Er metoden slet og ret at estimere f'(x) som (f(x+½d)-f(x-½d))/d og
> bruge det som hældningen?

Numerisk er der jo ikke nogen forskel på at tage differensen og
så at angive den analytisk differentierede funktion, forudsat at
d er passende lille så det er en god approximation.

Du kan så udregne gradienter og bruge dem iterativt.

Det er dog ikke helt indlysende for mig hvordan man i det helt
generelle tilfælde hvor man intet ved om f kan vælger en "optimal" d.


Med simulated annealing (Monte Carlo simulation hvor temperaturen sænkes)
eller genetiske algoritmer kan du også minimerer en ukendt funktion uden
at antage at den er differentiabel.

--
Mvh. Carsten Svaneborg
http://gauss.ffii.org

---

> Det er dog ikke helt indlysende for mig hvordan man i det helt
> generelle tilfælde hvor man intet ved om f kan vælger en "optimal" d.

Nej. Umiddelbart kan man vel vælge en d som så lille som muligt uden at man
for får stor forholdsmæssig unøjagtigthed i dy, men hvor lille det er...

> Med simulated annealing (Monte Carlo simulation hvor temperaturen sænkes)
> eller genetiske algoritmer kan du også minimerer en ukendt funktion uden
> at antage at den er differentiabel.

Ja, det er også en mulighed som jeg har brugt (i det små) tidligere. Jeg
ville bare gerne prøve om jeg kunne finde en maer matematisk metode, og lære
at bruge den ordentligt.

---

Scripsit "Jakob Nielsen" <snail@road.rain.no.mail>

> Hvis jeg kender f(x), men ikke selve funktionen, så kan jeg selvsagt ikke
> differentiere den og dermed kan jeg ikke umiddelbart minimere den.

Det bedste du kan håbe på er naturligvis at finde noget der ligner et
lokalt minimum, for a priori kan du jo ikke være sikker på at du ikke
overser en smal dyb dal et sted i grafen (fx skabt af et eller andet
ræsonnansfænomen).

> Er metoden slet og ret at estimere f'(x) som (f(x+½d)-f(x-½d))/d og
> bruge det som hældningen?

Her er et alternativt forslag. Antag at du har punkter x<y<z så f(y)
er mindre end både f(x) og f(z). Så ved du at f må have et lokalt
minimum et sted mellem x og z. Vælg endnu et punkt w <> y mellem
x og z, fx (uden tab af generalitet) x<y<w<z. Hvis f(w) < f(y), kan
du udskifte x,y,z med y,w,z og begynde forfra. Ellers udskift x,y,z
med x,y,w.

En mulig måde at vælge w på er som toppunktet i det
andengradspolynomium der falder sammen med f i punkterne x, y og z.
Men hvis det er meget tæt på y, må man sørge for at flytte det et
lille stykke væk - hvis man går til venstre og til højre hver anden
gang dette indtræffer og rykker en fast lille brøkdel af afstanden til
x hhv z, kan man opnå en hurtigere konvergens i slutfasen.

--
Henning Makholm "The compile-time type checker for this
language has proved to be a valuable filter which
traps a significant proportion of programming errors."

---

> Her er et alternativt forslag. Antag at du har punkter x<y<z så f(y)
> er mindre end både f(x) og f(z). Så ved du at f må have et lokalt
> minimum et sted mellem x og z. Vælg endnu et punkt w <> y mellem
> x og z, fx (uden tab af generalitet) x<y<w<z. Hvis f(w) < f(y), kan
> du udskifte x,y,z med y,w,z og begynde forfra. Ellers udskift x,y,z
> med x,y,w.

Det er binær partionering, så vidt jeg husker? Den tænkte jeg ikke på lige
nu, men du har vel egentlig ret i at den kan være lige så god; og simpel er
den jo i hvert fald. Hvis je

> En mulig måde at vælge w på er som toppunktet i det
> andengradspolynomium der falder sammen med f i punkterne x, y og z.
> Men hvis det er meget tæt på y, må man sørge for at flytte det et
> lille stykke væk - hvis man går til venstre og til højre hver anden
> gang dette indtræffer og rykker en fast lille brøkdel af afstanden til
> x hhv z, kan man opnå en hurtigere konvergens i slutfasen.

Det trick kendte jeg ikke. Jeg vil prøve et eksempel lidt senere *ser på
uret* jeg mener.. lidt tidligere..eller...

---

Jakob Nielsen wrote:
> Det trick kendte jeg ikke. Jeg vil prøve et eksempel lidt senere *ser på
> uret* jeg mener.. lidt tidligere..eller...

Hennings forslag er nem at have med at gøre. Men hvis du har lyst til
at mere avancerede muligheder, som for eksempel parabelmetoden, så
kig lidt på Numerical Recipes kapitel 10:

<http://www.library.cornell.edu/nr/bookcpdf.html>

--
Jens Axel Søgaard

---

Jakob Nielsen wrote:
> Hvis jeg kender f(x), men ikke selve funktionen, så kan jeg selvsagt ikke
> differentiere den og dermed kan jeg ikke umiddelbart minimere den. Er
> metoden slet og ret at estimere f'(x) som (f(x+½d)-f(x-½d))/d og bruge det
> som hældningen? Tilsvarende kan man finde den anden afledte ved at bruge to
> estimater for f'(x) og så fremdeles. Er det den gængse måde eller er der et
> eller andet smart matematisk trick som jeg ikke kender til her?

Hvis du er ude i numerisk løsning er der Downhill Simplex:

http://en.wikipedia.org/wiki/Downhill_simplex

Mvh. Michael.
--
Which is more dangerous? TV guided missiles or TV guided families?
Visit my home page at http://michael.zedeler.dk/
Get my vcard at http://michael.zedeler.dk/vcard.vcf

---

> http://en.wikipedia.org/wiki/Downhill_simplex

Takker. Jeg kigger på den.
Hvad menes der egentlig med "for minimising an objective function" objektiv
funktion? Er det en funktion hvor man kun kender funktionsværdien for et
givent input, men ikke selve funktionen?

---

Jakob Nielsen wrote:
>>http://en.wikipedia.org/wiki/Downhill_simplex
>
>
> Takker. Jeg kigger på den.
> Hvad menes der egentlig med "for minimising an objective function" objektiv
> funktion?

"Objective function" betyder bare noget i stil med "målfunktion" eller
"den funktion, der har vores interesse".

Mvh. Michael.
--
Which is more dangerous? TV guided missiles or TV guided families?
Visit my home page at http://michael.zedeler.dk/
Get my vcard at http://michael.zedeler.dk/vcard.vcf

---

> Hvis du er ude i numerisk løsning er der Downhill Simplex:
>
> http://en.wikipedia.org/wiki/Downhill_simplex

En mere udførlig forklaring på den simple metode er her
http://math.fullerton.edu/mathews/n2003/NelderMeadMod.html

Det der undrer mig lidt er at man har trekanten BGW hvor f(B)<=f(G)<=f(W)
Derefter spejler man W omkring linien BG. Ville det ikke være mere effektivt
hvis man istedet brugte de tre funktionsværdier til at beregne hældningen
for trekanten og lod W glide i retning af "nedad" istedet for at spejle lige
over BG? Hvis nu f(B) er meget mindre end f(G), så burde W vel flyttes over
linien BG, men mere i retning af B end G?

---

Jakob Nielsen wrote:
>>Hvis du er ude i numerisk løsning er der Downhill Simplex:
>>
>>http://en.wikipedia.org/wiki/Downhill_simplex
>
>
> En mere udførlig forklaring på den simple metode er her
> http://math.fullerton.edu/mathews/n2003/NelderMeadMod.html
>
> Det der undrer mig lidt er at man har trekanten BGW hvor f(B)<=f(G)<=f(W)
> Derefter spejler man W omkring linien BG. Ville det ikke være mere effektivt
> hvis man istedet brugte de tre funktionsværdier til at beregne hældningen
> for trekanten og lod W glide i retning af "nedad" istedet for at spejle lige
> over BG?

Jeg tror at simplex-algoritmen vil køre hurtigere, end hvis man skal til
at estimere hældninger. Det er også vigtigt at medtage at den
geometriske figur bliver mindre, så den ikke løber forbi det minimum,
den prøver at finde.

> Hvis nu f(B) er meget mindre end f(G), så burde W vel flyttes over
> linien BG, men mere i retning af B end G?

Idéen er at den kant, som er tættest på det minimum, man leder efter,
ikke skal flyttes. Algoritmen vil altså beholde kanten (B,f(B)) indtil
en af de nye kanter, der er fundet, er lavere. Hvis funktionen ikke er
alt for mærkelig, vil de andre kanters højder konvergere imod noget, som
er lavere (med mindre man i (B,f(B)) tilfældigvis har ramt det lokale
minimum, man ledte efter).

Mvh. Michael.
--
Which is more dangerous? TV guided missiles or TV guided families?
Visit my home page at http://michael.zedeler.dk/
Get my vcard at http://michael.zedeler.dk/vcard.vcf

---

> Jeg tror at simplex-algoritmen vil køre hurtigere, end hvis man skal til
> at estimere hældninger.

Det er muligt. Det kan være at du har ret i at det er bedre at tage en
hurtig itteration mere end at lave nogle færre og mere optimale skridt.


> Det er også vigtigt at medtage at den geometriske figur bliver mindre, så
> den ikke løber forbi det minimum, den prøver at finde.

Ja. Jeg smed lige et hurtigt eksempel sammen og glemte sjovt nok netop den
del. Bare en tanketorsk, men resultatet var selvfølgelig at figuren stod og
flimrede henne over et minimum.

> Idéen er at den kant, som er tættest på det minimum, man leder efter, ikke
> skal flyttes. Algoritmen vil altså beholde kanten (B,f(B)) indtil en af de
> nye kanter, der er fundet, er lavere.

Ja, det forstår jeg. Det jeg mener er bare at man kunne flytte W over linien
BG til en ny position R, som ikke nødvendigvis var en spejling omkring
midtpunktet på linien BW, men måske istedet trukket mere i retning af B,
hvis f(B) er markant mindre end f(G).

---

> Hvis du er ude i numerisk løsning er der Downhill Simplex:

Lige et spørgsmål. For en parameter har man to punkter som springer buk, for
to parametre har man en trekant der vipper på plads og for tre parametre har
man hvad? En tetraede hvor den dårligste hjørne spejles over på den anden
side af det plan de tre andre punkter ligger i? Hvad er den generelle metode
for n parametre hvor man har n+1 punkter? Man spejler det dårligste punkt
over det hyperplan som de andre n punkter udgører, hvilket gøres ved at
projektere punktet på planet og forlænge vektoren fra punktet til
projektionspunktet til det dobbelte? Det må vel være fremgangsmåden, men jeg
synes ikke mine links kommer ind på det.

Hvad siger man at metodens konvergeringshastighed er?

---

> hvor den dårligste hjørne spejles over på den anden
> side af det plan de tre andre punkter ligger i?

Nej, dit fjols. Man spejler ikke omkring planet men omkring middelpunktet.
Helt ærligt! Så følg dog lidt med. Tsk tsk!

---

Jakob Nielsen wrote:
>>Hvis du er ude i numerisk løsning er der Downhill Simplex:
>
>
> Lige et spørgsmål. For en parameter har man to punkter som springer buk, for
> to parametre har man en trekant der vipper på plads og for tre parametre har
> man hvad? En tetraede hvor den dårligste hjørne spejles over på den anden
> side af det plan de tre andre punkter ligger i? Hvad er den generelle metode
> for n parametre hvor man har n+1 punkter?

Det er som du skriver. Hvis man skal finde minimum af en funktion, der
virker på et n-dimensionelt rum, skal man bruge en n+1-dimensionel
"hypertetraede".

> Man spejler det dårligste punkt
> over det hyperplan som de andre n punkter udgører, hvilket gøres ved at
> projektere punktet på planet og forlænge vektoren fra punktet til
> projektionspunktet til det dobbelte?

Det er noget tid siden at jeg brugte den, men noget i den stil. Som jeg
husker det, skal man netop ikke lave en ren spejling, men sørge for at
den nye vinkel er lidt mere stump, så figuren langsomt bliver mindre.

> Det må vel være fremgangsmåden, men jeg
> synes ikke mine links kommer ind på det.

Jeg fandt metoden i en bog om numerisk optimering. Grunden til at jeg
valgte den, var fordi den var meget enkel at implementere.

> Hvad siger man at metodens konvergeringshastighed er?

Ikke andet end at den er relativt dårlig, hvilket skal ses i forhold til
hvor enkel den er at implementere.

Mvh. Michael.
--
Which is more dangerous? TV guided missiles or TV guided families?
Visit my home page at http://michael.zedeler.dk/
Get my vcard at http://michael.zedeler.dk/vcard.vcf

---

> Ikke andet end at den er relativt dårlig, hvilket skal ses i forhold til
> hvor enkel den er at implementere.

Ja, det tog vist ikke mere end 10 minutter at stoppe den ind i et
eksisterende program, der beregnede forskellige funktionsværdier. Man skal
naturligvis huske på at hvis man ikke kører voldsomt mange minimeringer, så
er det lidt ligegyldigt om det tager 0.01s eller 0.5s at finde et minimum