Méthode du gradient à pas optimal
La méthode du gradient à pas optimal est une méthode pour déterminer le minimum de certaines fonctions de plusieurs variables.
Théorème :
Soit $f:\mathbb R^n\to\mathbb R$ une fonction vérifiant la propriété suivante : $\exists \alpha>0,\ \forall (x,y)\in(\mathbb R^n)^2,\ \forall t\in[0,1],$
$$f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)-\alpha t(1-t)\|x-y\|^2.$$
Alors $f$ admet un unique minimum local $x^*$ sur $\mathbb R^n$ qui est aussi son minimum global. De plus, si $f$ est $\mathcal C^1$, la suite $(x_n)$
définie par $x_0\in\mathbb R^n$ et
$$x_{n+1}=
\left\{
\begin{array}{ll}
x^*&\textrm{ si }x_n=x^*\\
x_n-\rho_n \nabla f(x_n)&\textrm{ sinon}
\end{array}\right.$$
où $\rho_n$ vérifie
$$\rho_n=\inf_{\rho\geq 0} f(x_n-\rho\nabla f(x_n))$$
converge vers cet unique minimum.
Voici l'interprétation géométrique de cette méthode : on part d'un point quelconque, et on commence par se diriger dans la direction où $f$ varie le plus vite (cette direction est donnée par le gradient). On s'arrête jusqu'à atteindre le minimum de $f$ dans cette direction. Puis on recommence à partir de ce point.
Consulter aussi
Recherche alphabétique
Recherche thématique