5mm71 : Méthodes du premier ordre pour l’optimisation...

Sorbonne Université

Module B2
Méthodes de gradient explicite

Sauf mention contraire, X (resp. Y) est un espace de Hilbert, muni du produit

scalaire noté ⟨·, ·⟩ et on note ∥ · ∥ la norme qui découle du produit scalaire.
Dans ce module, on s’intéresse au problème de minimisation suivant
min J(x) (P)
x∈X

où J : X → R est une fonction différentiable (sur tout X ). On va introduire un algorithme

d’optimisation pour résoudre ce problème et étudier le comportement (et en particulier
la convergence) des suites générées par cet algorithme.

1 Direction de descente
1.1 Définition et exemple
Définition 1 (Direction de descente)

Soit J : X → R ∪ {+∞} une fonction. Soit x0 ∈ dom J et d ∈ X . On dit que d

est une direction de descente pour J au point x0 si J ′ (x0 ; d) existe et que
J ′ (x0 ; d) < 0
où J ′ (x0 ; d) désigne la dérivée directionnelle de J en x0 dans la direction d.

Autrement dit, si d est une direction de descente pour J en x0 , alors il existe α > 0 tel
que
∀t ∈ ]0;α], J(x0 + t d) < J(x0 )
(on notera que la réciproque est fausse). On peut alors énoncer le résultat suivant :

Proposition 1

Soit J : X → R ∪ {+∞} une fonction. Soit x0 ∈ dom J. Si x0 est un mini-

miseur de J, alors J n’admet aucune direction de descente en x0 . De manière
équivalente, si J admet une direction de descente en x0 , alors x0 n’est pas un
minimiseur de J.

Démonstration : Démontrons cette affirmation par l’absurde. On suppose donc

que x0 est un minimiseur de J et que J admet d comme direction de descente en x0 .
Par définition de d, il existe α > 0 tel que
∀t ∈ ]0;α], J(x0 + t d) < J(x0 )
Cela implique notamment que le point x = x0 + α d/2 vérifie J(x) < J(x0 ), ce qui
contredit le fait que x0 soit un minimiseur de J. ■

Pauline Tan 1 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Lorsque J est différentiable en x0 , la proposition suivante permet de caractériser de

manière plus pratique les directions de descente :

Proposition 2

Soit J : X → R ∪ {+∞} une fonction. Soit x0 ∈ dom J. On suppose que J est

différentiable au voisinage de x0 . Alors d est une direction de descente pour J
en x0 si et seulement si
⟨∇J(x0 ), d⟩ < 0

Démonstration : Ce résultat découle de l’identité J ′ (x0 ; d) = ⟨∇J(x0 ), d⟩ valable

lorsque J est différentiable. ■

Il est à noter que les directions de descente, lorsqu’elles existent, ne sont pas uniques
en un même point. L’exemple suivant est à la base de la méthode de Newton.

Exemple
Méthode de Newton. On suppose que J est deux fois différentiable et que
la matrice hessienne HessJ(x0 ) de J en x0 ∈ X est définie positive. Posons
d = −(HessJ(x0 ))−1 (∇J(x0 ))
Alors d est une direction de descente pour J en x0 . En effet, HessJ(x) est
diagonalisable et définie positive pour tout x ∈ X . Notons λmax la plus grande
valeur propre (positive) de HessJ(x0 ). On a alors
∥∇J(x0 )∥2
⟨∇J(x0 ), −(HessJ(x0 ))−1 ∇J(x)⟩ ≤ − <0
λmax
ce qui assure que d est bien une direction de descente pour J d’après la pro-
position 2. Ce vecteur apparaît lorsque l’on applique la méthode de Newton
pour trouver les zéros du gradient ∇J. Les itérations de cette méthode pour
rechercher les zéros d’une fonction G : X → Y s’écrivent
∀ n ∈ N, xk+1 = xk − (∇G(xk ))−1 (G(xk ))
ce qui donne, lorsque G = ∇J,
xk+1 = xk − (HessJ(xk ))−1 (∇J(xk ))
Pour plus de détails sur la méthode de Newton, le lecteur est invité à consulter
le module b3 : Méthode de Newton. Méthode du gradient (3ma261).

1.2 Méthodes de descente

Les méthodes dites de descente génèrent une suite d’itérées (xk )k∈N satisfaisant la
propriété de descente suivante :
∀ k ∈ N, J(xk+1 ) ≤ J(xk )
le point xk+1 pouvant toujours s’exprimer de manière arbitraire à l’aide du point précé-
dent xk en posant
xk+1 = xk + τk dk avec τk > 0 et dk ∈ X

Pauline Tan 2 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

(pour tout couple de points successifs (xk , xk+1 ), cette décomposition n’est pas unique).
Ainsi, d’après ce qui précède, le vecteur dk peut être choisi parmi les direction de descente
de J en xk , auquel cas l’existence d’un pas de temps τk assurant la décroissance de J est
assurée tant que xk n’est pas un minimiseur. Il est à noter que dk n’est pas nécessairement
une direction de descente au sens de la définition 1. La question réside donc dans le choix
de ce vecteur et des valeurs admissibles pour les pas de temps τk .

2 Méthode du gradient explicite

