Le gradient

Introduction
L'algorithme du gradient, aussi appelé algorithme de descente de gradient, désigne
un algorithme d'optimisation différentiable. Il est par conséquent destiné à minimiser une
fonction réelle différentiable définie sur un espace euclidien (par exemple, Rn, l'espace des n-
uplets de nombres réels, muni d'un produit scalaire) ou, plus généralement, sur un espace
hilbertien. L'algorithme est itératif et procède donc par améliorations successives. Au point
courant, un déplacement est effectué dans la direction opposée au gradient, de manière à faire
décroître la fonction. Le déplacement le long de cette direction est déterminé par la technique
numérique connue sous le nom de recherche linéaire. Cette description montre que
l'algorithme fait partie de la famille des algorithmes à directions de descente.

Les algorithmes d'optimisation sont généralement écrits pour minimiser une fonction. Si l'on
désire maximiser une fonction, il suffira de minimiser son opposée.

Dans sa version la plus simple, l'algorithme ne permet de trouver ou d'approcher qu'un point
stationnaire (i.e., un point en lequel le gradient de la fonction à minimiser est nul) d'un
problème d'optimisation sans contrainte. De tels points sont des minima globaux, si la fonction
est convexe. Des extensions sont connues pour les problèmes avec contraintes simples, par
exemple des contraintes de borne. Malgré des résultats de convergence théoriques
satisfaisants, cet algorithme est généralement lent si le produit scalaire définissant le gradient
ne varie pas avec le point courant de manière convenable, c'est-à-dire si l'espace vectoriel n'est
pas muni d'une structure riemannienne appropriée, d'ailleurs difficilement spécifiable a priori. Il
est donc franchement à déconseiller, même pour minimiser une fonction quadratique
strictement convexe de deux variables. Toutefois, ses qualités théoriques font que l'algorithme
sert de modèle à la famille des algorithmes à directions de descente ou de sauvegarde dans
les algorithmes à régions de confiance.
Le principe de cet algorithme remonte au moins à Cauchy

Méthode du gradient

Dans la méthode du gradient, on choisit

dk = −∇f (xk )

comme direction de descente car

f (xk+1) = f (xk− ρk∇f (xk))

= f (xk)− ρk(∇f (xk), ∇f (xk)) + 1/2ρ2k(H ∇f (xk), ∇f (xk)))

= f (xk)− ρkǁ∇f(xk)ǁ2 ≤ f (xk)

Algorithme du gradient:

 x0∈Rn donné
 xk+1 = xk− ρk∇f (xk)où ρk>0.

Si ρk= ρ, l’algorithme est dit à pas constant.

Critère d’arrêt

On peut utiliser un (ou une combinaison) des critères suivants pour arrêter les itérations d’un
algorithme de descente.

 Etant donné que ∇f (xk)→ ∇f (x¯) = 0, on pose

ǁ∇f(xk)ǁ< ϵ1.

 On a xk→ x¯, on peut aussi prendre

ǁxk+1− xkǁ < ϵ2.

ǁf(xk+1) − f (xk)ǁ< ϵ3.

Etude de la convergence

Voici un résultat de convergence de la méthode du gradient.

Théorème: Soit f : Rn R une fonction convexe et coécrive de classe C 2admettant un seul

(Hf(x )v, v ) ≤ M ǁvǁ2 ∀x, v ∈Rn.

Si on choisit les ρk dans l’intervalle

0 <β1<ρk<β2<2/M,

Alors l’algorithme du gradient converge.

Méthode du gradient à pas optimaux

Dans la pratique, la méthode du gradient à pas constant converge très lentement. Pour
améliorer la convergence il est préférable de choisir les ρkde manière optimale

 x0∈Rn donné
 xk+1 = xk ρk∇ f (xk)

oùρk>0 est choisi de sorte que

min f (xk− ρ∇f (xk))

ρ
Note: la condition d’optimalité de ce problème de minimisation s’écrit

0 =d/dρf (xk— ρ∇f (xk))|ρ=ρk= (∇f (xk+1), ∇f (xk)

C’est-à-dire

∇f (xk+1) ⊥∇f (xk)

Calcul du pas optimal

En général, il n’est pas facile de calculer exactement la valeur ρqui minimise

Min f (xk− ρ∇f (xk)). Par contre, pour la fonction

f (x ) = 1/2(Ax, x ) − (b, x ) + c

avec A >0, la situation est plus facile.

Résidu: il est défini par r = −∇f (x ) = b − A x.

La méthode du gradient s’écrit:

xk+1 = xk− ρk∇f (xk) = xk+ ρkrk

=⇒ Axk+1− b = Axk− b + ρkArk

=⇒ rk+1 = rk− ρkArk

La condition d’optimalité pour ρk est

∇f (xk+1) ⊥∇f (xk)⇐⇒(rk+1, rk) = 0 ⇐⇒(rk− ρkArk , rk) = 0

On prend notre exemple

F(x,y)= x2+y2+2x+4

Point de départ : (x0,y0) = (2,1)

1- Calculer le minimum
𝜕𝑓
= 2𝑥 + 2 = 2(2) + 2 = 6
𝜕𝑥

𝜕𝑓
= 2𝑦 = 2(1) = 2
𝜕𝑦

∇𝑓 = 6𝑖 + 2𝑗

F(x0,y0)= f(2,1) =13

Donc
𝜕𝑓 𝜕𝑓
F(x0+𝜕𝑥 . ℎ + y0+𝜕𝑦 . ℎ)

=f(2+6h, 1+2h)

=(2+6h)2+(1+2h)2+2(2+6h)+4

G(h)= 40h2+40h+13

Après on va calculer la valeur de h:

g’(h) =80h+40=0

h=-0.5

On remplace h dans l’équation

f(2+6.-0.5 , 1+2(-0.5)) = f(-1,0) =3

on remplace f(-1 ,0) dans l’équation

𝜕𝑓
= 2𝑥 + 2 = 2(−1) + 2 = 0
𝜕𝑥
𝜕𝑓
= 2𝑦 = 2(0) = 0
𝜕𝑦
Donc (x,y)=(-1,0) la solution

F(x,y)=x2y2

𝜕2 𝑓 𝜕2 𝑓
𝜕𝑥 2 𝜕𝑥.𝜕𝑦

Hesse =

𝜕2 𝑓 𝜕2 𝑓
𝜕𝑦𝜕𝑥 𝜕𝑦 2

𝜕2 𝑓
Si │h│> 0 ; > 0 (mini)
𝜕𝑥 2

Si │h│< 0 (point de selle)

𝜕2 𝑓
Si │h│> 0 ; < 0 (max)
𝜕𝑥 2

Point de départ (2,1)

𝜕𝑓
= 2𝑥𝑦 2
𝜕𝑥

𝜕 2𝑓
= 2𝑦 2
𝜕𝑥 2
𝜕𝑓
= 2𝑦𝑥 2
𝜕𝑦
𝜕2 𝑓
= 2𝑥 2
𝜕𝑦 2

𝜕 2𝑓
= 4𝑥𝑦
𝜕𝑥. 𝜕𝑦