Calcul paralel - metodă de gradient conjugat

Introducere

Metodele de optimizare sunt în general metode de descreştere, ce determină minimul unei funcţii U de n variabile reale care se numeşte funcţie scop sau funcţie obiectiv. De aici şi denumirea lor de metode de minimizare a funcţiilor de mai multe variabile. Evident, problema găsirii maximului revine la minimizarea funcţiei cu semn schimbat. Metodele de descreştere au convergenţa globală, adică permit găsirea soluţiei chiar dacă punctul de plecare este îndepărtat de soluţie.

Metodele de optimizare au un domeniu de aplicabilitate foarte larg. Pe de o parte, majoritatea fenomenelor naturii sau economice reprezintă compromisuri între cauze contradictorii, şi ca atare multe din problemele ingineriei, economiei, matematicii, statisticii, medicinei, dar mai cu seamă procesele decizionale se pot formula ca probleme de optimizare. Pe de altă parte, majoritatea metodelor numerice pot fi reformulate ca probleme de optimizare. Aceste reformulări duc uneori la obţinerea unor metode performante, cum ar fi cele pentru rezolvarea sistemelor de ecuaţii liniare, şi cele pentru rezolvarea sistemelor de ecuaţii neliniare

Metodele de gradient conjugat reprezintă o contribuţie importantă în panoplia metodelor de optimizare fără restricţii de mari dimensiuni. Algoritmii asociaţi acestor metode sunt caracterizaţi de cerinţe modeste de memorie şi au proprietăţi foarte bune de convergenţă globală. Popularitatea lor este datorată în parte simplităţii expresiei lor algebrice, implementării foarte rapide şi uşoare în programe de calcul, precum şi eficienţei lor în rezolvarea problemelor cu un număr mare de variabile.

Metodele de gradient conjugat au fost proiectate de Magnus Hestenes (1906-1991) şi Eduard Stiefel (1909-1978) în lucrarea Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards Sec. B. 48, 409-436 (1952) în care au prezentat un algoritm pentru rezolvarea sistemelor algebrice liniare, cu matricea simetrică şi pozitiv definită. În 1964, metoda a fost extinsă de Fletcher şi Reeves la probleme de optimizare neliniară fără restricţii. De atunci, un număr foarte mare de algoritmi de gradient conjugat au fost elaboraţi. Chiar dacă algoritmii de gradient conjugat au peste 50 de ani de existenţă, totuşi aceştia continuă să fie de un considerabil interes în particular datorită proprietăţilor lor de convergenţă şi eficienţei în rezolvarea problemelor de optimizare de mari dimensiuni.

Metodele de gradient conjugat nu se deosebesc esenţial de metodele cvasi-Newton din punct de vedere al scopului, şi anume obţinerea minimului unei forme pătratice în n iteraţii. Ambele clase de metode necesită calculul derivatelor parţiale de ordinul întâi şi au aceeaşi convergenţă superliniară. Deosebirea esenţială constă în faptul că metodele de gradient conjugat nu necesită memorarea unei matrice.

Consideraţii teoretice

Metodele de gradient.

Aceste metode sunt tipic de ordinul I şi sunt caracterizate prin alegerea în fiecare punct curent vk a unei direcţii de deplasare dk opusă gradientului local:

dk = -gk (1)

Dezvoltând în serie Taylor funcţia în vecinătatea punctului vk şi reţinând doar termenii de ordinul întâi, se obţine:

(2)

Însă,

(3)

egalitatea având loc numai în cazul (1). Prin urmare, pentru orice pas sk >0 alegerea direcţiei de căutare conform relaţiei (1) asigură local descreşterea maximă posibilă a funcţiei obiectiv f.

Algoritmul de calcul al punctului de minim prin metoda gradientului este prezentat în cele ce urmează:

0. Se alege un punct iniţial astfel încât mulţimea

să fie mărginită.

1. Se iniţializează k = 0.

2. Se calculează gk = f v (vk ) .

Dacă || g k ||= 0 , atunci şi algoritmul este oprit.

Altfel, se alege direcţia dk = -gk şi se trece la pasul 3.

3. Se determină pasul sk .

4. Se calculează vk+1 = vk + sk dk , se actualizează k prin înlocuirea lui k cu k+1 şi se revine la pasul 2.