Il s’agit d’une classe de méthodes très étudiée et bien connue, généralement l’une des
premières qui sont abordées en optimisation numérique car elle est facile à mettre en
œuvre dès lors que le problème d’optimisation étudié possède les bonnes propriétés.

2.1 Description de l’algorithme

Les méthodes du gradient explicite sont des méthodes de descentes (on parle par-
fois de méthode de descente du gradient, l’adjectif explicite étant souvent omis), dans
lesquelles le vecteur dk introduit à la fin de la section précédente est une direction de
descente, définie à l’aide du gradient de la fonction J au point courant.
Plus précisément, ce vecteur est l’opposé du gradient de J au point courant xk , car
selon la proposition suivante, ce vecteur constitue une direction de descente pour la
fonction J au point xk :

Proposition 3

Soit J : X → R ∪ {+∞} une fonction. Soit x ∈ dom J. On suppose que J est

différentiable au voisinage de x. On suppose par ailleurs que x n’est pas un
point critique de J. Alors d = −∇J(x) est une direction de descente pour J
en x.

Démonstration : Il s’agit d’une conséquence directe de la proposition 2, puisque

⟨∇J(x), d⟩ = −⟨∇J(x), ∇J(x)⟩ = −∥∇J(x)∥2 ■

Les itérations de la méthode du gradient explicite sont alors données par

x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τk ∇J(xk ) avec τk > 0.
L’hypothèse de différentiabilité sur J assure que, quelle que soit l’initialisation x0 et le
choix des pas de temps τk , la suite des itérées est bien définie.
Ce qui distingue les différentes versions de la méthode du gradient explicite entre
elles, c’est le choix du pas de temps τk , qui est détaillé dans les paragraphes suivants,
de même que le choix du critère d’arrêt.

2.2 Choix du pas de temps

Une fois le choix de la direction de descente arrêté, celui du pas de temps est crucial.
Il doit répondre à plusieurs exigences :
• descente : pour rester dans le cadre des méthodes de descente, le pas de temps
doit être choisi de sorte que l’algorithme génère une suite d’itérées dont la valeur
par J décroît (cette contrainte pourra être levée dans le cas général) ;

Pauline Tan 3 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

• convergence : le choix du pas de temps doit permettre d’assurer la convergence

du schéma itératif, autrement dit qu’en un nombre fini d’itérations, la suite générée
approche raisonnablement bien une solution du problème (P) ;
• vitesse de convergence : comme on le verra par la suite, le choix du pas de
temps peut grandement influencer la vitesse de convergence de l’algorithme, c’est-
à-dire le nombre d’itérations nécessaire avant d’activer le critère d’arrêt ; il faut
donc veiller à en sélectionner un qui permet de converger en un nombre raisonnable
d’itérations ;
• complexité : outre le nombre d’itérations, c’est le temps de calcul pour atteindre la
solution (à une précision souhaitée) qui importe ; or, celui-ci est fonction du nombre
d’itérations que l’algorithme doit calculer avant d’activer le critère d’arrêt, mais
également du temps de calcul d’une itération isolée. Pour la méthode du gradient
explicite, celui-ci repose essentiellement sur deux calculs : l’évaluation du gradient
au point courant, et le choix du pas de temps. Il apparaît donc essentiellement que
le choix de ce dernier ne mène pas à des calculs trop complexes qui serait trop
gourmands en temps (ou en mémoire).
De manière générale (mais il existe de nombreuses exceptions), on peut dire que la
convergence du schéma nécessite des pas de temps relativement faibles, mais qu’obtenir
une convergence en un nombre d’itérations petit demande de choisir des pas de temps
relativement grands. La première difficulté réside dans la conciliation de ces deux exi-
gences contradictoires. Il existe alors deux possibilités : soit on choisit un pas de temps
fixe, qui a le mérite de satisfaire le critère sur la complexité (puisqu’il n’est au plus cal-
culé qu’une seule fois), mais avec l’inconvénient d’être très rigide, soit on choisit un pas
de temps qui s’adapte localement au point courant (permettant parfois d’économiser un
nombre intéressant d’itérations), mais qui peut demander un grand nombre de calculs.
Voici quelques exemples de règles de choix de pas de temps classiques.
• Pas optimal. Cette règle est la plus naturelle : à chaque itération, on cherche le
point suivant en sélectionnant celui qui, dans la direction de descente, minimise la
fonction objectif :
xk+1 = argmin J(x)
x=xk −τ ∇J(xk )
τ >0

Le pas de temps associé est alors défini de la manière suivante :

τk = argmin J xk − τ ∇J(xk )
τ >0

La recherche de ce pas optimal est appelée recherche linéaire (line search en an-
glais). Il existe des contre-exemples connus démontrant que cette stratégie n’est pas
toujours optimale, ou ne permet pas de faire converger l’algorithme ; par ailleurs,
elle est en général coûteuse en calcul, puisqu’il s’agit de résoudre un problème
d’optimisation. Supposons que xk n’est pas un point critique. Puisque la fonction


