Ştiri:

Vă rugăm să citiţi Regulamentul de utilizare a forumului Scientia în secţiunea intitulată "Regulamentul de utilizare a forumului. CITEŞTE-L!".

Main Menu

Cautare multidimensionala

Creat de CriSci, Mai 30, 2011, 05:19:45 PM

« precedentul - următorul »

0 Membri şi 1 Vizitator vizualizează acest subiect.

CriSci

Inainte de toate vreau sa salut toti membrii acestei comunitati fiindca sunt nou pe forum.Am deschis acest topic fiindca vreau sa implementez intr-un limbaj de programare un algoritm de cautare multidimensionala,mai exact Newton-Raphson.Problema este ca nu gasesc o explicatie clara si/sau o problema rezolvata ca sa vad cum "lucreaza".Astept sfaturi.

florin_try


Cautare multidimensionala a ce? A unui minim? A unui optim? A unui nod intr-un graph? Sau a fericirii?
Defineste concret problema, daca vrei sa ii afli solutia. Exemplu de enunt: "algoritm numeric pentru gasirea unui minim local a unei functii f(x1,x2,..xN), in spatiul N-dimensional dat de variablilele x1,x2,..xN". La asta te referi?

Atentie insa cu metoda Newton-Rapson: desi are convergenta quadratica, numarul de operatii cresc ca N^2, ceea ce o face inefectiva daca ai mai mult de vre-o 100 de variabile. Nici nu mi-as bate capul cu metoda Newton-Rapson, conjugate-gradient cu un preconditioner 'muncit' ar trebui sa fie calea. 





CriSci

Cautarea unui minim,dar daca ai unul si pentru fericire esti tare.Nu cred ca voi folosi vreodata 100 de variabile,algoritmul il fac in scop didactic.

HarapAlb

Mai multe informatii gasesti pe wikipedia: http://en.wikipedia.org/wiki/Newton%27s_method . Vezi ca are si generalizarea pentru mai multe variabile si functii. Metoda Newton-Raphson desi simpla ridica probleme pentru ca nu poate fi aplicata in general. Trebuie sa-ti gasesti un exemplu concret pe care functioneaza metoda asta si apoi sa incerci s-o implementezi. Poti alege o functie sau un sistem de functii neliniare, ceva de genul

[tex]\begin{eqnarray}ax^3+by^3-c &=& 0\\cx+dy - e &=& 0\end{eqnarray}[/tex]

care sa aiba solutie unica.

Ai inteles cum lucreaza algoritmul in cazul unei singure necunoscute ?

CriSci

Pentru o singura variabila stiu cum functioneaza algoritmul,este simplu.Se calculeaza raportul dintre valoarea functiei in punctul curent si valoarea derivatei,apoi se scade din punctul curent.Pentru mai multe variabile n-am idee.

florin_try


Fie functia f({x}) , unde {x}=x1,x2,...xN. Se cere minimum.

-------

Pai in primul rind cauti minimum pe o singura directie. Directia de cautare poate fi oricare din vectorii:
(1x1,0,0,...0), (0,1x2,...0),...,(0,0,...,1xN)
unde cu 1xN e vectorul unitate.
Sau directia de cautare poate fi o conbinatie lineara a vectorilor de mai sus.

Cum afli minimum pe o directie?
Alegi 3 puncte in directia data, a < b < c, si calculezi f(a),f(b),f(c)
Daca punctul din mijloc f(b) e mai mic decit extremitatile(f(b)<f(c)&&f(b)<f(a)), atunci intre extremitati (intre punctele a si c) ai un minim.

Pe urma poti aplica algoritmul (naiv) de injumatatire a intervalului.

Ceva la genul.
set __MAX_ITER=100; __ERROR=0.000001 //say
set a < b < c

