metode optimiranja

O matematiki, številih, množicah in računih...
Post Reply
User avatar
fogl
Posts: 545
Joined: 7.11.2004 20:25
Location: Radovljica

metode optimiranja

Post by fogl » 15.11.2010 9:09

Gledam malo metode optimiziranja, pa vedno piše da mora biti funkcija zvezna in odvedljiva... Kaj pa če se funkcije analitično sploh ne da zapisat (da je npr. rezultat neke numerične simulacije), bi lahko v tem primeru odvode (če bi uporabil npr. metodo spusta) aproksimiral tako, da bi izračunal vrednost funkcije pri x_i-dx_i in pri x_i+dx_i in potrem aproksimiral odvode v vseh smereh? Kako se imenujejo take metode optimiziranja (nikjer nisem našel nič napisanega o tem)?

User avatar
Aniviller
Posts: 7263
Joined: 15.11.2004 18:16

Re: metode optimiranja

Post by Aniviller » 15.11.2010 9:22

Zveznost in odvedljivost velja tudi za neanaliticno podane funkcije - se pac odvodi poracunajo numericno, ta pogoj samo zagotovi da bo metoda sploh delovala (ce funkcija ni zvezna in odvedljiva, potem ne mores glede na okolico nicesar sklepat o tem kje je minimum in bo prakticno vsaka metoda odpovedala). Za izracun odvodov vecina numericnih optimizacijskih algoritmov ze avtomatsko poskrbi. V praksi se zelo redko optimizira analiticno podane funkcije - oziroma ponavadi niti ni smiselno razlocevat analiticno ali neanaliticno - metodi das neko funkcijo in dela z njo kar hoce. Tudi ce je funkcija analiticno podana (recimo pri fitanju) je ponavadi lazje racunat odvode numericno kot analiticno.

Obstajajo tako algoritmi ki zahtevajo samo funkcijo, kot tisti ki jim lahko podas tudi odvode. Poglej si malo Numerical Recipes, tam je opisanih veliko metod (taka brez odvodov je recimo powellova metoda). Ce delas z Mathematico si tudi lahko pogledas katere metode ima in kaksne lastnosti imajo.

User avatar
fogl
Posts: 545
Joined: 7.11.2004 20:25
Location: Radovljica

Re: metode optimiranja

Post by fogl » 15.11.2010 10:23

Kako pa lahko vem če je funkcija zvezna on odvedljiva, če pa ni analitično zapisana. Zame bi bila funkcija nek "black box", nek simulacijski program, ki bi za neke vrednosti spremenljivk izračunal vrednost funkcije. Pa se da Mathematico povezat z nekim zunanjim programom, da bi npr. zaganjala simulacijo pri vrednostih ki jih zahteva algoritem optimizacije v Mathematici?

User avatar
Aniviller
Posts: 7263
Joined: 15.11.2004 18:16

Re: metode optimiranja

Post by Aniviller » 15.11.2010 11:22

To ves iz narave problema. Ce majhna sprememba v parametru malo spremeni resitev, potem je zvezno - to si ni tezko predstavljat. Za odvedljivost je pa itak bolj slabo definirano ker vzame koncno velik korak. Edino tista crna skatla se mora konsistentno obnasat (ce je njen rezultat recimo "zrnat" ker se zadovolji z nekim priblizkom in ne racuna do konca, ali ce je problem take vrste, potem je boljse vzeti vecji korak za racunanje odvoda in bo pac rezultat malo slabo natancen).

S to odvedljivostjo se ponavadi ni treba pretirano ukvarjat. Poskusi in ce bo delalo potem je v redu.

Zunanji program sicer lahko klices (sintaksa je nekaj s klicajem, poglej po googlu). Pac napises neko mathematicino funkcijo ki notri klice ta program. Ampak to ne vem ce bo ravno hitro ce bo vedno znova klicalo nek program. Odvisno od tega koliko parametrov imas ampak ponavadi traja reda velikosti 10-20 iteracij da najde minimum in v vsaki tocki racuna odvod, kar pomeni da klice najmanj (n+1) krat to funkcijo ce je n stevilo parametrov.

Ce je program tudi tvoje delo (imas kodo), potem predlagam da naredis optimizacijo v istem programskem jeziku.

User avatar
fogl
Posts: 545
Joined: 7.11.2004 20:25
Location: Radovljica

Re: metode optimiranja

Post by fogl » 21.11.2010 20:55

Še nekaj me zanima... ali to optimiranje (ko kriterijska funkcija ni znana - da je nek "black box") deluje tudi v primeru, ko imamo neke omejitve enakosti (equality constraints)? Če funkcija za omejitev ni znana (če je ravno tako nek "black box") potem lahko najbrž samo s poskušanjem "zadanemo" prave vrednosti da je omejitev izpolnjena, ali kako - ne predstavljam si kako bi funkcioniralo iskanje rešitve.

User avatar
Aniviller
Posts: 7263
Joined: 15.11.2004 18:16

Re: metode optimiranja

Post by Aniviller » 21.11.2010 21:11

Enakosti niso problem. To znamo ze analiticno (to je vezan ekstrem) in numericno naredis isto - z lagrangeovimi multiplikatorji. To privede do tega da minimizacijo resujes veckrat, s tem da vmes delas neko iskanje nicle (bisekcija ali kaj podobnega) se za lagrangeov multiplikator. So tudi algoritmi, ki med spuscanjem proti ekstremu znajo tudi skrbet da ostanejo na vezi.

Hujsi problem so neenakosti (omejitve obmocja in podobno). V teh primerih nimas analiticnih pomagal in mora to opravljat namenski algoritem - niso ravno elegantni ampak obstajajo. Ce hoces uporabit iste algoritme kot za obicajno minimizacijo, lahko tukaj dodas neko "skatlasto" funkcijo, ki na meji zelo hitro naraste - s tem vsaj priblizno izpolnis omejitve.

User avatar
fogl
Posts: 545
Joined: 7.11.2004 20:25
Location: Radovljica

Re: metode optimiranja

Post by fogl » 24.11.2010 11:45

Zdaj sem zadevo stestiral. Naredil sem eno kratko kodo (klik), ki zgenerira fajl z vhodnimi podatki za simulacijo, požene simulacijo (nek zunanji program) in potem prebere rezultate te simulacije. Če sam ročno vnesem neke vrednosti (In[315] na linku) zadeva deluje. Ko pa funkcijo vstavim v FindMaximum, pa se program zažene samo enkrat, rezultat pa je napačen (zgleda kot da sploh ni počakal na rezultat simulacije in je kar takoj šel brat fajl, ki je ostal tam še od prejšnje simulacije). Mogoče kdo ve kaj bi lahko bilo narobe?

User avatar
fogl
Posts: 545
Joined: 7.11.2004 20:25
Location: Radovljica

Re: metode optimiranja

Post by fogl » 30.11.2010 13:06

Če bo še koga kaj takega matral: v funkciji je potrebno spremenljivke namesto m01_ definirat kot m01_?NumericQ. Ta dodatek za spremenljivko naj bi povedal da gre za številko, ne za simbol... kaj dela Mathematica brez tega dodatka pa ne bi vedel...

Post Reply