τ 7→ J xk − τ ∇J(xk )
est différentiable et que −∇J(xk ) est une direction de descente, alors (on suppose
que la fonction J admet un minimiseur), la fonction précédente admet au moins
un minimiseur local sur ] 0 ; +∞ [, parmi les points τ ∗ vérifiant
∇J(xk ), ∇J xk − τ ∗ ∇J(xk ) = 0

de sorte que le nouveau point xk+1 vérifie ⟨∇J(xk ), ∇J(xk+1 )⟩ = 0. On peut

interpréter cette dernière égalité de manière géométrique : les gradients en deux
points consécutifs sont orthogonaux (cf. figure 1).

Pauline Tan 4 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

• Pas constant. Enfin, le cas des pas de temps fixes

∀ k ∈ N, τk = τ
où τ > 0, est le plus simple, puisqu’il suffit de choisir une seule fois la valeur du pas.
L’inconvénient le plus visible de cette stratégie est le fait qu’un pas fixe ne tenant
a priori pas compte de l’information locale (c’est-à-dire au point courant xk ), il
peut être trop restrictif et conduire à des convergences plus lentes. Cependant, on
verra dans la section suivante que, sous certaines hypothèses sur le problème, il
est possible d’ajuster correctement la valeur τ pour aboutir à une convergence de
l’algorithme.

◦ ◦

1 •
•
•
• • • ••• •••• • •
x
0 1

Figure 1 – Illustration de la méthode du gradient à pas optimal dans le cas d’une fonc-
tion convexe quadratique pour deux choix de pas de temps et d’initialisation différents.
Les ellipses correspondent à des lignes de niveau de la fonction objectif.

On pourra noter que toutes ces considérations sur le choix des pas de temps,
ainsi que les différentes stratégies proposées pour résoudre un tel problème,
ne sont pas spécifiques aux méthodes du gradient explicite, et doivent être
soulevées pour d’autres méthodes d’optimisation.

Contre-exemple
Oscillations dans le cas des pas constants. Considérons le problème de
minimisation convexe suivant :
1
min x2
x∈R 2

Pauline Tan 5 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Les itérations de la méthode du gradient à pas constant s’écrivent

∀ k ∈ N, xk+1 = xk − τ xk = (1 − τ ) xk
Si τ = 2, alors on constate que xk+1 = −xk , de sorte que la suite des itérées
oscille entre deux points x0 et −x0 , qui sont différents si x0 ̸= 0. Notons que,
dans cet exemple, la suite des valeurs J(xk ) reste constante. Il n’y a donc pas
de décroissance stricte. Le prochain exemple montre que rajouter cette seconde
condition n’est pas non plus suffisant pour assurer la convergence vers un point
critique de la fonction objectif.

• •

x2k x2k+1 x
0 1

Figure 2 – Oscillations dans le cas des pas constants.

Contre-exemple
Oscillations dans le cas des pas optimaux. Considérons le problème de
minimisation convexe quadratique suivant :
1 2
min (x + λ y 2 )
(x,y)∈R2 2
avec λ > 0. Les itérations de la méthode du gradient à pas optimal s’écrivent
       
xk+1 xk xk (1 − τk ) xk
∀ k ∈ N, = − τk =
yk+1 yk λ yk (1 − λ τk ) yk
où τk > 0 est choisi de sorte de minimiser la quantité
1
1 2
(1−τk )2 x2k +λ (1−λ τk )2 yk2 = xk +λ yk2 −2 (x2k +λ2 yk2 ) τk +(x2k +λ3 yk2 ) τk2


2 2
Il s’agit d’un polynôme du second degré en τk ; on vérifie donc aisément que
x2k + λ2 yk2 1 2 2 1 (λ − 1)2 λ x2k yk2
τk = donc (xk+1 + λ yk+1 )=
x2k + λ3 yk2 2 2 (x2k + λ3 yk2 )
Notons que, lorsque λ est grand, les croissances comparées assurent que τk est
proche de zéro. Dans la figure 3, on montre deux exemples de suites d’itérées
dans le cas λ = 100, générées à partir de deux points initiaux différents. On voit
que, dans l’un de deux cas, il faut un grand nombre d’itérations pour approcher

Pauline Tan 6 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

raisonnablement le minimiseur (0, 0). Cela est dû au fait que les lignes de ni-
veau de la fonction objectif (ici, des ellipses) sont très allongées. Formellement,
cette propriété
√ se traduit par un grand (donc mauvais) conditionnement (il vaut
ici κ = λ).

• •• • •• ••• • • •
• • x
0 1 ◦

Figure 3 – Oscillations dans le cas des pas optimaux. Les ellipses sont des lignes de
niveaux de la fonction objectif. En bleu et en rouge, deux trajectoires correspondant à
deux initialisations différentes.

3 Convergence de l’algorithme dans le cas régulier

On considère dans cette section l’algorithme du gradient explicite à pas constant
pour la minimisation d’une fonction régulière.

3.1 Convergence du critère et des gradients

Dans ce paragraphe, on commence par établir quelques résultats valables lorsque le
problème est régulier et que le pas de temps τ est correctement choisi en fonction de la
constante de Lipschitz du gradient de la fonction objectif.
Proposition 4 (Convergence du critère)

Soit J : X → R une fonction L-régulière. On suppose que J est minorée.

Soit (xk )k∈N une suite générée par l’algorithme suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )
Si τ ∈ ] 0 ; 2/L [, alors la suite (J(xk ))k∈N est décroissante et converge vers une
valeur J ∗ . De plus, on a
τ2
 
J(xk+1 ) ≤ J(xk ) − τ − L ∥∇J(xk )∥2
2

Pauline Tan 7 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Démonstration : Soit k ∈ N. Commençons par écrire que

h iτ
J(xk+1 ) − J(xk ) = J(xk − τ ∇J(xk )) − J(xk ) = J(xk − t ∇J(xk ))
0

En intégrant, on obtient donc que

h it Z τ
J(xk − t ∇J(xk )) = − ⟨∇J(xk ), ∇J(xk − t ∇J(xk ))⟩ dt
0 0

En ajoutant le vecteur nul ∇J(xk ) − ∇J(xk ) dans le second membre du produit

scalaire, on obtient que (attention au signe du terme intégral)
Z τ
J(xk+1 ) − J(xk ) = −τ ∥∇J(xk )∥2 + ⟨∇J(xk ), ∇J(xk ) − ∇J(xk − t ∇J(xk ))⟩ dt
0

Majorons le produit scalaire à l’aide de l’inégalité de Cauchy–Schwarz, puis de

l’hypothèse de régularité sur J ; il s’ensuit que
Z τ
τ2
 
J(xk+1 ) − J(xk ) ≤ −τ ∥∇J(xk )∥2 + t L ∥∇J(xk )∥2 dt = − τ − L ∥∇J(xk )∥2
0 2
Par hypothèse sur le pas de temps τ , on a τ −τ 2 L/2 > 0. On prouve ainsi que la suite
des J(xk ) est décroissante. La convergence suit car cette suite est minorée par inf J
par hypothèse. ■

Proposition 5 (Convergence du critère d’optimalité)

Soit J : X → R une fonction L-régulière. On suppose que J est minorée.

Soit (xk )k∈N une suite générée par l’algorithme suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )

Si τ ∈ ] 0 ; 2/L [, alors lim ∥∇J(xk )∥ = 0

k→+∞

Démonstration : Dans la proposition 4, on a établi que

τ2
 
J(xk+1 ) ≤ J(xk ) − τ − L ∥∇J(xk )∥2 ≤ J(xk )
2
Par encadrement, la suite des
τ2
 
J(xk ) − τ − L ∥∇J(xk )∥2
2
converge vers J ∗ . Il s’ensuit que la suite (∥∇J(xk )∥)k∈N converge vers 0. ■

3.2 Convergence vers un minimum dans le cas convexe

Pour obtenir des résultats plus intéressants, il faut ajouter des hypothèses supplé-
mentaires. Parmi les options possibles, on peut supposer la convexité du problème.
Lemme 1

Soit J : X → R une fonction convexe L-régulière. On suppose que J admet

un minimiseur x∗ . Soit (xk )k∈N une suite générée par l’algorithme suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )
∗
Si τ ∈ ] 0 ; 2/L [, alors la suite (∥xk − x ∥)k∈N est décroissante.

Pauline Tan 8 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Remarque : Il s’ensuit immédiatement que cette suite converge, puisqu’elle est réelle
minorée par 0. Cependant, tant que l’on n’a pas établi que la limite de cette suite est
nulle, on ne peut pas conclure à la convergence des itérées.

Démonstration : La règle de Fermat (∇J(x∗ ) = 0) entraîne que

x∗ = x∗ − τ ∇J(x∗ )
(Autrement dit, x∗ est un point fixe de la méthode du gradient explicite). Aussi, pour
tout k ∈ N, on a

∥xk+1 − x∗ ∥2 = ∥xk − τ ∇J(xk ) − x∗ + τ ∇J(x∗ )∥2

= ∥xk − x∗ ∥2 − 2 τ ⟨∇J(xk ) − ∇J(x∗ ), xk − x∗ ⟩
+ τ 2 ∥∇J(xk ) − ∇J(x∗ )∥2

Il suffit alors d’utiliser le lemme de Baillon–Haddad (module a4 : Fonctions

régulières) et la régularité de J pour obtenir la majoration
τ
∥xk+1 − x∗ ∥2 ≤ ∥xk − x∗ ∥2 − 2 ∥∇J(xk ) − ∇J(x∗ )∥2 + τ 2 ∥∇J(xk ) − ∇J(x∗ )∥2
L
τ2
 
∗ 2 2
≤ ∥xk − x ∥ − τ− L ∥∇J(xk ) − ∇J(x∗ )∥2
L 2

Puisque τ − τ 2 L/2 > 0, on en déduit que ∥xk+1 − x∗ ∥2 ≤ ∥xk − x∗ ∥2 . ■

Une conséquence importante de ce lemme est le fait que, si le problème est convexe
et régulier, qu’il admet une solution, et que le pas de temps est correctement choisi,
alors la suite générée par la méthode du gradient explicite est bornée. On verra dans le
paragraphe suivant que cette propriété est déterminante pour démontrer la convergence
de cet algorithme.
Démontrons en effet que, dans le cas convexe, la suite des J(xk ) converge vers le
minimum de J lorsque le pas de temps τ est correctement choisi.

Proposition 6 (Convergence du critère vers le minimum)

Soit J : X → R une fonction convexe L-régulière. On suppose que J admet

un minimiseur x∗ . Soit (xk )k∈N une suite générée par l’algorithme suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )
Si τ ∈ ] 0 ; 2/L [, alors la suite (J(xk ))k∈N converge vers J(x∗ ) et
∥x0 − x∗ ∥2 1
∀ k ∈ N, 0 ≤ J(xk ) − J(x∗ ) ≤
τ − τ 2 L/2 k + 1

Remarque : Par définition de x∗ , on a toujours la positivité de la quantité J(xk )−J(x∗ ).

Démonstration : Soit k ∈ N. La convexité de J assure que

J(x∗ ) ≥ J(xk ) + ⟨∇J(xk ), x∗ − xk ⟩
L’inégalité de Cauchy–Schwarz permet d’obtenir la majoration suivante :
J(xk ) − J(x∗ ) ≤ ∥∇J(xk )∥ ∥xk − x∗ ∥ ≤ ∥∇J(xk )∥ ∥x0 − x∗ ∥
où la deuxième inégalité est obtenue grâce au lemme 2. En utilisant la proposition 4,
on peut alors écrire que

Pauline Tan 9 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

2
τ2 J(xk ) − J(x∗ )
 
J(xk+1 ) − J(x∗ ) ≤ J(xk ) − J(x∗ ) − τ − L
2 ∥x0 − x∗ ∥2
On conclut la preuve par un raisonnement par récurrence. Commençons par l’initia-
lisation (k = 0). Pour cela, il suffit de remarquer que l’inégalité précédente s’écrit
J(xk+1 ) − J(x∗ ) J(xk ) − J(x∗ ) J(xk ) − J(x∗ )
 
2
≤ 1 − (τ − τ L/2)
∥x0 − x∗ ∥2 ∥x0 − x∗ ∥2 ∥x0 − x∗ ∥2
Le membre de droite étant positif, on en déduit que, pour tout k ∈ N,
∥x0 − x∗ ∥2
0 ≤ J(xk ) − J(x∗ ) ≤
τ − τ 2 L/2
Supposons la majoration de la proposition 6 vraie au rang k. En multipliant la troi-
sième inégalité de cette preuve par la quantité adéquate, on obtient alors

τ − τ 2 L/2 τ − τ 2 L/2
J(xk+1 ) − J(x∗ ) ≤ 1 + J(xk ) − J(x∗ )



(k + 2) ∗
∥x0 − x ∥ 2 ∥x0 − x∗ ∥2
∗

2
(τ − τ 2 L/2)2 J(xk ) − J(x )
− (k + 2) ∗ ∗
∥x0 − x ∥ 2 ∥x0 − x ∥ 2

où le premier terme du membre de droite est obtenu à l’aide de l’hypothèse de récur-

rence. Intéressons-nous aux deux termes restants. En utilisant la décroissance de la
suite (J(xk ) − J(x∗ ))k∈N , on peut majorer leur somme par
τ − τ 2 L/2 J(xk+1 ) − J(x∗ )
 
∗
2
J(x k ) − J(x ) 1 − (k + 2) (τ − τ L/2)
∥x0 − x∗ ∥2 ∥x0 − x∗ ∥2
On en déduit que l’hypothèse de récurrence est vérifiée au rang k + 1, c’est-à-dire que
la quantité ci-dessus est positive. Sinon, elle serait négative et l’inégalité précédente
serait majorée par 1, ce qui serait l’hypothèse de récurrence au rang k + 1. On en
déduit que par récurrence le résultat souhaité. ■

La proposition 6 donne, dans le cas convexe, une vitesse de convergence / décroissance

pour le critère, qui est en O(1/k), avec k le nombre d’itérations. Ce taux de convergence
dépend de l’initialisation (en particulier, de la distance du premier point à l’ensemble
des minimiseurs de J), mais également du choix du pas de temps. Il apparaît que le taux
de convergence est d’autant plus intéressant que la quantité
∥x0 − x∗ ∥2
τ − τ 2 L/2
est faible, donc que la quantité τ − τ 2 L/2 est grande. Si τ ∈ ] 0 ; 2/L [, alors la valeur
optimale τ ∗ du pas de temps selon ce critère est
1
τ∗ =
L
2 L ∥x0 − x∗ ∥2
auquel cas ∀ k ∈ N, 0 ≤ J(xk ) − J(x∗ ) ≤
k+1
Par ailleurs, il est facile de voir que le taux établi dans la proposition 6 est croissant
en fonction de la constante de Lipschitz L. Ainsi, plus L est petit, meilleure est la
convergence de la méthode du gradient explicite à pas constant.
Une manière de traduire la proposition 6 est la suivante : la suite des itérées (xk )k∈N
est une suite minimisante de J. Ainsi, si J est fortement convexe et qu’on est en di-
mension finie, alors on en déduit immédiatement que cette suite converge vers l’unique
minimiseur de J (d’après la proposition 15 du module b1 : Méthodes d’optimisation
du premier ordre), avec (si τ = τ ∗ = 1/L)

Pauline Tan 10 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

8 L ∥x0 − x∗ ∥2 8 κ ∥x0 − x∗ ∥2
∀ k ∈ N, 0 ≤ ∥xk − x∗ ∥2 ≤ =
α (k + 1) k+1
où κ est le conditionnement de la fonction J. On peut donc déjà observer que ce taux
est d’autant plus intéressant que le conditionnement est bon (κ proche de 0). On verra
plus loin qu’il est en réalité possible d’obtenir un taux de convergence beaucoup plus
intéressant.
On termine ce paragraphe avec le résultat central sur la convergence de la méthode
du gradient explicite dans le cas convexe.

Proposition 7 (Convergence des itérés dans le cas convexe)

Soit J : X → R une fonction convexe L-régulière. On suppose que J admet

un minimiseur. Soit (xk )k∈N une suite générée par l’algorithme suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )
Si τ ∈ ] 0 ; 2/L [, alors la suite (xk )k∈N converge vers un minimiseur de J.

Démonstration : Décomposons cette preuve en deux étapes.

• La suite des itérées est bornée. Il s’agit d’une conséquence du lemme 2.
• La suite des itérées converge. La proposition 8 (qui se démontre de manière
indépendante) assure l’existence d’une sous-suite (xkj )j∈N qui converge vers un
point critique (donc un minimiseur) x∗ de J. D’après le lemme 2, il s’ensuit
que, par unicité de la limite,

lim ∥xk − x∗ ∥ = lim ∥xkj − x∗ ∥ = 0

k→+∞ j→+∞

Autrement dit, la suite (xk )k∈N converge vers x∗ . ■

3.3 Convergence vers un point critique dans le cas coercif et KŁ

Lorsque la fonction objectif n’est pas convexe, on peut obtenir des résultats inté-
ressants en ajoutant deux autres hypothèses, qui sont la coercivité et la propriété KŁ
(voir module a3 : Propriété de Kurdyka–Łojasiewicz). La première hypothèse
assure que la suite des itérées est bornée :

Lemme 2

On suppose que X est de dimension finie. Soit J : X → R une fonction coercive

et L-régulière. Soit (xk )k∈N une suite générée par l’algorithme suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )
Si τ ∈ ] 0 ; 2/L [, alors la suite (xk )k∈N est bornée.

Démonstration : La propriété de décroissance du critère assure que

∀ k ∈ N, xk ∈ niv≤J(x0 ) J
Or, on a démontré dans la preuve de la proposition 5 du module b1 : Méthodes
d’optimisation du premier ordre que cet ensemble est borné, ce qui conclut la
preuve. ■

Pauline Tan 11 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Cette hypothèse n’est pas nécessaire s’il existe un autre moyen pour assurer que la
suite générée par la méthode du gradient explicite est bornée.

Proposition 8

Soit J : X → R une fonction L-régulière. On suppose que J est minorée.

Soit (xk )k∈N une suite générée par l’algorithme suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )
Si la suite (xk )k∈N est bornée et que τ ∈ ] 0 ; 2/L [, alors il existe une sous-
suite (xkj )j∈N qui converge vers un point critique de J.

Démonstration : Puisque la suite des xk est supposée bornée, elle admet une sous-
suite (xkj )j∈N convergente. Notons x̄ sa limite. D’après la proposition 5, la sous-suite
des gradients ∇J(xkj ) converge vers 0. Or, par continuité, on a
 
0 = lim ∇J(xkj ) = ∇J lim xkj = ∇J(x̄)
j→+∞ j→+∞

D’où le résultat annoncé. ■

Une conséquence immédiate de ce résultat est le suivant :

Corollaire 1 (Convergence des itérés dans le cas borné)

Soit J : X → R une fonction L-régulière. On suppose que J admet un unique

minimiseur x∗ . Soit (xk )k∈N une suite générée par l’algorithme suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )
Si la suite (xk )k∈N est bornée et que τ ∈ ] 0 ; 2/L [, alors la suite (xk )k∈N
converge vers x∗ .

Démonstration : En effet, la proposition précédente assure que tout point d’adhé-

rence de la suite des itérées est un point critique de J. Si J admet un unique mini-
miseur, alors l’adhérence de cette suite est réduite à ce point. Il s’ensuit qu’elle est
nécessairement convergente. ■

En combinant le lemme 2 et la proposition 8, on prouve le corollaire suivant :

Corollaire 2

On suppose que X est de dimension finie. Soit J : X → R une fonction coercive

et L-régulière. Soit (xk )k∈N une suite générée par l’algorithme suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )
Si τ ∈ ] 0 ; 2/L [, alors il existe une sous-suite (xkj )j∈N qui converge vers un
point critique de J.

Pour obtenir la convergence forte des itérées, il faut généralement, dans le cas non-
convexe, utiliser la propriété KŁ.

Pauline Tan 12 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Proposition 9 (Convergence des itérés dans le cas KŁ et coercif)

Soit J : X → R une fonction KŁ, coercive et L-régulière. Soit (xk )k∈N une suite
générée par l’algorithme suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )
Si τ ∈ ] 0 ; 2/L [, alors la suite (xk )k∈N converge vers un minimiseur de J.

Démonstration : Il s’agit d’appliquer le théorème d’Attouch, Bolte & Svaiter

(module a3 : Propriété de Kurdyka–Łojasiewicz). La condition (C1) de
décroissance est une conséquence directe de la régularité de J et du choix associé
de τ (proposition 4). La condition (C2) d’erreur relative découle directement de la
définition des itérées, puisque
1
xk+1 = xk − τ ∇J(xk ) =⇒ ∥∇J(xk )∥ = ∥xk − xk+1 ∥
τ
Enfin, la condition (C3) de continuité est une conséquence de la coercivité qui, couplée
avec le caractère décroissant du critère, assure l’existence d’un point d’adhérence pour
la suite des itérées, tandis que la limite du critère est due à la continuité de J. ■

3.4 Convergence linéaire dans le cas fortement convexe

Dans le cas convexe, on ne peut a priori pas établir de taux de convergence pour la
suite des itérées. Dans le cas fortement convexe en revanche, il est possible d’établir un
taux de convergence linéaire :

Théorème 1 (Convergence linéaire dans le cas fortement convexe)

Soit J : X → R une fonction convexe L-régulière. On suppose que J est forte-

ment convexe de module α. Soit (xk )k∈N une suite générée par l’algorithme
suivant
x0 ∈ X et ∀ k ∈ N, xk+1 = xk − τ ∇J(xk )
Si τ ∈ ] 0 ; 1/L ], alors la suite (xk )k∈N converge vers le minimiseur x∗ de J et
∀ k ∈ N, 0 ≤ ∥xk − x∗ ∥2 ≤ (1 − τ α)k ∥x0 − x∗ ∥2