iter=0;
do while (converge && iter<__MAX_ITER){
fa=f(a); fb=f(b); fc=f(c)
if (fb<fa&&fb<fc{ // trebuie sa fie un minim intre a si c
    a1=(a+b)/2;
    c1=(b+c)/2;
  }
  fa1=f(a1)
  fc1=f(c1)
  if (fa1<fa) { if (fa1<fb){b=a1} else {a=a1} }
  if (fc1<fc)  { if (fc1<fb){b=c1} else {c=c1} }
  iter+=1;
  converge  = abs(a-c)<__ERROR
}//dowhile

Daca functia f e complicat de calculat atunci fitezi o parabola cu cele 3 puncte a,b,c si cauti minimum parabolei fitate.  Te duci pe acel minim, alegi niste puncte in jurul lui la un anumit pas (desigur pe directia de cautare) si recalculezi punctele a,b,c cu formula exacta si repeti procesul.

Vezi 2 algoritmuri (+ codul C) in Numerical Recipies (cred ca e biblia oricarei persoane ce incepe sa intre in algoritmi numerici).
http://apps.nrbook.com/c/index.html
Vezi capitolul: 10.1 "Golden Search in one direction" - pagina 397 (ai codul integral la pg. 400-401 cum sa alegi intervalul initial si cautarea in sine)
Vezi capitolul: 10.2 "Parabolic interpolation and Brant Method ..." - pagina 402 (la fel, vezi ca ai codul integral la pagina 404 405)   
Iar codul dat la pagina 406 - 407 cred ca e cel mai util. (pentru mine a mers excelent in cam toate situatiile cind nu am stiut sa rezolv analitic whatever)

--------

Referitor la cautarea multidimensionala. Practic repeti algoritmul de mai sus pentru o directie data, schimbind succesiv directiile de cautare pina converge. Insa daca alegi anumite directii , ajungi garantat la minim in numar finit de pasi.

Tot din Numerical Recipies (  http://apps.nrbook.com/c/index.html )explica ce directii sa folosesti.
Vezi capitotul: 10.5 (Metoda Powell) incepe la pagina 412
Vezi si tu codul in C de la 417-418.

----

Iti spun sigur ca metoda asta Powel din Numerical Recipies e robusta, usor de implementat si inteles, si merge chiar si pentru functii complicate.




CriSci

Multumesc florin pentru ajutor,o sa incerc sa implementez Powel.

CriSci

#7
Am gasit un document in care este explicat algoritmul lui Powell,cu pseudocodul cat si exemplu.Problema este ca m-am blocat la cautarea minimului functiei pe o singura directie.In exemplul din fisierul atasat,la functia f(x,y)=cos(x)+sin(x) se pleaca din punctul X0(5.5,2),iar la prima iteratie se cauta minimul unidimensional intr-o singura directie pt. functia f(x)=cos(5.5+&)+sin(2).Aici m-am blocat,nu stiu in ce interval sa caut minimul.

florin_try

Destul de bine prezentata metoda Powell in linkul dat de tine.

Citat din: CriSci din Iunie 03, 2011, 10:49:31 AM
.Aici m-am blocat,nu stiu in ce interval sa caut minimul.

Ca sa folosesc terminologia de specialitate, problema ta se numeste: "bracketing a minimum".
Adica, sa gasesti un interval a<b in care functia are garantat un minim.
Ca sa 'bracket' a minimum ai nevoie de 3 puncte (pe directia considerata) a<c<b.
Daca f(c)<f(a) si f(c)<f(b), atunci intre a si b functia ta are minim.

In principiu, alegi in interval de placare a0, b0 (0..1) sa zicem, alegi un punct c0 in mijloc (c0=0.5) si vezi daca f(c0) e mai bica decit f in extremitati.
Daca nu, atuncti maresti intervalul initial de exemplu de la 0 la 1 la 0 ..2 sau -1..1 sau -1 .. 2. si vezi daca obtii  f(c)<f(a) si f(c)<f(b)'
Daca nu, atunci continui sa maresti intervalul.

Intervale prea mari la functiile cu multe minime (ca functia sin) s-ar putea sa te duca la alt minim.

Functii monoton crescatoare (ca f(x)=0.1x) nu vor avea nici un minim local, si deci nu ai ce minim braketa la ele. 

----

Vezi si: un goole seach "bracketing minimum"

Vezi si: http://mymathlib.webtrellis.net/optimization/nonlinear/one_dim/parabolic_extrapolation.html
http://www.codecogs.com/code/maths/optimization/bracket.php
si desigur Numerical Recipies (nr.com) http://apps.nrbook.com/c/index.html pagina 400.

CriSci

#9
Citat din: florin_ din Iunie 04, 2011, 02:18:35 AM
Destul de bine prezentata metoda Powell in linkul dat de tine.

Ca sa folosesc terminologia de specialitate, problema ta se numeste: "bracketing a minimum".
Adica, sa gasesti un interval a<b in care functia are garantat un minim.
Ca sa 'bracket' a minimum ai nevoie de 3 puncte (pe directia considerata) a<c<b.
Daca f(c)<f(a) si f(c)<f(b), atunci intre a si b functia ta are minim.

http://www.codecogs.com/code/maths/optimization/bracket.php
Am implementat algoritmul de bracket,pentru f(x)=x*sin(x) a=4 si b=5 obtin c=6.6180,exact ca in linkul de mai sus.Dar tot nu realizez cum trebuie sa gasesc minimul pt functia f(P0+γ1*U1)=cos(5.5 + γ1 ) + sin(2) din exemplu Powell atasat de mine.