L3 MIASHS Analyse avancée 2

Roland Becker

22 juillet 2024

Table des matières

1 Rappel : Analyse réelle univarié 2

2 Rappel : Algèbre linéaire 4

3 Problèmes d’optimisation 5

4 Optimisation sans contraintes 7

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 Condition d’ordre un nécessaire . . . . . . . . . . . . . . . . . . . . . . . . 9
4.4 Condition d’ordre deux nécessaire . . . . . . . . . . . . . . . . . . . . . . 10
4.5 Condition d’ordre un suffisante . . . . . . . . . . . . . . . . . . . . . . . . 11
4.6 Condition d’ordre deux suffisante . . . . . . . . . . . . . . . . . . . . . . 11
4.7 Convergence de la méthode du gradient . . . . . . . . . . . . . . . . . . . 12
4.7.1 Gradient lipschitzien (pas constant) . . . . . . . . . . . . . . . . . 12
4.7.2 Gradient lipschitzien et convexité (pas constant) . . . . . . . . . . 13
4.7.3 Gradient lipschitzien et µ-convexité (pas constant) . . . . . . . . . 15
4.7.4 Gradient lipschitzien (pas adaptatif) . . . . . . . . . . . . . . . . . 16
4.8 Méthode d’ordre plus élevé . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

5 Calcul différentiel 18

6 Convexité 21
6.1 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1
1 Rappel : Analyse réelle univariée

Definition 1.1: Inf et Sup

Soit A ⊂ R. 

 +∞ A = ∅
inf A := −∞ A non-minoré (1.1)


plus grand minorant sinon
x ∈ R est un ≪ minorant ≫ ssi x ⩽ a pour tout a ∈ A.
≪ plus grand minorant ≫ veut dire : x∗ est ≪ plus grand minorant ≫ ssi

• pour tout a ∈ A on a x ⩽ a et
• pour tout ε > 0 il existe aε ∈ A tel que aε − ε < x.
Le plus grand minorant est unique ! (Sinon on ne pourrait définir l’infimum).
Si inf A ∈ A, on dit que la borne inférieure est atteinte et on écrit inf A = min A.

Lemma 1.1: Inf définition équivalente

Soit A ⊂ R, A ̸= ∅. Alors il existe une suite (an )n∈N ⊂ A telle que inf A =
limn→∞ an .

Example 1.1

A = [0, 1], inf A = 0, (inf A ∈ A),

A =]0, 1], inf A = 0, (inf A ̸∈ A),
A =] − ∞, 0], inf A = −∞, (inf A ̸∈ A).

Definition 1.2: (Différentiabilité 1D)

Soit I ⊂ R un intervalle non-vide, f : I → R et x ∈ I. On dit que f est dérivable en

x si et seulement si la limite suivante existe : On dit que f est dérivable en x si et
seulement s’il existe d ∈ R et une fonction R : I → R tels que

R(t)
f(x) = f(x0 ) + d(x − x0 ) + R(x − x0 ) et lim = 0. (1.2)
t→0
t̸=0
|t|

Alors d est unique et l’on écrit f ′ (x0 ) := d. f is dérivable sur I si f est dérivable an
tout x0 ∈ I. Dans ce cas, f ′ : I → R définie par x → f ′ (x) est la fonction dérivée.
Si elle est continue, on écrit f ∈ C1 (I).

2
Démontrer l’unicité de d dans (1.2) par contradiction. Dans le cas où x0 est une
extrémité de l’intervalle (1.2) définit la dérivée à gauche ou à droite. Montrer que
la définition est équivalente à

f(x0 + h) − f(x0 )
lim = f ′ (x0 ). (1.3)
h→0 h
h̸=0
x0 +h∈I

Proposition 1.1

Nous avons les règles suivantes. Si u, v ∈ C1 (I), alors u + λv ∈ C1 (I) pour tout
λ ∈ R, uv ∈ C1 (I) et

(u + λv) ′ = u ′ + λv ′ , (uv) ′ = u ′ v + uv ′ . (1.4)

Si f ∈ C1 (J) avec u(I) ⊂ J, la fonction f ◦ u ∈ C1 (I) et