Remarque : Attention aux valeurs possibles pour le pas de temps τ , qui diffèrent des
propositions précédentes !

Démonstration : Dans la preuve du lemme 2, on a démontré que

∥xk+1 − x∗ ∥2 = ∥xk − x∗ ∥2 + 2 τ ⟨∇J(xk ), x∗ − xk ⟩ + τ 2 ∥∇J(xk )∥2
(en utilisant le fait que ∇J(x∗ ) = 0). D’après la caractérisation de la forte convexité
par les (sous-)gradients (corollaire 1 du module a2 : Sous-différentiabilité), on a
 α 
∥xk+1 − x∗ ∥2 ≤ ∥xk − x∗ ∥2 − 2 τ J(xk ) − J(x∗ ) + ∥xk − x∗ ∥2 + τ 2 ∥∇J(xk )∥2
2
Dans la proposition 4, on a par ailleurs démontré que
τ2
 
J(xk+1 ) − J(x) ≤ − τ − L ∥∇J(xk )∥2
2

Pauline Tan 13 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

de sorte que, puisque J(x∗ ) ≤ J(xk+1 ) par optimalité, on a (après simplification)

τ − τ2 L
∥xk+1 − x∗ ∥2 ≤ (1 − τ α) ∥xk − x∗ ∥2 − τ J(xk ) − J(x∗ )


