Metoda gradientului şi metoda Newton

Metoda gradientului şi metoda Newton sunt două metode remarcabile de rezolvare a problemelor de optimizare atât necondiţionate, cât şi condiţionate. Descrierea succintă prezentată infra sper să fie un suport util la orele de laborator când se elaborează şi se testează programele. Lista de probleme pentru testare va fi completată periodic.

Se consideră problema:

z = f(x) → min,  x ∈ ℝn

unde f : ℝn → ℝ este o funcţie diferenţiabilă de două ori.

Se cere să se determine un punct care îl aproximează pe cel de minim local cu o exactitate dată ε>0. Exactitatea se poate referi: la argument (ε1 ), la valoarea funcţiei (ε2 ), la argument şi la valoarea funcţiei concomitent (ε = min{ε1 , ε2 }), la gradient (ε 3 ) etc.

Procesul de calcul în metoda gradientului se desfăşoară conform formulei iterative:

xk+1 = xk – αk f‘(xk), k = 0, 1, 2, …

unde:

  • f‘(xk) = ∇f (x1, …, xn) = (∂f/∂x1, ∂f/∂x2, …, ∂f/∂xn) este gradientul funcţiei obiectiv în punctul xk,
  • αk este lungimea pasului efectuat în direcţia antigradientului – f‘(xk) .

Lungimea pasului αk se calculează conform unuia dintre procedeele:

  1. αk = argmin α≥0 f(xk – α f‘(xk)) (metoda pasului optim);
  2. αk = αλs, unde α este o mărime numerică dată, λ ∈ (0;1), s este cea mai mică putere care asigură o micşorare a valorii funcţiei obiectiv, adică acel s pentru care se verifică inegalitatea f(xk – αf‘(xk)) < f(xk ) (metoda fragmentării pasului);
  3. lungimea pasului este constantă în orice iteraţie.

Pentru a lansa procesul iterativ se alege un punct iniţial x0 din domeniul de convergenţă.

În calitate de condiţii de oprire a procesului iterativ pot fi folosite condiţii de tipul:

||xk+1 xk ||<ε1,
|f(xk+1 ) – f(xk )|<ε2,
||f‘(xk )||<ε3.

După l iteraţii pot fi aplicate şi condiţii de oprire de tipul:

Σi=0,…,l-1 ||xk-i+1 xk-i || < ε4,
Σi=0,…,l-1 |f(xk-i+1 ) – f(xk-i )|< ε5.

O realizare rudimentară a metodei gradientului în sistemul Mathematica poate arăta astfel:

ε=10-3;  X={x,y};
f[{x_, y_}] := 100 (y-x2)2+(1-x)2
grad[{x_, y_}]=D[f[X],{X}];
X={-1.2, 1};
While[Norm[grad[X]]>ε,
X=X – α grad[X]/.Minimize[{f[X – α grad[X]], α ≤ 1}, α] [[2]]
]
Print[N[X], f[X]]

În metoda lui Newton:

xk+1 = xk – f”(xk)-1 f‘(xk), k = 0, 1, 2, …

unde f”(xk) este matricea lui Hesse (matricea derivatelor parţiale de ordinul doi calculate în punctul xk), iar f”(xk)-1 este matricea inversă ei.

Programul ce urmează reprezintă o simplă realizare a metodei Newton în sistemul Mathematica.

ε=10-3;  X={x,y};
f[{x_, y_}] := 100 (y-x2)2+(1-x)2
grad[{x_, y_}]=D[f[X],{X}];
H[{x_, y_}]=D[grad[X],{X}];
X={-1.2, 1};
While[Norm[grad[X]]>ε,
X=X – Inverse[H[X]].grad[X];
]
Print[N[X], f[X]]

În metoda modificată Newton:

xk+1 = xk – αk f”(xk)-1 f‘(xk), k = 0, 1, 2, …

unde αk este lungimea pasului (se determină prin procedee similare cu cele din metoda gradientului).
Metoda gradientului converge mai rapid la depărtare de punctul de minim, unde norma gradientului este suficient de mare. În imediata vecinătate a punctului de minim metoda poate să conveargă lent.
Metoda Newton converge rapid în apropiere de punctul de minim, unde funcţia poate fi aproximată bine cu polinoame de gradul doi. La depărtare de punctul de minim, ea poate, în general, să nu conveargă.
În concluzie, metodele pot fi aplicate combinat:

  • la depărtare de punctul de minim (unde norma gradientului e mare) se aplică metoda gradientului,
  • în apropiere (unde norma gradientului e mică) se aplică metoda Newton.

La programarea metodelor pe calculator sunt utile formulele de calcul aproximativ al derivatelor prin diferenţe:

f/∂xj = (f(xj+h,x-j)-f(xj-h,x-j))/(2h),

f2/∂xj 2= (f(xj+2h,x-j)-2f(x)+f(xj-2h,x-j))/(4h2),

f2/∂xi xj = (f(xi+h,xj+h,x-ij)-f(xi+h,xj-h,x-ij)-f(xi-h,xj+h,x-ij)+f(xi-h,xj-h,x-ij))/(4h2),

unde

x-j = (x1, x2, …, xj-1, xj+1,…, xn),

adică indicele negativ la un vector semnifică omiterea acelui indice.

Programele se testează cu ajutorul unor funcţii speciale, cum sunt, spre exemplu, următoarele:

Funcţia (banană) Rosenbrock

f(x) = 100 (x2-x12)2+(1-x1)2,

x0 = (-1.2; 1), x* = (1; 1),  f(x*) = 0.

Funcţia (cupă)

f(x) = x12 /2 – 0.065625 x14 + x16/384- x1x2/2+x22,

x0 = (-2.5; 5), x* = (0; 0),  f(x*) = 0.

x0 = (-5; 1), x* = (-3.4951; -0.873776),  f(x*) = 0.298638.

x0 = (5; 1), x* = (-3.4951; -0.873776),  f(x*) = 0.298638.

Anunțuri

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s