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


2/11

Metoda Newton modificata clasica

Este o metoda de cautaremultidimensionala.

Deoarece metoda Newton nu este

neaparat convergenta se folosescvariante modificate care incearcaevitarea problemelor.


3/11


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)


4/11


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).


5/11


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:


6/11


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/11


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


8/11


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)


9/11


Algoritm:

Pasul 1: Initializare x0;

Pasul 2: Calculam matricea hessian afunctiei obiectiv si inversa acesteia in

punctul x0.


10/11


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


11/11


Notiuni teoretice:

Definim gradientulfunctiei f : X R

Definim matricea hessiana a functiei

f : X R

Newton Modif Clasica-eremia,Hampau

Documents

Transcript of Newton Modif Clasica-eremia,Hampau