τ − τ 2 L/2
Dans le quotient qui apparaît dans l’inégalité ci-dessus, le dénominateur est stricte-
ment positif car 0 < τ < 2/L, tandis que le numérateur est positif car 0 < τ ≤ 1/L.
On peut donc ignorer ce terme et terminer la preuve par une récurrence. ■

Le taux de convergence établi dans cette dernière proposition est donc un taux de
convergence linéaire, avec
0<1−τα<1
car L ≥ α d’après une remarque du module a4 : Fonctions régulières. Celui-ci est
d’autant plus intéressant que la quantité ci-dessus est proche de zéro. On voit donc qu’il
s’agit de choisir τ aussi grand que possible dans l’intervalle autorisé, c’est-à-dire
1
τ∗ =
L
Le pas de temps optimal sous ces contraintes est donc le même que celui déterminé dans
le cas convexe. Dans ce cas, on a
 k
 α k 1
∀ k ∈ N, 0 ≤ ∥xk − x∗ ∥2 ≤ 1 − ∥x0 − x∗ ∥2 = 1 − ∥x0 − x∗ ∥2
L κ
et on voit que la convergence de la méthode du gradient explicite à pas constant optimal
est d’autant plus bonne que le conditionnement de la fonction objectif est bon.
Il est important de noter qu’en pratique, seul le résultat de convergence dans le
cas fortement convexe est réellement exploitable. En effet, sans taux de convergence,
il n’existe aucun indice sur le temps nécessaire (c’est-à-dire, le nombre d’itérations né-
cessaire) pour obtenir une estimation suffisamment bonne d’une solution du problème.
Par ailleurs, on notera que, pour l’erreur sur le critère dans le cas convexe, par exemple
(proposition 6), dépend de la distance entre le point initial x0 et un minimiseur. Il est
évident que cette distance est généralement inconnue et difficile à estimer. Or, si l’initia-
lisation est faite arbitrairement, cette distance peut être importante. Dans le cas d’une
convergence linéaire, la distance au minimiseur décroît de manière exponentielle vers 0,
de sorte que l’initialisation a un poids moins important.

