Metoda de gradient conjugat 1

Termenul "metoda gradientului conjugat" este un exemplu al modului în care expresiile fără sens, devenind obișnuite, sunt considerate date și nu provoacă nici o încurcătură. Faptul este că, cu excepția unui caz particular, care nu este de interes practic, gradientele nu sunt conjugate, iar direcțiile conjugate nu au nimic în comun cu declivitățile. Denumirea metodei reflectă faptul că această metodă de a găsi un extremum necondiționat combină conceptele de gradient al funcției obiective și direcțiilor conjugate.

Câteva cuvinte despre notația folosită mai jos.

Produsul scalar al două vectori este scris cu $ x ^ Ty $ și reprezintă suma scalarelor: $ \ sum_ ^ n \, x_i \, y_i $. Rețineți că $ x ^ Ty = y ^ Tx $. Dacă x și y sunt ortogonale, atunci $ x ^ Ty = 0 $. În general, expresiile care sunt convertite într-o matrice 1x1, cum ar fi $ x ^ Ty $ și $ x ^ TA_x $, sunt considerate ca fiind cantități scalare.

Inițial, metoda gradientului conjugat a fost dezvoltată pentru a rezolva sisteme de ecuații algebrice liniare de formă:

unde x este un vector necunoscut, b este un vector cunoscut, iar A este o matrice cunoscută, pătrată, simetrică, pozitiv-definită. Soluția acestui sistem este echivalentă cu găsirea unui minim de formă patratică corespunzătoare.
O formă patratică este pur și simplu o funcție scalară, o funcție patratică a unui vector x al următoarei forme:

Prezența unei astfel de conexiuni între matricea transformării liniare A și funcția scalară f (x) face posibilă ilustrarea unor formule de algebră liniară prin figuri intuitive. De exemplu, o matrice A se spune a fi pozitiv-definită dacă pentru orice vector nonzer x x următoarele sunt adevărate:

Figura 1 arată modul în care arată formele patrate, respectiv, pentru o matrice pozitiv-definită (a), o matrice negativă-definită (b), o matrice pozitivă nedeterminată (c), o matrice nedefinită (d).

Adică, dacă matricea A este pozitivă, atunci în loc de a rezolva sistemul de ecuații 1, se poate găsi minimul funcției sale patrate. Mai mult, metoda de gradient conjugat va face acest lucru în n sau mai puține etape, unde n este dimensiunea vectorului necunoscut x. Deoarece orice funcție netedă în apropierea punctului minim este bine aproximată de o funcție patratică, aceeași metodă poate fi folosită pentru a minimiza funcțiile ne-patrate. În acest caz, metoda încetează să mai fie finită, dar devine iterativă.

Este recomandabil să începeți să luați în considerare metoda gradientului conjugat luând în considerare o metodă mai simplă de căutare a extremumului unei funcții, metoda celei mai abrupte coborâri. Figura 2 prezintă traiectoria mișcării până la punctul minim prin metoda celei mai abrupte coborâri. Esența acestei metode:

• gradientul este calculat la punctul de pornire x (0), iar mișcarea se face în direcția antigradientului până când funcția obiectivului scade;
• în punctul în care funcția încetează să scadă, gradientul este calculat din nou, iar coborârea continuă într-o nouă direcție;
• Procesul se repetă până când se atinge punctul minim.

În acest caz, fiecare nouă direcție de mișcare este ortogonală cu cea anterioară. Există o modalitate mai sensibilă de a alege o nouă direcție? Există și se numește metoda direcției conjugate. Și metoda gradientului conjugat este doar un grup de metode de direcții conjugate. Figura 3 prezintă traiectoria mișcării până la punctul minim atunci când se folosește metoda gradientului conjugat.

Determinarea conjugat este formulat după cum urmează: doi vectori x și y sunt numite A-conjugat (sau conjugat cu matricea A) sau A-ortogonali dacă produsul scalar al lui x și Ay egal cu zero, adică:

Conjugarea poate fi considerată o generalizare a conceptului de ortogonalitate. Într-adevăr, atunci când matricea A - matricea identitate, conform ecuației 4, vectorii x și y - ortogonale. Și în caz contrar se poate demonstra relația dintre concepte și conjugat ortogonale: mental Figura întindere 3, astfel încât liniile de nivel egal de elipse transformat într-un cerc, cu direcțiile ortogonale asociate vor fi doar.

Rămâne de văzut cum se calculează direcțiile conjugate. Una dintre căile posibile este utilizarea metodelor de algebră liniară, în special a procesului de ortogonalizare Gramm-Schmidt. Dar pentru aceasta este necesară cunoașterea matricei A, prin urmare, pentru majoritatea problemelor (de exemplu, învățarea rețelelor neuronale multistrat), această metodă nu este adecvată. Din fericire, există alte metode iterative de calcul al direcției conjugate, cea mai faimoasă fiind formula Fletcher-Reeves:

Ecuația 5 înseamnă că noua direcție obținută prin adăugarea antigradient conjugat la punctul de rotire și direcția anterioară de mișcare, înmulțită cu coeficientul calculat prin formula 6. Directions calculate din Formula 5, sunt conjugate dacă funcția care urmează să fie redusă la minimum este definită sub forma 2. Aceasta este, pentru pătratică funcții, metoda gradientelor conjugate găsește un minim de n pași (n este dimensiunea spațiului de căutare). Pentru funcțiile de formă generală, algoritmul încetează să mai fie finit și devine iterativ. În acest caz, Fletcher și Reeves propun să reia procedura algoritmică la fiecare etapă n + 1.

Se poate oferi o altă formulă pentru determinarea direcției conjugate, formula Polak-Ribiere:

Metoda Fletcher-Reeves converge dacă punctul inițial este suficient de apropiat de minimul necesar, în timp ce metoda Polak-Reiber poate rar ciclic ciclic în cazuri rare. Cu toate acestea, acestea din urmă converg adesea mai rapid decât prima metodă. Din fericire, convergența metodei Polak-Reiber poate fi garantată prin alegerea lui $ \ beta = \ max \ $. Aceasta este echivalentă cu restaurarea unui algoritm cu condiția $ \ beta \ leq 0 $. Repornirea procedurii algoritmice este necesară pentru a uita ultima direcție de căutare și a porni din nou algoritmul în direcția coborârii rapide.

Apoi, este prezentat un algoritm pentru gradiente conjugate pentru a minimiza funcțiile unei forme generale (nequadratice).

1. Un antigradient este calculat la un punct arbitrar x (0).