Forumul Scientia

Matematică şi Logică => Matematică - probleme generale => Subiect creat de: CriSci din Mai 30, 2011, 05:19:45 PM

Titlu: Cautare multidimensionala
Scris de: CriSci din Mai 30, 2011, 05:19:45 PM
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.
Titlu: Răspuns: Cautare multidimensionala
Scris de: florin_try din Mai 30, 2011, 08:05:26 PM

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. 




Titlu: Răspuns: Cautare multidimensionala
Scris de: CriSci din Mai 30, 2011, 10:50:42 PM
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.
Titlu: Răspuns: Cautare multidimensionala
Scris de: HarapAlb din Mai 30, 2011, 11:49:09 PM
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 ?
Titlu: Răspuns: Cautare multidimensionala
Scris de: CriSci din Mai 31, 2011, 09:04:05 AM
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.
Titlu: Răspuns: Cautare multidimensionala
Scris de: florin_try din Mai 31, 2011, 10:25:45 AM

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.



Titlu: Răspuns: Cautare multidimensionala
Scris de: CriSci din Mai 31, 2011, 11:11:46 AM
Multumesc florin pentru ajutor,o sa incerc sa implementez Powel.
Titlu: Răspuns: Cautare multidimensionala
Scris de: CriSci din Iunie 03, 2011, 10:49:31 AM
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.
Titlu: Răspuns: Cautare multidimensionala
Scris de: florin_try din Iunie 04, 2011, 02:18:35 AM
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.
Titlu: Răspuns: Cautare multidimensionala
Scris de: CriSci din Iunie 05, 2011, 05:37:17 PM
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.