Download - Newton Modif Clasica-eremia,Hampau
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
1/11
Metoda Newtonmodificata clasica
Studenti:
Eremia Vali-Ionut
Hampau Bogdan
Grupa: 443A
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
2/11
Metoda Newton modificata clasica
Este o metoda de cautaremultidimensionala.
Deoarece metoda Newton nu este
neaparat convergenta se folosescvariante modificate care incearcaevitarea problemelor.
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
3/11
Metoda Newton modificata clasica
Unele dintre probleme apar, incazul in care functia nu estepatratica, datorita faptului ca
aproximarea functiei obiectiv prinseria Taylor la termenul de gradul2 este grosiera.
Iar solutia de optim este:
xk+1 = xk H-1
(xk)
* f(xk)
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
4/11
Metoda Newton modificata clasica
1) Matricea Hessiana H(xk) estimatalocal este singulara in xk si prin
urmare nu poate fi determinatasolutia Newton xk+1 cu care sacontinuam algoritmul de optimizare.
2) Desi se poate determina H-1inpunctul xk , rezulta f(xk+1) > f(xk).
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
5/11
Metoda Newton modificata clasica
In cazul in care functia obiectiv nu estepatratica, punctul curent de aproximare
este departe de solutia de optim, neasteptam ca aproximarea de gradul doial funtiei obiectiv sa fie grosiera, iaraplicarea unui pas Newton clasic poate
conduce la un urmator punct cuprobleme d.p.v. al convergentei. Inaceasta situatie, o solutie care inlaturamacar partial problemele posibile este:
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
6/11
Metoda Newton modificata clasica
a) pastrarea directie de inaintare data de solutiaNewton;
b) introducerea unui parametru de cautare kastfel incat:
xk+1 = xkk * H-1(x0)* f(xk)unde k este ales sa minimizeze functia obiectiv
si se determina prin optimizare 1-D a funtieiobiectiv pe directia:
H0-1 * f(xk)
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
7/11
Metoda Newton modificata clasica
In apropierea solutiei ne asteptam cak sa fie aproximativ 1.
Introducerea acestui parametrupentru puncte generale eliminaposibilitatea ca functia obiectiv sacreasca cand k = 1 ca urmare atermenilor nepatratici.
Si Hessianul H-1(x0) in punctul initial
x0 este folosit in intregul proces de
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
8/11
Metoda Newton modificata clasica
Eficacitatea procedurii este guvernata decat de rapid se schimba Hessianul.
Dificultatile de calcul sunt evidente.Trebuiesa calculam:
-matricea hessian H(x0);
-inversa matricei hessian H
-1
(x0)(inversa unei matrice (n x n)implica n3 inmultiri).
Si pe fiecare iteratie se calculeaza:
-vectorul gradient f(xk)
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
9/11
Metoda Newton modificata clasica
Algoritm:
Pasul 1: Initializare x0;
Pasul 2: Calculam matricea hessian afunctiei obiectiv si inversa acesteia in
punctul x0.
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
10/11
Metoda Newton modificata clasica
Algoritm:
Pasul 3: Pentru k=0, 1, 2, 3,
Calculam directia de cautare:
dk = H0-1 * f(xk)
Calculam k prin optimizare 1-D a funtieif( ) = f(xk + dk)
pe directia dk.
xk+1 = xkk * dk
-
7/31/2019 Newton Modif Clasica-eremia,Hampau
11/11
Metoda Newton modificata clasica
Notiuni teoretice:
Definim gradientulfunctiei f : X R
Definim matricea hessiana a functiei
f : X R