Metoda gradientului descendent#
Acest subcapitol intenționează să prezinte succint metoda gradientului descendent. Deși reprezintă o simplă lectură suplimentară, considerăm interesantă metoda utilizată, așadar o vom prezenta în câteva rânduri.
Gradient#
Noțiunea de gradient ar trebui să vă fie (parțial) cunoscută de la matematică.
Fie \(f:D\subseteq\mathbb{R}^n\rightarrow\mathbb{R}\), \(n\in{N}^*\), o funcție de \(n\) variabile, mai bine interpretată în acest context ca o funcție ce primește un vector și întoarce un număr. Atunci, pentru punctul (vectorul) \(\bm{x}=(x_1,x_2,\dots,x_n)\in D\), se definește vectorul \(\nabla f(\bm{x})\), denumit gradientul lui \(f\) în punctul \(\bm{x}\), astfel:
\[ \boxed{\nabla f(\bm{x})=\begin{bmatrix} \frac{\partial f}{\partial x_1}(\bm{x})\\\\ \frac{\partial f}{\partial x_2}(\bm{x})\\\\ \vdots\\\\ \frac{\partial f}{\partial x_n}(\bm{x}) \end{bmatrix}} \]Suntem interesați să definim această operație pe vectori pentru că prin ea se generalizează cumva operația de derivare. O altă notație utilizată în practică este \(\nabla f(\bm{x})=f'(\bm{x})\). Pentru a nu genera însă confuzii, vom prefera notația folosind operatorul nabla (\(\nabla f(\bm{x})\)).
Funcția de minimizare#
Fie \(A\bm{x}=\bm{b}\) un sistem de ecuații liniare, unde \(A\in\mathbb{R}^{n\times n}\), \(\bm{x},\bm{b}\in\mathbb{R}^n\) și \(n\in\mathbb{N}^*\).
Atunci, prin definiție, funcția de minimizare a matricei \(A\) este dată de funcția \(f:\mathbb{R}^n\rightarrow\mathbb{R}\):
\[ f(\bm{u})=\left\langle\bm{u},A\bm{u}\right\rangle-2\left\langle\bm{b},\bm{u}\right\rangle \]Suntem interesați de această funcție deoarece este minimă în momentul în care \(\bm{u}\) este ales astfel încât să fie fie soluția sistemului \(A\bm{x}=\bm{b}\) (adică \(\bm{u}=\bm{x}\)), iar matricea \(A\) este simetrică și pozitiv-definită.
Vom calcula gradientul funcției de minimizare:
\[\begin{split} &\nabla f(\bm{u})=\nabla\left[\left\langle\bm{u},A\bm{u}\right\rangle-2\left\langle\bm{b},\bm{u}\right\rangle\right]\\ \text{dar }\nabla f(\bm{u})=\left(\frac{\partial}{\partial\bm{u}}\right)^T\Rightarrow&\nabla f(\bm{u})=\left[\frac{\partial}{\partial\bm{u}}\left(\bm{u}^TA\bm{u}-2\bm{u}^T\bm{b}\right)\right]^T\\ &\nabla f(\bm{u})=\left[\frac{\partial\bm{u}^T}{\partial\bm{u}}A\bm{u}+\bm{u}^TA\frac{\partial\bm{u}}{\partial\bm{u}}-2\frac{\partial\bm{u}^T}{\partial\bm{u}}\bm{b}\right]^T\\ \text{dar }\frac{\partial\bm{u}^T}{\partial\bm{u}}\varphi=\varphi^T\Rightarrow&\nabla f(\bm{u})=\left[(A\bm{u})^T+\bm{u}^TA+2\bm{b}^T\right]^T =2\left[(A\bm{u}-\bm{b})^T\right]^T\\&\nabla f(\bm{u})=2(A\bm{u}-\bm{b}) \end{split}\]În cadrul ecuației anterioare, au fost folosite câteva proprietăți matematice pe care nu le vom dezvolta mai mult aici (detalii suplimentare pot fi găsite în subcapitolul dedicat).
Cu toate acestea, deoarece știm că \(A\bm{x}=\bm{b}\), adică \(A\bm{x}-\bm{b}=0\), devine evident că \(\nabla f(\bm{x})=0\), ceea ce ne duce cu gândul (renunțând la rigoare) că acesta va fi un punct de minim în funcția \(f\).
Descoperirea algoritmului#
Algoritmul se bazează pe următoarea proprietate matematică a gradientului: o funcție \(f:\mathbb{R}^n\rightarrow\mathbb{R}\) va scădea cel mai rapid dintr-un punct \(\bm{a}\in\mathbb{R}^n\) dacă se merge în direcția gradientului negativ din \(\bm{a}\), anume \(-\nabla f(\bm{a})\).
Devine deci evident că se poate forma un șir de vectori \((\bm{x_m})_{m\in\mathbb{N}^*}\) folosind formula:
\[ \bm{x_{m+1}}=\bm{x_m}-\gamma\nabla f(\bm{x_m}) \]unde \(\gamma\in\mathbb{R}_+\) este o constantă ce va fi utilizată pentru a face pasul în direcția inversului gradientului. Astfel, dacă \(\gamma\) se alege corespunzător, vom respecta \(f(\bm{x_{m+1}})\leq f(\bm{x_{m}})\). Extrapolând:
\[ f(\bm{x_0})\geq f(\bm{x_{1}})\geq f(\bm{x_{2}})\geq \dots \]Calcularea lui \(\gamma\)#
Cum facem însă să alegem constanta \(\gamma\)? Acest lucru nu este tocmai evident.
Pentru început, putem porni prin a transforma \(\gamma\) astfel încât acesta să fie variabil în funcție de \(m\), adică să se utilizeze șirul \((\gamma_m)_{m\in\mathbb{N}^*}\):
\[ \boxed{\bm{x_{m+1}}=\bm{x_m}-\gamma_m\nabla f(\bm{x_m})} \]Observăm cum acest lucru nu ne încurcă, ci generalizează formula pentru a fi și mai ușor de utilizat.
Dacă valorile \((\gamma_m)_{m\in\mathbb{N}^*}\) sunt prea mici, convergența va fi evident lentă, iar dacă se aleg valori prea mari, metoda diverge. Nu voi intra în prea multe detalii, însă menționez că există o mulțime de metode ce pot fi folosite pentru a calcula aceste valori, precum utilizarea unui algoritm de tip line search, utilizarea matricei hessiane pentru a optimiza o anumită inegalitate etc.
Îmbunătățirea algoritmului#
Acest algoritm este foarte rar utilizat în practică, deoarece există metode mult mai potente. Din nefericire, acestea necesită mai multă matematică decât ne simțim confortabil să împărtășim în cadrul acestei materii. Pentru informații suplimentare, puteți consulta oricând subcapitolul dedicat.
Licență#
The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0 