4 Application : débruitage de signal

4.1 Régularisation de Tikhonov
Une application possible pour la méthode du gradient explicite est le problème
de débruitage d’un signal bruité. Plus précisément, on a un signal (son, image par
exemple) g ∈ X (où X = Rn dans le cas d’un son, X = Rmn ou R3mn dans le cas
d’une image en niveaux de gris ou en couleur RGB), résultant d’une mesure (enregistre-
ment, prise de vue). Cette mesure a introduit du bruit additif, c’est-à-dire que g est une
version dégradée d’un signal idéal u, et que la relation entre la mesure et le signal idéal
est modélisée par
g =u+n
avec n le bruit additif. Sans entrer dans les détails, si n est un bruit blanc gaussien, et
que le signal est supposé relativement régulier 1 , alors on peut essayer de trouver une
1. En réalité, ce n’est pas le cas pour une image, qui comporte des discontinuités. On le voit d’ailleurs
dans les tests expérimentaux, où la solution trouvée est certes débruitée, mais floue, ce qui correspond
à une image régulière.

Pauline Tan 14 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

estimation de u en résolvant le problème d’optimisation suivant

 
1 2 λ h 2
min ∥u − g∥2 + ∥∇ u∥2
u∈X 2 2
Le premier terme est appelé terme d’attache aux données ou terme de fidélité ; il sert à
imposer à la solution u∗ à rester proche des données bruitées g. Le second terme est le
terme de régularisation : il permet d’injecter une forme d’informations supplémentaires
sur la solution, ici de la régularité grâce à la régularisation dite de Tikhonov. Elle
est définie à l’aide d’une discrétisation du gradient spatial. Enfin, le réel positif λ est
un paramètre qui permet de moduler l’importance relative des deux termes ; plus λ est
grand, plus le terme de régularisation est prépondérant, et de manière équivalente moins
le terme d’attache aux données est fort ; en particulier, cela signifie que la solution u∗
sera régulier, au détriment de sa proximité avec la donnée bruitée g.
En posant J la fonction objectif de ce problème, on voit que J est convexe, et
même fortement convexe (de module 1) grâce au terme d’attache aux données. Elle est
également différentiable, de gradient
∀u ∈ X, ∇J(u) = u − g + λ (∇h )∗ ∇h u = (Id + λ (∇h )∗ ∇h ) u − g
On voit donc que ∇J est lipschitzien, de constante de Lipschitz
L = |||Id + λ (∇h )∗ ∇h |||
Les itérations de la méthode du gradient explicite s’écrivent
uk+1 = uk − τ uk − g + λ (∇h )∗ ∇h uk


