$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

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