f(u(x)) ′ = f ′ (u(x)u ′ (x). (1.5)

Theorem 1.1: Théorème fondamental du calcul différentiel

Soit f ∈ C1 (I) et a, b ∈ I. Alors

Zb
f(b) − f(a) = f ′ (x) dx. (1.6)
a

Avec (1.4) on obtient

Corollary 1.1: Intégration par parties

Si f, g ∈ C1 ([a, b]) nous avons

Zb Zb
f ′ (x)g(x) dx = − f(x)g ′ (x) dx + f(b)g(b) − f(a)g(a). (1.7)
a a

3
2 Rappel : Algèbre linéaire

Definition 2.1: Espace euclidien

Soit n ∈ N. L’espace vectoriel Rn est muni d’un produit scalaire ⟨·, ·⟩ : Rn ×Rn →
R qui vérifie
1. ⟨u, u⟩ ⩾ 0 ∀u ∈ Rn
2. ⟨u, u⟩ = 0 ⇒ u=0 ∀u ∈ Rn
3. ⟨u, v⟩ = ⟨v, u⟩ ∀u, v ∈ Rn
4. ⟨u, λv + µw⟩ = λ⟨u, v⟩ + µ⟨u, w⟩ ∀u, v, w ∈ Rn , ∀λ, µ ∈ R
On peut résumer les deux dernières propriétés par la bilinéarité du produit sca-
laire. On utilise différentes notations :
X
n
u · v = ⟨u, v⟩ = uT v = ui vi .
i=1

La norme associé au produit scalaire est

v
uX
u n
p
∥x∥ := ⟨x, x⟩ = t x2i . (2.1)
i=1

Deux sous-espaces V1 ⊂ Rn et V2 ⊂ Rn sont orthogonaux (V1 ⊥ V2 ) ssi

⟨v1 , v2 ⟩ = 0 pour tout v1 ∈ V1 et v2 ∈ V2 . Pour un sous-espace V1 ⊂ Rn , V2
est son complément orthogonal si V1 ⊥ V2 et V1 + V2 = Rn .

Theorem 2.1: Cauchy-Schwarz et identités remarquables

Nous avons l’inégalité de Cauchy-Schwarz

⟨u, v⟩ ⩽ ∥u∥∥v∥ ∀u, v ∈ Rn , (2.2)

ainsi que l’identité remarquable

∥u + v∥2 = ∥u∥2 + 2⟨u, v⟩ + ∥v∥2 ⟨u + v, u − v⟩ = ∥u∥2 − ∥v∥2 ∀u, v ∈ Rn . (2.3)

Theorem 2.2: Diagonalisaton d’une matrice symétrique

Si A ∈ Rn×n est symétrique , il existe une base orthonormale de vecteurs propres

qi associés à des valeur propres réels λi

Aqi = λi qi 1 ⩽ i ⩽ n.

4
 Par conséquent A est diagonalisable

A = QΛQT , QT Q = I et Λ = diag(λi ) matrice diagonale. (2.4)

3 Problèmes d’optimisation

Definition 3.1: Problème d’optimisation

Un problème d’optimisation est un problème de minimisation ou de maximisa-

tion, défini par
• des variables indépendantes x ∈ Rn , n ⩾ 1,
• un ensemble admissible K ⊂ Rn (ensemble des contraintes),
• une fonction f : K → R, ≪ coût/perte ≫ pour la minimisation, ou
≪ gain ≫ pour la maximisation.

min f(x) max f(x). (3.1)

x∈K x∈K

• La définition précise est :

inf {f(x) : x ∈ K} (minimisation) sup {f(x) : x ∈ K} (maximisation).

Definition 3.2: Admissibilité

Le problème est admissible si K ̸= ∅, sinon il est non-admissible.

Definition 3.3: Solution (minimisation)

On suppose le problème admissible. Alors x∗ ∈ Rn est une solution (globale)

pour la minimisation si et seulement si
1. x∗ ∈ K et
2. f(x∗ ) ⩽ f(x) pour tout x ∈ K.
S’il existe une solution nous avons

inf f(x) = min f(x)

x∈K x∈K

Definition 3.4: Valeur optimale (minimisation)

Si x∗ est une solution globale, la valeur optimale du problème est

f∗ = f(x∗ ).

5
Definition 3.5: Ensemble des solutions (minimisation)

Si inf x∈K f(x) = minx∈K f(x) l’ensemble de solutions est

argmin {f(x) : x ∈ K} = {x ∈ K : f(x) = f∗ } . (3.2)

Si la solution est unique on écrit souvent x∗ = argmin {f(x) : x ∈ K} ou x∗ =

argminx∈K f(x).

Definition 3.6: Solution locale (minimisation)

x∗ ∈ K est une solution locale pour la minimisation si et seulement si il existe

η > 0 tel que

x ∈ K et ∥x − x∗ ∥ ⩽ η ⇒ f(x∗ ) ⩽ f(x).

Une solution globale est une solution locale.

Remark 3.1

• On peut toujours transformer un problème de minimisation en problème

de maximisation.
• Il est import de comprendre la différence entre ≪ min ≫ et ≪ inf ≫, voir
définition 1.1.

Remark 3.2: Différents problèmes

La nature de K est de f détermine différentes classes de problèmes

• Optimisation sans contraintes : K = Rn .
• Optimisation linéaire (programmation linéaire) : K = {g(x) ⩽ 0 | x ∈ Rn }
avec f et g linéaires.
• Optimisation quadratique, convexe, non-lisse,...

Remark 3.3
Il est convenable de travailler avec ±∞ :
• Minimisation :

+∞ si K = ∅
inf f(x) =
K −∞ si si le problème est non-borné inférieurement.

Le deuxième cas : il existe une suite (xk )k∈N telle que lim f(xk ) = −∞.
k→∞

6
 • Maximisation :

−∞ si K = ∅
sup f(x) =
K +∞ si si le problème est non-borné supérieurement.

Le deuxième cas : il existe une suite (xk )k∈N telle que lim f(xk ) = +∞.
k→∞
On considère donc souvent f : Rn → R, R := R ∪ {+∞} ∪ {−∞}. Avec la fonction
indicatrice χK : Rn → R

+∞ si x ̸∈ K
χK =
0 six ∈ K.

nous avons

inf f(x) = infn (f(x) + χK (x)) .

x∈K x∈R

Remark 3.4: Optimisation sur un ensemble fini

Si K = {1, . . . , n}, on écrit i à la place de x et fi à la place de f(x). Cela donne :

inf {fi | 1 ⩽ i ⩽ n} = inf fi . (3.3)

1⩽i⩽n

Il existe toujours un solution, que l’on peut trouver par comparaison (O(n2 )
opérations).

4 Optimisation sans contraintes

4.1 Introduction
On s’intéresse à la minimisation d’une fonction f : Rn → R (f ∈ C1 (Rn ))

inf f(x). (4.1)

x∈Rn

On s’intéresse à des algorithmes de la forme suivante. Ici, on ne discutera pas le

critère d’arrêt, pourtant primordial dans les applications.

Algorithm 4.1: Algorithme général

Inputs : x0 ∈ X, t0 > 0. Set k = 0.

(1) Déterminer direction pk .

7
 (2) Déterminer step-size tk .
(3) Mise à jour xk+1 = xk + tk pk .
(4) Si critère d’arrêt est satisfait, retour output (xk+1 ,· · · ).
(5) Incrémenter k et retour à (1).

D’abord, on s’intéresse à savoir si un tel algorithme a une chance de converger.

Proposition 4.1

Supposons que l’ensemble

S0 := {x ∈ Rn | f(x) ⩽ f(x0 )} (4.2)

est borné inférieurement. Alors le problème (4.1) possède au moins une solution.

Démonstration. L’ensemble S0 est fermé, car f est continue. D’après le lemme 1.1, il
existe une suite (xk )k∈N telle que inf x∈Rn f(x) = lim f(xk ). Si la suite (f(xk ))k∈N ten-
k→∞
dait vers −∞, on aurait un N ∈ N tel que f(xk ) ⩽ f(x0 ) pour k ⩾ N, ce qui revient à
dire que xk ∈ S0 . Une contradiction.

Remark 4.1
La condition de la proposition 4.1 est satisfaite, si f est coercive, c’est à dire

lim f(x) = +∞.

∥x∥→∞

Maintenant on s’intéresse à ce qui se passe en une itération. On écrit x = xk , p = pk .

Pour t ∈ R \ {0} on peut prévoir le changement grâce au calcul différentiel. D’après le
développement de Taylors d’ordre un (5.4) (avec F = f et y = x + tp) nous avons

R1 (t)
f(x + tp) = f(x) + t⟨∇f(x), p⟩ + R1 (t), lim = 0. (4.3)
y→x
y̸=x
|t|

Pour t petit, on peut négliger R1 et (4.3) montrer que p = −∇f(x) est un choix qui
permet de diminuer f.
Si f ∈ C2 (Rn , R), nous avons aussi

t2 2 R2 (t)
f(x + tp) = f(x) + t⟨∇f(x), p⟩ + ⟨∇ f(x)p, p⟩ + R2 (t), lim = 0. (4.4)
2 y→x
y̸=x |t|2

8
4.2 Exemples

Example 4.1: Solution d’équations matricielles

µ 1
f(x) = ∥x∥2 + xT Ax − xT , A ∈ Rn×n (A symétrique). (4.5)
2 2

Example 4.2: Moindres carrés avec régularisation de Tikhonov

µ 1
f(x) = ∥x∥2 + ∥Ax − b∥2 , A ∈ Rm×n . (4.6)
2 2

Example 4.3: Regression logistique régularisée (classification binaire)

µ X m X n
f(x) = ∥x∥2 + log(1 + exp(yi aij xj )), yi ∈ {−1, +1} . (4.7)
2
i=1 j=1

Example 4.4: Regression logistique

X
m X
n
!
f(x) = ρ log rk (x) , rk (x) = exp( (akj xj − bk )/ρ) (4.8)
k=1 j=1

Example 4.5: Perte de Huber

µ X m X n
f(x) = ∥x∥2 + log(cosh(yi − aij xj )), yi ∈ {−1, +1} . (4.9)
2
i=1 j=1

Example 4.6: Rosenbrock banana function

f(x) = (1 − x1 )2 + 100(x2 − x1 )2 (4.10)

4.3 Condition d’ordre un nécessaire

Supposons que x∗ ∈ Rn soit une solution locale de (4.1). Alors nous avons pour tout
p ∈ Rn \ {0} et t ∈ R \ {0}
0 ⩽ f(x∗ + tp) − f(x∗ ) = t⟨∇f(x∗ ), p⟩ + R1 (t).
On divise par t > 0 et on utiliser la deuxième équations de (4.3) pour faire tendre t → 0.
Cela donne ⟨∇f(x∗ ), p⟩ ⩾ 0. Ensuite on utiliser t < 0 pour obtenir ⟨∇f(x∗ ), p⟩ ⩽ 0, donc
⟨∇f(x∗ ), p⟩ = 0. Pour p = ∇f(x∗ ) on obtient le résultat suivant

9
 Theorem 4.1: Condition d’ordre un nécessaire

Si f ∈ C1 (Rn ) et x∗ ∈ Rn est une solution locale de (4.1), nous avons

∇f(x∗ ) = 0. (4.11)

Remark 4.2

• L’exemple f(x) = x3 (n = 1) et x̄ = 0 , montre que l’implication dans l’autre

sens est fausse. De f ′ (x̄) on ne peut déduire que x̄ est une solution locale.
• Nous avons converti le problème de l’optimisation en problème de
résolution d’une équations.
• (4.11) peut avoir plusieurs solutions.

4.4 Condition d’ordre deux nécessaire

Supposons que x∗ ∈ Rn soit une solution de (4.1) et f ∈ C2 (Rn ). A l’aide de la
condition d’ordre un (4.11), (4.4) se simplifie

t2 2 ∗
0 ⩽ f(x∗ + tp) − f(x∗ ) = ⟨∇ f(x )p, p⟩ + R2 (t).
2
En divisant par t2 on obtient le résultat suivant.

Theorem 4.2: Condition d’ordre deux nécessaire

Si f ∈ C2 (Rn ) et x∗ ∈ Rn est une solution locale de (4.1), nous avons

∇f(x∗ ) = 0, ⟨∇2 f(x∗ )p, p⟩ ⩾ 0 ∀p ∈ Rn . (4.12)

Remark 4.3

Le deuxième inégalité de (4.12) exprime que la hessienne ∇2 f(x∗ ) (qui est tou-
jours symétrique) est positive semi-définie. L’algèbre linéaire, théorème 2.2, nous
dit que cela est équivalent à ce que toutes ses valeurs propres sont positives ou
nulles :

λi = λi (∇2 f(x∗ )) .


λ1 ⩾ λ2 · · · ⩾ λn ⩾ 0,

10
4.5 Condition d’ordre un suffisante
Sous quelle condition ∇f(x∗ ) est suffisante ? C’est à -dire quand ∇f(x) = 0 implique
x = x∗ ? Supposons ∇f(x) = 0. Alors (4.3) donne

R1 (t)
f(x + tp) = f(x) + R1 (t), lim = 0.
y→x
y̸=x
|t|

On voit que pour déduire que f(x + tp) ⩾ f(x) il faudrait savoir que R1 (t) ⩾ 0. Cela est
le cas, si la fonction est convexe :

f(y) ⩾ f(x) + ⟨∇f(x), y − x⟩ ∀x, y ∈ Rn . (4.13)

Voir sous-section 6.1.

Theorem 4.3: Condition d’ordre un suffisante

Si f ∈ C1 (Rn ) est convexe et x̄ ∈ Rn tel que ∇f(x̄) = 0, alors x̄ ∈ argmin f(x).

x∈Rn

4.6 Condition d’ordre deux suffisante

Supposons f ∈ C2 (Rn ) et que x̄ ∈ Rn est un point stationnaire, ∇f(x̄) = 0. Alors
(4.4) se simplifie en

t2 t2
 
R2 (t)
f(x̄ + tp) = f(x̄) + ⟨∇2 f(x̄)p, p⟩ + R2 (t) = f(x̄) + ⟨∇2 f(x̄)p, p⟩ + 2 .
2 2 t
⟨∇2 f(x̄)p,p⟩
Supposons maintenant qu’il existe µ > 0 tel que ∥p∥2
⩾ µ pour tout p ∈ Rn \ {0}.
Alors nous avons
R2 (t) R2 (t)
⟨∇2 f(x̄)p, p⟩ + 2
⩾ µ∥p∥2 + 2 ⩾ 0 si t petit.
t t
Ici, t dépend de p. On voudrait alors savoir qu’il existe t0 de sorte que ce dernier terme
soit positif pour tout p avec ∥p∥ = 1 et t ⩽ t0 (convergence uniforme). Nous admettons
cela.

Theorem 4.4: Condition d’ordre deux suffisante

Si f ∈ C2 (Rn ) et x̄ ∈ Rn vérifie

∇f(x̄) = 0, ⟨∇2 f(x̄)p, p⟩ > 0 ∀p ∈ Rn , (4.14)

alors x̄ est une solution locale.

11
 Remark 4.4
Comme pour le remarque 4.3, on fait appel à théorème 2.2. On peut alors donner
une condition équivalent à (4.14) :

λi = λi (∇2 f(x̄)) .


λ1 ⩾ λ2 · · · ⩾ λn > 0,

Remark 4.5

Comme montre l’example f(x) = x4 (n = 1) et x̄ = 0, on peut avoir une solution

locale (même globale) sans que (4.14) soit satisfaite.

4.7 Convergence de la méthode du gradient

Si l’on prend pk = −∇f(xk ) on obtient la méthode du gradient.

Algorithm 4.2: Méthode du gradient

Inputs : x0 ∈ X, t0 > 0. Set k = 0.

(1) Déterminer step-size tk .
(2) Mise à jour xk+1 = xk − tk ∇f(xk ).
(3) Si critère d’arrêt est satisfait, retour output (xk+1 ,· · · ).
(4) Incrémenter k et retour à (1).

Il existe différents algorithme pour choisir tk . On considère d’abord le cas le plus

simple, pas constant, avec différentes hypothèse sur f.

4.7.1 Gradient lipschitzien (pas constant)

Definition 4.1: Gradient L-lipschitzien

On dit que f possède un gradient L-lipschitzien ssi :

∥∇f(x) − ∇f(y)∥ ⩽ L∥x − y∥ ∀x, y ∈ X. (4.15)

Proposition 4.2: Convergence méthode du gradient (pas constant)

Soit f ∈ C1 (Rn ) et que (4.2) soit borné. On suppose que le pas satisfait

1
0 < tk = t ⩽ . (4.16)
L
x, i.e. ∇f(e
Alors l’algorithme 4.2 tend vers un point stationnaire e x) = 0.

12
Remark 4.6. Ce résultat est assez faible. D’abord, il ne donne aucune estimation de la vitesse
de convergence. Ensuite, ex ne correspond par forcément à un minimum, même local. De plus, la
mise en ouvre de l’algorithme nécessite la connaissance the L.

Démonstration. Nous utilisons (6.8) et nous posons pk = −∇f(xk ). Comme xk+1 − xk =

tpk nous avons
L
f(xk+1 ) ⩽ f(xk ) + ⟨∇f(xk ), tpk ⟩ + ∥tpk ∥2
 2  2  
Lt 2 Lt
⇒ f(xk+1 ) − f(xk ) ⩽ − t ∥pk ∥ = t − 1 ∥pk ∥2 .
2 2
1
Par conséquent, avec (4.16) nous avons tL/2 ⩽ 2 et

t
f(xk+1 ) − f(xk ) ⩽ − ∥∇f(xk ∥2 , (4.17)
2
ce qui donne

X
ℓ
tX
ℓ
f(xℓ+1 ) − f(x0 ) = (f(xk+1 ) − f(xk )) ⩽ − ∥pk ∥2 ,
2
k=0 k=0

et

tX
ℓ  
2 t t
∥∇f(xk )∥ ⩽ (f(x0 ) − f(xℓ+1 )) ⩽ f(x0 ) − inf f(x) .
2 2 2 x∈S0
k=0

Comme le second membre est indépendant de ℓ, nous avons démontré que la série
converge et lim ∥∇f(xk )∥ = 0. Alors on utilise
k→∞

X
ℓ+m−1 X
ℓ+m−1
xℓ+m − xℓ = (xk+1 − xk ) = −t ∇f(xk )
k=ℓ k=ℓ
X
ℓ+m−1 ∞
X
⇒ ∥xℓ+m − xℓ ∥ ⩽ t ∥∇f(xk )∥ ⩽ t ∥∇f(xk )∥.
k=ℓ k=ℓ

pour montrer que la limite de (xk )k∈N existe. La limte e

x est alors un point stationnaire
par continuité de ∇f.

4.7.2 Gradient lipschitzien et convexité (pas constant)

13
 Lemma 4.1
Sous l’hypothèse (4.15) et si f est convexe nous avons

1
f(y) ⩾ f(x) + ⟨∇f(x), y − x⟩ + ∥∇f(y) − ∇f(x)∥2 ∀x, y ∈ Rn . (4.18)
2L

Démonstration. On définit g(y) := f(y)−⟨∇f(x), y⟩, de sorte que ∇g(y) = ∇f(y)−∇f(x).

Donc g est convexe et grâce à ∥∇g(y) − ∇g(z)∥ = ∥∇f(y) − ∇f(z)∥ ⩽ L∥y − z∥ son
gradient est L-lipschitzien.
Comme ∇g(x) = 0, y = x est une solution de minimisation de inf y∈Rn g(y). Alors
avec (6.8) pour tout z ∈ Rn
 
L 2
g(x) ⩽ infn g(z) ⩽ infn g(y) + ⟨∇g(y), z − y⟩ + ∥y − z∥ .
z∈R z∈R 2

Le dernier infimum est atteint pour z = y − L1 ∇g(y) et on obtient

1
g(x) ⩽ g(y) − ∥∇g(y)∥2 ,
2L
ce qui implique
1 1
∥∇f(y) − ∇f(x)∥2 = ∥∇g(y)∥2 ⩽ g(y) − g(x) = f(y) − f(x) − ⟨∇f(x), y − x⟩.
2L 2L

Proposition 4.3

Soit f convexe et ∇f est L-Lipschitz. Sous la condition (4.16) nous avons l’estima-
tion d’erreur
∥x∗ − x0 ∥2 L∥x∗ − x0 ∥2
f(xk ) − f(x∗ ) ⩽ , ∥∇f(xk )∥2 ⩽ . (4.19)
2tk tk

Démonstration. Par (4.17) nous avons avec ∆fk := f(xk ) − f(x∗ )

t
∆fk+1 ⩽ ∆fk − ∥∇f(xk )∥2 .
2
Par convexité nous avons

∆fk = f(xk ) − f(x∗ ) ⩽ ⟨∇f(xk ), xk − x∗ ⟩.

Combiner les deux inégalités précédentes donne

t
∆fk+1 ⩽ ⟨∇f(xk ), xk − x∗ ⟩ − ∥∇f(xk )∥2 .
2

14
On note ensuite que

∥xk − x∗ ∥2 − ∥xk+1 − x∗ ∥2 =∥xk − x∗ ∥2 − ∥xk − x∗ − t∇f(xk )∥2

=2t⟨∇f(xk ), xk − x∗ ⟩ + t2 ∥∇f(xk )∥2

de sorte que
1
∥xk − x∗ ∥2 − ∥xk+1 − x∗ ∥2


∆fk+1 ⩽ (4.20)
2t
En additionnant nous avons
X
ℓ
1 1
∥x0 − x∗ ∥ − ∥xℓ+1 − x∗ ∥2 ⩽ ∥x0 − x∗ ∥2 .


∆fk ⩽
2t 2t
k=1

Par la monotonicité de (∆fk )k∈N nous avons

X
ℓ X
ℓ
1
∆fk ⩾ ∆fℓ = ℓ∆fℓ ⇒ ∆fℓ ⩽ ∥x0 − x∗ ∥.
2tℓ
k=1 k=1

De plus, (4.18) avec y = x∗ et x = xℓ donne comme ∇f(x∗ ) = 0

1 1
∆fℓ = f(xℓ ) − f(x∗ ) ⩾ ⟨∇f(x∗ ), xℓ − x∗ ⟩ + ∥∇f(xℓ ) − ∇f(x∗ )∥2 = ∥∇f(xℓ )∥2
2L 2L
Cela donne (4.19).

4.7.3 Gradient lipschitzien et µ-convexité (pas constant)

Proposition 4.4

Soit f fortement µ-convexe et ∇f L-lipschitzien. Sous la condition (4.16) nous

avons r
∗ k ∗ tµ
∥x − xk ∥ ⩽ ρ ∥x − x0 ∥, ρ = 1 − . (4.21)
1 + tµ
Pour t = 1/L on trouve avec κf := L/µ
r
1 1
ρ= 1− ⩽1− . (4.22)
κf + 1 2(κf + 1)

Démonstration. Comme dans la démonstration de la proposition 4.3 nous avons (4.20)

1
∥x∗ − xk ∥2 − ∥x∗ − xk+1 ∥2 .


∆fk+1 ⩽
2t
La forte µ-convexité donne
µ ∗
f(xk+1 ) ⩾ f(x∗ ) + ⟨∇f(x∗ ), xk+1 − x∗ ⟩ + ∥x − xk+1 ∥2 ,
2

15
de sorte que
µ ∗
∥x − xk+1 ∥2 ⩽ ∆fk+1 . (4.23)
2
Alors on trouve
1 1 1
(µ + )∥x∗ − xk+1 ∥2 ⩽ ∥x∗ − xk ∥2 ⇒ ∥x∗ − xk+1 ∥2 ⩽ ∥x∗ − xk ∥2
t t 1 + tµ

Nous savons que t = 1/L donne une méthode monotone, la fonction décroit en
chaque itération. On peut choisir le pas plus grand.

Proposition 4.5
2
Soit f fortement µ-convexe et ∇f L-lipschitzien. Sous la condition t = µ+L nous
avons
L−µ 2
∥x∗ − xk ∥ ⩽ ρk ∥x∗ − x0 ∥, ρ = =1− . (4.24)
L+µ κf + 1

Démonstration. L’inégalité suivante est valable pour toute fonction µ-convexe avec gra-
dient L-Lipschitz

µL 1
⟨∇f(x) − ∇f(y), x − y⟩ ⩾ ∥x − y∥2 + ∥∇f(x) − ∇f(y)∥2 . (4.25)
µ+L µ+L

Alors

∥x∗ − xk+1 ∥2 =∥x∗ − xk ∥2 − 2⟨x∗ − xk , xk+1 − xk ⟩ + ∥xk+1 − xk ∥2

=∥x∗ − xk ∥2 + 2t⟨x∗ − xk , ∇f(xk )⟩ + t2 ∥∇f(xk )∥2
=∥x∗ − xk ∥2 − 2t⟨∇f(xk ) − ∇f(x∗ ), xk − x∗ ⟩ + t2 ∥∇f(xk )∥2
   
µL ∗ 2 2 1
⩽ 1 − 2t ∥x − xk ∥ + t − 2t ∥∇f(xk )∥2
µ+L µ+L
(L − µ)2 ∗
 
4µL ∗ 2
= 1− ∥x − x k ∥ = ∥x − xk ∥2
(µ + L)2 (µ + L)2

4.7.4 Gradient lipschitzien (pas adaptatif)

On s’intéresse maintenant à l’algorithme 4.2. Nous présentons seulement l’algo-
rithme le plus simple pour adapter le pas.

16
 Algorithm 4.3: Méthode du gradient avec ’backtracking’

Inputs : x0 ∈ X, t0 > 0, 0 < ω < 1. On pose k = 0.

tk 2
(1) While f (xk − tk ∇f(xk )) > f(xk ) − 2 ∥∇f(xk )∥ : tk = ω ∗ t k .
(2) xk+1 = xk − tk ∇f(xk ).
(3) tk+1 = tk /ω.
(4) Incrémenter k et retour à (1).

Lemma 4.2
Si le gradient de f est L-lipschitzien, la boucle dans (1) de l’algorithme 4.3 s’arrête
avec tk ⩾ ω/L.

Démonstration. Pour t > 0 on définit x(t) := xk − t∇f(xk ) et

t
ψ(t) := f(x(t)) − f(xk ) + ∥∇f(xk )∥2 .
2

L’algorithme cherche à trouver t ∈ t0 ωℓ ℓ ∈ N tel que ψ(t) ⩽ 0 (avec ℓ le plus
possible). Nous utilsons (6.8) pour montrer que cela est possible.
 2 
L 2 Lt
f(x(t)) − f(xk ) ⩽⟨∇f(xk ), x(t) − xk ⟩ + ∥x(t) − xk ∥ = − t ∥∇f(xk )∥2
2 2
t
⇒ ψ(t) ⩽ (Lt − 1) ∥∇f(xk )∥2
2
Alors ψ(t) ⩽ 0 pour t ⩽ 1/L, et l’algorithme s’arrête si t0 ωℓ ⩽ 1/L. S’il s’arrête en ℓ
pour la première fois, nous avons t0 ωℓ−1 > 1/L ou tk > ω/L.

On peut vérifier que les résultats de convergence démontrés restent valable pour
l’algorithme 4.3.

4.8 Méthode d’ordre plus élevé

4.9 Exercices

Exercice 1 (Examples) Calculer les gradients et les hessiennes des exemples de la

section 4.2.

Exercice 2 (MG/Problèmes approchés) La méthode du gradient peut être in-

terpréter de la façon suivante. À chaque itération k, on minimise un problème ap-
proché :
xk+1 = argmin Q(x, tk , xk ) (4.26)
x∈Rn

17
avec
1
Q(x, t, y) := f(y) + ⟨∇f(y), x − y⟩ + ∥x − y∥2 (t > 0).
2t

1. Montrer que infn Q(x, t, y) admet une solution unique

x∈R
2. Calculer la solution de ce problem.
3. Calculer la valeur optimale.

Exercice 3 (MG pour f quadratique)

1. Préciser la méthode du gradient à pas fixe pour l’exemple (4.5).
2. Préciser la méthode du gradient à pas fixe pour l’exemple (4.6).

5 Calcul différentiel
Definition 5.1: Dérivées partielles

Soit U ⊂ Rn . Pour une fonction f : U → R et une direction i (et le vector

ei associé), 1 ⩽ i ⩽ n, donné, on considère la fonction ϕ(t) := f(x + tei ) =
f(x1 , · · · , xi−1 , xi + t, xi+1 , · · · , xn ). Si ϕ est dérivable en 0, f possède une dérivée
partielle en direction i et on note

∂f f(x + tei ) − f(x)

(x) = ϕ ′ (0) = lim . (5.1)
∂xi t→0
t̸=0
t

Definition 5.2: Différentiabilité

Soit U ⊂ Rn et m ∈ N. F : D → Rm est différentiable au point x ∈ U s’il existe
une matrice D ∈ Rm×n telle que

R(t)
F(y) = F(x) + D(y − x) + R(∥y − x∥) et lim = 0. (5.2)
t→0
t̸=0
|t|

Comme pour n = m = 1 D est unique et nous écrivons D = DF(x0 ) = F ′ (x0 ) =

dF(x0 ) = Fh (x). Si F(x) = (F1 (x), · · · , Fm (x))T , on a
 ∂F1 ∂F1 
∂x1 (x) · · · ∂xn (x)
Df(x) =  ... .. ..  .

. . 
∂Fm ∂Fm
∂x1 (x) ··· ∂xn (x)

F est différentiable sur U, si F est différentiable en tout x ∈ U. Si l’application

U → Rm×n , x → DF ′ (x) est continue on écrit F ∈ C1 (U, Rm ).

18
Dans le cas m = 1, on écrit f ∈ C1 (U) et on définit le gradient

∇f(x) := Df(x)T (⇒ D(h) = ⟨∇f(x), h⟩ ∀h ∈ Rn ) . (5.3)

Si x → ∇f(x) est différentiable, c’est-à-dire si chaque composante est

différentiable, la dérivée seconde est la matrice hessienne
 ∂2 f 2f 
∂x21
(x) · · · ∂x∂n ∂x i
(x)  2 
2
 . . .  ∂ f
∇ f(x) = Hf(x) =   .. .. ..  = ∂xi ∂xj (x)
 .
2
∂ f 2
∂ f 1⩽i,j⩽n
∂x1 ∂xn (x) · · · ∂x2 n
(x)

S’il dépend de manière continue de x, la hessienne est symétrique.

Example 5.1

On peut souvent calculer des dérivées multi-dimensionnelles de deux façon

différentes : soit avec les dérivées partielles, soit avec la définition. Prenons
comme example le carré de la norme,
1
N : Rn → R, N(x) = ∥x∥2 .
2
P
n
x2i
1. Par dérivées partielles. Comme N(x) = 2 , pour 1 ⩽ j, k ⩽ n
i=1

∂N(x) X ∂x2i X
n n
= = xi δij = xj
∂xj 2∂xj
i=1 i=1
∂2 N(x) ∂xj
= = δjk . ⇒ ∇N2 (x) = I.
∂xk ∂xj ∂xk

2. Par la définition
1 1
∥x + h∥2 − ∥x∥2 = ⟨x, h⟩ + ∥h∥2 .


N(x + h) − N(x) =
2 2
Comme
R(h)
N(x + h) − N(x) = ⟨∇N(x), h⟩ + R(h), lim = 0.
h→0
h̸=0
∥h∥

Nous avons bien ∇N(x) = x (et R(h) = ∥h∥2 /2).

∇N(x + h) − ∇N(x) = (x + h) − x = h = ∇2 N(x)h + R(h),

donc ∇2 N(x) = I (et R(h) = 0).

19
 Theorem 5.1: Taylor d’ordre un

Soit F ∈ C1 (Rn , Rm ). Alors pour tout y ̸= x

R1 (x, y)
F(y) = F(x) + DF(x)(y − x) + R1 (x, y), lim = 0. (5.4)
y→x
y̸=x
∥x − y∥

Theorem 5.2: Taylor d’ordre deux

Soit f ∈ C2 (Rn , R). Alors pour tout y ̸= x

1 R2 (x, y)
f(y) = f(x)+⟨∇f(x), y−x⟩+ ⟨∇2 f(x)(y−x), y−x⟩+R2 (x, y), lim = 0.
2 y→x
y̸=x
∥x − y∥2
(5.5)

Theorem 5.3: Taylor avec reste intégral

Soit f ∈ C1 (Rn ). Alors pour tout y ̸= x

Z1
f(y) = f(x) + ⟨∇f(x + t(y − x)), y − x⟩ dt. (5.6)
0

Si f ∈ C2 (Rn ) nous avons

Z1
f(y) = f(x) + ⟨∇f(x), y − x⟩ + ⟨∇2 f(x + t(y − x))(y − x), y − x⟩(1 − t) dt. (5.7)
0

Démonstration. Soit ϕ(t) := f(x + t(y − x)). Nous avons ϕ(0) = f(x), ϕ(1) = f(y) et
ϕ ′ (t) = ⟨∇f(x + t(y − x)), y − x⟩. Avec (1.6) nous avons
Z1 Z1 Z1
′ d= ′ d=
f(y) − f(x) = ϕ(1) − ϕ(0) = ϕ (t) ϕ (t) ⟨∇f(x + t(y − x)), y − x⟩ dt.
0 dt 0 dt 0

En suite nous avons ϕ ′′ (t) = ⟨∇2 f(x + t(y − x))(y − x), y − x⟩ et avec (1.7)
Z1 Z1 Z1
ϕ ′ (t) dt = ϕ ′ (t)(t − 1) ′ dt = − ϕ ′′ (t)(t − 1) dt + ϕ ′ (1)(1 − 1) − ϕ ′ (0)(0 − 1)
0 0 0
Z1
= ϕ ′′ (t)(1 − t) dt + ϕ ′ (0).
0

Cela donne le résultat.

20
 Theorem 5.4: Dérivée de la fonction composée

Soit m, n, p ∈ N, U ⊂ Rn , V ⊂ Rm , F ∈ C1 (U, Rm ), G ∈ C1 (V, Rp ) et F(U) ⊂ V.

Alors h := g ◦ f ∈ C1 (U, Rp ) et

Dh(x) = Dg(f(x))Df(x). (5.8)

Example 5.2
√
Pour la norme, on pose f(x) = ∥x∥2 et g(y) = y, qui est differentiable pour
y > 0. Alors la norme h(x) = ∥x∥ est differentiable sur Rn \ {0} et
1 x
Dh(x) = p (2x)T ⇒ ∇h(x) = .
2 ∥x∥2 ∥x∥
x
Pour calculer la hessienne, on remarque d’abord que ∇∥x∥−1 = − ∥x∥3 . On ob-
tient
xxT
 
2 1
∇ h(x) = I− .
∥x∥ ∥x∥2

6 Convexité
6.1 Fonctions convexes
Definition 6.1: Convexité (fonction)

Soit K ⊂ Rn un ensemble convexe. Une fonction f : K → R est convexe si et

seulement si pour tout a, b ∈ K et 0 ⩽ t ⩽ 1 on a

f((1 − t)a + tb) ⩽ (1 − t)f(a) + tf(b). (6.1)

Elle est strictement convexe, ssi

f((1 − t)a + tb) < (1 − t)f(a) + tf(b) ∀a, b ∈ K, a ̸= b, ∀0 < t < 1. (6.2)

Elle est µ-fortement convexe, ssi

µ
f((1 − t)a + tb) ⩽ (1 − t)f(a) + tf(b) − t(1 − t)∥a − b∥2 ∀a, b ∈ K, ∀0 ⩽ t ⩽ 1.
2
(6.3)

21
Example 6.1

Voici quelques examples de fonctions convexes.

1. Fonction affine : f(x) = a + bT x.
2. Fonction quadratique : f(x) = xT Ax ssi A définie positive (strictement
convexe ssi strictement définie-positive).
x2
3. Pour n = 1. f(x) = ex , f(x) = |x|p avec p ⩾ 1, f(x) = 1−|x| , f(x) = |x| −
log(1 + |x|).

Theorem 6.1: Caractérisation convexité

Soit f ∈ C1 (Rn ). f est µ-fortement convexe si et seulement si

µ
f(x) ⩾ f(y) + ⟨∇f(y), x − y⟩ + ∥x − y∥2 ∀x, y ∈ Rn , (6.4)
2
ou de façon équivalente

⟨∇f(x) − ∇f(y), x − y⟩ ⩾ µ∥x − y∥2 ∀x, y ∈ Rn . (6.5)

Soit f ∈ C2 (Rn ). f est µ-fortement convexe si et seulement si

ξT ∇2 f(x)ξ ⩾ µ∥ξ∥2 ∀ξ ∈ Rn , ∀x ∈ Rn . (6.6)

Remark 6.1

Le théorème reste vrai, si f ∈ C1 (Rn ) est convexe (µ = 0).

Remark 6.2
La définition de la convexité admet une interprétation graphique : le graphe de
la fonction est en-dessous de sa sécante. (6.4) signifie que le graphe est au-dessus
de la tangente.
La condition (6.5) signifie que ∇f est une application monotone (pour n = 1 la
dérivée est croissante). En général, elle implique pour µ > 0 que ∇f : Rn → Rn
est injective. Il existe alors une application inverse (sur son image).
Finalement (6.6) est équivalent à la positivité (stricte si µ > 0) des valeurs propres
de la hessienne.

Definition 6.2: Lipschitz

Soit K ⊂ Rn et F : K → Rm . F is L-Lischitz ssi’l existe L > 0 tel que

∥F(x) − F(y)∥ ⩽ L∥x − y∥ ∀x, y ∈ K.

22
 f : K → R possède un gradient L-Lischitz ssi

∥∇f(x) − ∇f(y)∥ ⩽ L∥x − y∥ ∀x, y ∈ K (6.7)

Example 6.2

Pour la fonction quadratique f(x) = 12 xT Ax − bT x, de sorte que dans (6.7) on a

L = λmax (A).

Proposition 6.1

Si f ∈ C1 (Rn ) avec gradient L-Lipschitz, nous avons

L
f(y) ⩽ f(x) + ⟨∇f(x), y − x⟩ + ∥x − y∥2 ∀x, y ∈ Rn . (6.8)
2

Démonstration. Nous avons avec (5.6)

Z1
f(y) = f(x) + ⟨∇f(x + t(y − x), y − x⟩ dt,
0

de sorte que l’inégalité de Cauchy-Schwarz (2.2) et la condition de Lipschitz (4.15)

donnent
Z1 Z1
f(y) − f(x) − ⟨∇f(x), y − x⟩ = ⟨∇f(x + t(y − x) − ∇f(x), y − x⟩ dt ⩽ tL∥x − y∥2 dt
0 0

23