∀ k ∈ N,
et si le pas de temps est choisi strictement inférieur à 2/L, on a la convergence de
l’algorithme, tandis qu’un pas de temps strictement inférieur à 1/L assure un convergence
linéaire.

4.2 Approximation du problème de Rudin–Osher–Fatemi

La méthode décrite dans le paragraphe précédent souffre d’un inconvénient impor-
tant : elle a tendance à sur-lisser les images / signaux. Dans le cas d’une image qui
comporte des discontinuités (par exemple des photographies usuelles), cela crée des ar-
téfacts gênants.
Une manière de restituer les discontinuités naturelles présentes dans le signal original
(idéal), Rudin, Osher et Fatemi ont proposé de remplacer la régularisation de de
Tikhonov par la régularisation suivante :
TV(u) = ∥∇h u∥2
appelée variation totale de u. Ici, dans sa version discrétisée, il s’agit simplement de
remplacer la norme au carré par la norme. En procédant de la sorte, on perd la régularité
de la fonction objective, et la méthode du gradient explicite n’est plus applicable.
Pour être en mesure d’appliquer cette méthode, on peut remplacer la norme (non
différentiable), par une approximation régulière, comme celles introduites dans le mo-
dule a4 : Fonctions régulières, par exemple
q
gε (u) = ∥∇h u∥2 + ε
TV 2

avec ε > 0. Notons que, plus ε est petit, plus l’approximation est précise, mais plus
la constante de Lipschitz du gradient de J est grand (et donc les pas de temps de la
méthode du gradient petits).

Pauline Tan 15 V2.9.2023

5mm71 : Méthodes du premier ordre pour l’optimisation... Sorbonne Université

Pour aller plus loin

Fonctions régulières. La méthode du gradient explicite est la méthode la
plus simple pour optimiser une fonction régulière, mais n’est pas applicable qu’à
une famille de problèmes restreinte. La différentiabilité est en particulier une
propriété difficile à obtenir dans les problèmes pratiques. Une manière de l’obte-
nir est de remplacer le problème initial par un problème régulier en remplaçant
tout ou partie de la fonction objectif par une approximation régulière. Lorsque
la non-régularité de la fonction objectif provient de l’utilisation d’une norme,
on peut utiliser l’approximation régulière de la valeur absolue introduite dans
le module a4 : Fonctions régulières.
Algorithme du point proximal. Lorsque le problème est non différen-
tiable, une idée naturelle est de remplacer le gradient par un sous-gradient.
En pratique, le comportement de cette variante n’est pas intéressant (en par-
ticulier, le sous-gradient n’est pas nécessairement une direction de descente).
En revanche, au lieu de prendre un sous-gradient au point courant xk , si on le
prend au point suivant xk+1 , alors on obtient un algorithme très adapté à l’op-
timisation de fonctions non différentiables, appelé algorithme du point proximal
(module b3 : Algorithme du point proximal). La difficulté principale ré-
side dans la possibilité de calculer l’itération suivante, alors que le sous-gradient
(qui définit donc ce point) est lui-même pris en ce même point. On verra que ce
calcul fait intervenir un opérateur appelé proximal (module a5 : Opérateur
proximal de Moreau).
Éclatement d’opérateurs. Les itérations de la méthode du gradient inter-
viennent dans d’autres algorithmes, lorsque la fonction objectif est partiellement
régulière. On pourra citer en particulier l’algorithme FBS (module b4 : Écla-
tement primal d’opérateurs), pour lequel l’étude de la convergence utilise
des résultats établis pour la méthode du gradient.

Pauline Tan 16 V2.9.2023