Sciences des données

Cours #5 : Optimisation numérique d’une fonction

Stéphane Robin
© Équipe enseignante LU1INMA1
Cours #5 : Optimisation numérique d’une fonction
Plan du cours

1 Annulation d’une fonction

Méthode par dichotomie
Méthode du point fixe
Méthode de Newton

2 Minimisation d’une fonction

Méthode de Newton
Cas des moindres carrés

3 Minimisation d’une fonction de plusieurs variables

Méthode de Newton par coordonnée
Cas des moindres carrés
Dérivée partielle, gradient
Descente de gradient

4 Démonstrations

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 1/43
Cours #5 : Optimisation numérique d’une fonction
Plan du cours

1 Annulation d’une fonction

Méthode par dichotomie
Méthode du point fixe
Méthode de Newton

2 Minimisation d’une fonction

Méthode de Newton
Cas des moindres carrés

3 Minimisation d’une fonction de plusieurs variables

Méthode de Newton par coordonnée
Cas des moindres carrés
Dérivée partielle, gradient
Descente de gradient

4 Démonstrations

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 2/43
Annulation d’une fonction

Objectif. Déterminer la racine x ∗ d’une fonction f , c’est-à-dire la solution de l’équation

f (x) = 0.

Fonction f (x) = 1 − x + exp(−3x)

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 3/43
Rappels : Dérivée

Le signe de la dérivée f ′ (x) d’une fonction x → f (x) indique son sens de variation.

Fonction f (x) = 1 − x + exp(−3x)

Dérivée
f ′ (x) = −1 − 3 exp(−3x) < 0
(car e u ≥ 0).

On a
lim f (x) = +∞ et lim f (x) = −∞,
x→−∞ x→+∞

et f est continue, donc {f (x) = 0} admet une unique solution x ∗ .

Puisque f (0) = 2, on conclue que x ∗ > 0.

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 4/43
Méthode par dichotomie

Principe : On procède par encadrements successifs de la solution x ∗ .

Recherche de la racine d’une fonction par dichotomie

(0) (0)
Initialisation : Choisir xmin et xmax tels que

(0) (0)
xmin < x ∗ < xmax

et une précision ϵ.
(h−1) (h−1)
Itération h : Calculer x (h) = (xmin + xmax )/2.
(h−1) (h−1)
Si f (x (h) ) est du même signe que f (xmin ) (f (x (h) )f (xmin ) > 0), alors

(h) (h) (h−1)

xmin = x (h) , xmax = xmax .

(h−1) (h−1)
Si f (x (h) ) est du même signe que f (xmax ) (f (x (h) )f (xmax ) > 0), alors
(h) (h−1) (h)
xmin = xmin , xmax = x (h) .

(h) (h)
Arrêt : Quand xmax − xmin < ϵ.

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 5/43
Méthode par dichotomie : exemple
Fonction f (x) = 1 − x + exp(−3x)
On vérifie
f (1/2) ≃ 5.98169 > 0 et f (3/2) ≃ −0.488891 < 0
(h) (h)
pour choisir xmin = −1/2 et xmax = 3/2
(h) (h) (h) (h)
h xmin xmax x (h) f (xmin ) f (xmax ) f (x (h) )
0 -5.00000e-01 1.50000e+00 5.00000e-01 5.982e+00 -4.889e-01 7.231e-01
1 5.00000e-01 1.50000e+00 1.00000e+00 7.231e-01 -4.889e-01 4.979e-02
2 1.00000e+00 1.50000e+00 1.25000e+00 4.979e-02 -4.889e-01 -2.265e-01
3 1.00000e+00 1.25000e+00 1.12500e+00 4.979e-02 -2.265e-01 -9.079e-02
. . . . . . .
. . . . . . .
. . . . . . .
18 1.04367e+00 1.04368e+00 1.04367e+00 2.924e-06 -5.704e-06 -1.390e-06
19 1.04367e+00 1.04367e+00 1.04367e+00 2.924e-06 -1.390e-06 7.673e-07
20 1.04367e+00 1.04367e+00 1.04367e+00 7.673e-07 -1.390e-06 -3.113e-07

L’algorithme converge vers x ∗ si f

est strictement monotone sur l’intervalle
[xmin , xmax ] à vitesse exponentielle : (1/2)h .

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 6/43
Méthode du point fixe

Objectif. On cherche la solution de l’équation, dite du point fixe :

g(x) = x.

La solution x ∗ est invariante (“fixe”) par la fonction g : g(x ∗ ) = x ∗ .

Principe de l’algorithme. On itère la fonction g jusqu’à stabilisation.

Algorithme du point fixe

Initialisation : Choisir x (0) et une précision ϵ.

Itération h : Calculer x (h) = g(x (h−1) ).
Arrêt : Quand |x (h) − x (h−1) | < ϵ.

Remarque. Le problème est équivalent à résoudre f (x) = 0 en posant

g(x) = f (x) + x.

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 7/43
Méthode du point fixe : exemple

Fonction f (x) = 1 − x + exp(−3x)

On pose
g(x) = f (x) + x = 1 + exp(−3x)
et on se donne x (0) = 0.

h x (h) g(x (h) ) f (x (h) )

0 0.000000e+00 2.000000e+00 2.000000e+00
1 2.000000e+00 1.002479e+00 -9.975212e-01
2 1.002479e+00 1.049418e+00 4.693946e-02
3 1.049418e+00 1.042927e+00 -6.491227e-03
4 1.042927e+00 1.043771e+00 8.441390e-04
5 1.043771e+00 1.043660e+00 -1.107065e-04
6 1.043660e+00 1.043675e+00 1.450288e-05
7 1.043675e+00 1.043673e+00 -1.900196e-06
8 1.043673e+00 1.043673e+00 2.489626e-07
9 1.043673e+00 1.043673e+00 -3.261901e-08

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 8/43
Méthode du point fixe : conditions de convergence (1/3)
Remarque. L’algorithme du point fixe ne converge pas systématiquement vers une solution de
l’équation x = g(x).

Fonction f (x) = xe x − 1 − x
On cherche la solution de l’équation

x = g(x) avec g(x) = f (x) + x = xe x − 1.

Cette équation admet en fait deux solutions : x1∗ ≃ −1.35 et x2∗ ≃ 0.806.

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 9/43
Méthode du point fixe : conditions de convergence (2/3)
Fonction f (x) = xe x − 1 − x, g(x) = xe x − 1

x (0) = −4 x (0) = 0

Le comportement dépend du
point initial x (0) :

x (0) = 0.7 x (0) = 0.9 x1∗ ≃ −1.35 : “attractrice”

x2∗ ≃ 0.806 : “répulsive”

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 10/43
Méthode du point fixe : conditions de convergence (3/3)

La convergence de l’algorithme du point-fixe dépend de la valeur de la dérivée de la fonction g

au voisinage de la solution x ∗ .

Convergence de l’algorithme du point fixe

L’algorithme converge vers x ∗ si la valeur absolue de la dérivée de g est strictement inférieure
à 1 au voisinage de x ∗ .
(g est alors dite “contractante”.)

(La démonstration de cette propriété fait appelle au théorème des valeurs intermédiaires.)

Fonction f (x) = xe x − 1 − x, g(x) = xe x − 1

On a g ′ (x) = e x (x + 1), donc

g ′ (x1∗ ) ≃ −0.0907, g ′ (x2∗ ) ≃ 4.05

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 11/43
Rappels : Tangente
Tangente
La tangente en x0 à la courbe d’équation y = f (x) est la droite de pente f ′ (x0 ) passant par le
point (x0 , f (x0 )).

Équation de la tangente
La tangente en x0 à la courbe y = f (x) a pour équation

a0 = f (x0 ) − f ′ (x0 )x0 ,


y = a0 + b0 x avec (1)
b0 = f ′ (x0 ).

Fonction f (x) = 1 − x + exp(−3x)

Soit x0 = 0 :

f (x0 ) = 2, f ′ (x0 ) = −4

Tangente à f en x0 :

y = 2 − 4x.

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 12/43
Méthode de Newton (Newton-Raphson)

Heuristique. L’intersection entre la tangente à f en un point x0 et l’axe de abscisse fournit une

approximation de la solution de l’équation f (x) = 0.

Fonction f (x) = 1 − x + exp(−3x)

x0 = 0

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 13/43
Méthode de Newton : itération

Itération Newton
Le point d’intersection de la tangente en x0 à la fonction f a pour abscisse

f (x0 )
x1 = x0 − . (2)
f ′ (x0 )

Fonction f (x) = 1 − x + exp(−3x)

Partant de x (0) = 0, on peut ré-itérer l’opéra-

tion :

x (0) = 0

x (1) = x (0) − f (x (0) )/f ′ (x (0) ) = 1/2

x (2) = x (1) − f (x (1) )/f ′ (x (1) ) = ...

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 14/43
Méthode de Newton : algorithme
Algorithme de Newton

Initialisation : Choisir x (0) et une précision ϵ.

Itération h : Calculer
f (x (h−1) )
x (h) = x (h−1) −
f ′ (x (h−1) )
Arrêt : Quand |x (h) − x (h−1) | < ϵ.

Fonction f (x) = 1 − x + exp(−3x)

x (0) = 0

h x (h) f (x (h) )
0 0.000000e+00 2.000000e+00
1 5.000000e-01 7.231302e-01
2 9.331702e-01 1.276697e-01
3 1.041134e+00 2.872884e-03
4 1.043672e+00 1.272217e-06
5 1.043673e+00 2.486900e-13
6 1.043673e+00 2.220446e-16

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 15/43
Méthode de Newton : point initial (1/2)
Remarques.
L’algorithme de Newton ne converge pas systématiquement vers une solution de
l’équation.
Le résultat final peut dépendre du choix du point de départ x (0) , notamment quand il
existe plusieurs solutions

Fonction f (x) = exp(−2 cos(x)) − x

x (0) = −1

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 16/43
Méthode de Newton : point initial (2/2)

Fonction f (x) = exp(−2 cos(x)) − x

x (0) = 2.8 x (0) = 2.9 x (0) = 5

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 17/43
Cours #5 : Optimisation numérique d’une fonction
Plan du cours

1 Annulation d’une fonction

Méthode par dichotomie
Méthode du point fixe
Méthode de Newton

2 Minimisation d’une fonction

Méthode de Newton
Cas des moindres carrés

3 Minimisation d’une fonction de plusieurs variables

Méthode de Newton par coordonnée
Cas des moindres carrés
Dérivée partielle, gradient
Descente de gradient

4 Démonstrations

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 18/43
Minimisation d’une fonction
Objectif. On cherche le minimum de la fonction f (x).
L’extremum d’une fonction f continuement dérivable annule f ′ :

f ′ (x) = 0.

Fonction f (x) = x 2 + exp(x)

La dérivée

f ′ (x) = 2x + exp(x)

est strictement croissante avec

lim f ′ (x) = −∞, lim f ′ (x) = +∞.

x→−∞ x→+∞

donc
f ′ s’annule en un seul x ∗
x est un minimum (puisque f ′ (x) < 0 pour
x < x ∗ et f ′ (x) > 0 pour x > x ∗ ).
L’objectif est de déterminer x ∗ .

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 19/43
Adaptation de la méthode de Newton

Puiqu’on veut résoudre l’équation

f ′ (x) = 0,
toutes les méthodes précédentes peuvent être utilisées en remplaçant f par f ′ .

Exemple : Méthode de Newton.

Formule de Newton pour l’annulation

f (x0 )
x1 = x0 − .
f ′ (x0 )

Formule de Newton pour la minimisation

f ′ (x0 )
x1 = x0 − .
f ′′ (x0 )

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 20/43
Algorithme de Newton pour la minimisation
Algorithme de Newton pour la minimisation d’une fonction

Initialisation : Choisir x (0) et une précision ϵ.

Itération h : Calculer
f ′ (x (h−1) )
x (h) = x (h−1) −
f ′′ (x (h−1) )
Arrêt : Quand |x (h) − x (h−1) | < ϵ.

Fonction f (x) = x 2 + exp(x)

f ′ (x) = 2x + exp(x), f ′′ (x) = 2 + exp(x).

x (0) = 0
h x (h) f (x (h) ) f ′ (x (h) ) f ′′ (x (h) )
0 0.000e+00 1.000e+00 1.000e+00 3.000e+00
1 -3.333e-01 8.276e-01 4.986e-02 2.717e+00
2 -3.517e-01 8.272e-01 1.200e-04 2.703e+00
3 -3.517e-01 8.272e-01 6.928e-10 2.703e+00
4 -3.517e-01 8.272e-01 1.110e-16 2.703e+00
Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 21/43
Méthode de Newton : dépendance au point de départ

Fonction f (x) = (x 2 − 1)2 + 1

x (0) = −2 x (0) = 1.5

x∗ f (x ∗ ) f ′ (x ∗ ) f ′′ (x ∗ ) x∗ f (x ∗ ) f ′ (x ∗ ) f ′′ (x ∗ )
-1 1 0 8 1 1 0 8

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 22/43
Méthode de Newton : minimum ou maximum ?
La dérivée est nulle pour un maximum ou un minimum : le signe de la dérivée seconde f ′′ (x ∗ )
indique s’il s’agit d’un maximum (f ′′ (x ∗ ) < 0) ou d’un minimum (f ′′ (x ∗ ) > 0).

Fonction f (x) = (x 2 − 1)2 + 1

x (0) = −0.4 x (0) = −0.5

x∗ f (x ∗ ) f ′ (x ∗ ) f ′′ (x ∗ ) x∗ f (x ∗ ) f ′ (x ∗ ) f ′′ (x ∗ )
0 2 0 -4 1 1 0 8

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 23/43
Application : Ajustement d’une fonction
Objectif. Déterminer la “meilleure” valeur d’un paramètre a pour ajuster une fonction
y ≃ ga (x)
à partir des observations
x = [x1 . . . xn ]⊤ , y = [y1 . . . yn ]⊤ .

Données fictives (A)

Données :
i xi yi
1 0.000 0.103
2 0.250 1.376
3 0.500 3.007
4 0.750 0.560
5 1.000 1.934
6 1.250 2.531
.. .. ..
. . .

On cherche

yi ≃ e axi .

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 24/43
Critère des moindres carrés
De façon analogue à la régression linéaire, on peut considérer le critère
n
X
C (a) = (yi − ga (xi ))2 = C (a; x, y).
i=1

Données fictives (A)

ga (x) = e ax :

n
X
C (a) = (yi − e axi )2
i=1

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 25/43
Méthode de Newton pour les moindres carrés

La méthode de Newton requiert les dérivées première et seconde de ce critère par rapport à a
(et non par rapport aux xi ).

Dérivées du critère des moindres carrés

Pour toute valeur de x, on définit
hx (a) = ga (x).
Le critère devient
n
X
C (a) = (yi − hxi (a))2 ,
i=1

et ses dérivées valent

n
X
C ′ (a) = −2 hx′ i (a)(yi − hxi (a)) (3)
i=1
Xn  
C ′′ (a) = −2 hx′′i (a)(yi − hxi (a)) − (hx′ i (a))2 .
i=1

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 26/43
Méthode de Newton pour les moindres carrés : exemple (1/2)

Fonction ga (x) = e ax

hxi (a) = e axi , hx′ i (a) = xi e axi , hx′′i (a) = xi2 e axi
donc
n
X
C ′ (a) = −2 xi e axi (yi − e axi ),
i=1
Xn n
X
C ′′ (a) = −2 xi2 e axi (yi − e axi ) − xi2 e 2axi = −2 xi2 e axi (yi − 2e axi ) .

i=1 i=1

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 27/43
Méthode de Newton pour les moindres carrés : exemple (2/2)

Fonction ga (x) = e ax
Partant de a(0) = 1 :

a∗ C (a∗ ) C ′ (a∗ ) C ′′ (a∗ )

0.706953 22.7433 1.20871e-11 157298

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 28/43
Cours #5 : Optimisation numérique d’une fonction
Plan du cours

1 Annulation d’une fonction

Méthode par dichotomie
Méthode du point fixe
Méthode de Newton

2 Minimisation d’une fonction

Méthode de Newton
Cas des moindres carrés

3 Minimisation d’une fonction de plusieurs variables

Méthode de Newton par coordonnée
Cas des moindres carrés
Dérivée partielle, gradient
Descente de gradient

4 Démonstrations

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 29/43
Méthode de Newton par coordonnée

0bjectif. On veut maintenant minimiser une fonction de plusieurs variables f (x, y ).

Principe. On alterne des itérations de Newton dédiées à chacune des coordonnées en

définissant les fonctions

uy (x) = f (x, y ) et vx (y ) = f (x, y )

Newton : recherche de l’optimum d’une fonction bivariée

Initialisation : Choisir (x (0) , y (0) ) et une précision ϵ.

Itération h : Mettre à jour x :
u ′ (h−1) (x (h−1) )
y
x (h) = x (h−1) − ,
u ′′(h−1) (x (h−1) )
y

puis y :
v ′ (h) (y (h−1) )
x
y (h) = y (h−1) − .
v ′′(h) (y (h−1) )
x

Arrêt : Quand max(|x (h) − x (h−1) |, |y (h) − y (h−1) |) < ϵ.

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 30/43
Moindres carrés
Objectif. Déterminer les “meilleurs” paramètres a et b pour ajuster une fonction
y ≃ ga,b (x)
à partir d’observations de la forme
x = [x1 . . . xn ]⊤ , y = [y1 . . . yn ]⊤ .

Données fictives (B)

ga,b (x) = a(1 − e −bxi ).

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 31/43
Critère des moindres carrés
On définit le critère analogue au cas à un paramètre :
n
X
C (a, b) = (yi − ga,b (xi ))2 .
i=1

Données fictives (B) : ga,b (x) = a(1 − e −bx )

n 
X  2
C (a, b) = yi − a 1 − e −bxi
i=1

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 32/43
Critère des moindres carrés : dérivées

Algorithme de Newton. Il faut calculer les dérivées du critères C par rapport à a et b.

Pour calculer ces dérivées, on introduit les fonctions

Ub (a) = C (a, b), Va (b) = C (a, b)

Pour toute valeur de x, on définit les fonctions

ub,x (a) = ga,b (x), va,x (b) = ga,b (x)

On obtient alors

Ub (a), Ub′ (a), Ub′′ (a) en remplaçant hxi (a) par ub,xi (a) et

Vb (a), Vb′ (a), Vb′′ (a) en remplaçant hxi (a) par va,xi (b)

dans les équations (3), vues pour le cas à un paramètre.

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 33/43
Moindres carrés : exemple (1/2)

Données fictives (B) : ga,b = a(1 − e −bx )

Algorithme partant de a(0) = 4, b(0) = .5 Critère C (a(h) , b(h) )

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 34/43
Moindres carrés : exemple (2/2)

Données fictives (B) : ga,b = a(1 − e −bx )

Valeurs optimales des paramètres partant de a0 = 4, b = 1/2 :

a∗ b∗ ub′ ∗ (a∗ ) va′ ∗ (b∗ ) ub′′∗ (a∗ ) va′′∗ (b∗ ) C (a∗ , b∗ )

2.032e+00 9.998e-01 1.102e-05 -1.647e-11 2.909e+01 8.146e+00 1.590e-01

(Les dérivées premières sont proches de 0, les dérivées secondes sont positives.)
Courbe “ajustée”

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 35/43
Dérivées partielles
Intuition. La minimisation est d’autant plus rapide que l’algorithme se déplace dans la direction
de plus grande variation de la fonction multivariée f (u1 , u2 , . . . ud ).

Cette direction est donnée par le gradient dont la définition repose sur celle de dérivée partielle.

Dérivée partielle
La dérivée partielle ∂uj f de la fonction f de Rd dans R au point u = (u1 , u2 , . . . ud ) est la
fonction de Rd dans R qui associe à u la dérivée de par rapport à uj (1 ≤ j ≤ d), calculée au
point u, les autres coordonnées uk (k ̸= j) étant fixes.

Fonction f (u1 , u2 ) = u1 /u2

1 u1
∂u1 f (u1 , u2 ) = , ∂u2 f (u1 , u2 ) = − .
u2 u22

Fonction f (a, x) = e ax

∂a f (a, x) = xe ax , ∂x f (a, x) = ae ax .
Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 36/43
Gradient
Vecteur gradient
Le vecteur gradient de la fonction f de Rd dans R au point u = (u1 , u2 , . . . ud ) est le vecteur
de ses dérivées partielles au point u :
 ⊤
∇f (u) = ∂u1 f (u) ∂u2 f (u) . . . ∂ud f (u) .

Vecteur gradient de la perte quadratique pour la fonction ga,b (x) = a(1 − e −bx )

n
X
C (a, b) = (yi − ga,b (xi ))2 .
i=1

Flèches = directions de plus grand accroisse-

ment de la fonction C .

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 37/43
Descente de gradient

Principe. L’algorithme de descente de gradient vise à minimiser une fonction en se déplaçant

dans la direction opposée au vecteur gradient.

Vecteur gradient de la perte quadratique pour la fonction ga,b (x) = a(1 − e −bx )

Les flèches indiquent la direction dans laquelle la fonction C décroît le plus.

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 38/43
Algorithme de descente du gradient
Recherche du minimum d’une fonction multivariée par descente de gradient

Initialisation : Choisir un point u(0) , un pas γ et une précision ϵ.

Itération h : Calculer le vecteur gradient au point u(h−1) : ∇f (u(h−1) ) et itérer

u(h) = u(h−1) − γ∇f (u(h−1) )

Arrêt : Quand ∥u(h) − u(h−1) ∥ < ϵ.

Perte quadratique pour la fonction ga,b (x) = a(1 − e −bx )

Partant de a(0) = 4, b(0) = 1/2

Résultat final
a∗ b∗ ub′ ∗ (a∗ ) va′ ∗ (b∗ ) C (a∗ , b∗ )
2.0325 0.9995 0.0004 -0.0001 0.1590

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 39/43
Descente du gradient : choix du pas (1/3)

Perte quadratique pour la fonction ga,b (x) = a(1 − e −bx )

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 40/43
Descente du gradient : choix du pas (2/3)

Perte quadratique pour la fonction ga,b (x) = a(1 − e −bx )

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 41/43
Descente du gradient : choix du pas (3/3)

Choix de γ. Le choix du pas γ conditionne grandement le comportement de l’algorithme :

un pas γ trop faible produit un comportement régulier au prix d’un grand nombre
d’itérations,

un pas γ trop grand peut conduire à un comportement erratique.

Choix automatique de γ. Il existe des techniques de détermination automatique du pas de

gradient γ, fondée notamment sur la notion de développement limité.

Elles permettent notamment de faire varier le pas γ au cours des itérations (γ devient alors
γ (h) ).

Exemple. Dans le cas d’une fonction d’une variable, l’algorithme de Newton est un algorithme
de descente de gradient de pas
1
γ (h) = ′′ (h)
f (x )

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 42/43
Á retenir: cours 5

Définitions et algorithmes Définitions et algorithmes

Dichotomie : La dérivée partielle ∂uj f de la fonction f de Rd dans

On coupe et on garde un demi-intervalle qui contient R au point u = (u1 , u2 , . . . ud ) :
une racine, et on itère.
on fixe les uk (k ̸= j) ;
Méthode du point fixe :
On itère x (h) = g(x (h−1) )
on dérive par rapport à uj .
Méthode de Newton Le vecteur gradient de f en u :
h i⊺
Extremum d’une fonction (Newton) : ∇f (u) = ∂u1 f (u) ∂u2 f (u) . . . ∂ud f (u) .

Initialisation : Choisir x (0) et une précision ϵ. Minimisation par descente de gradient

Itération h : Calculer
Initialisation : Choisir un point u(0) , un pas γ
f ′ (x (h−1) ) et une précision ϵ.
x (h) = x (h−1) −
f ′′ (x (h−1) ) Itération h : Calculer le vecteur gradient au
point u(h−1) : ∇f (u(h−1) ) et
Arrêt : Quand |x (h) − x (h−1) | < ϵ. itérer
Si f ′′ (x ∗ ) < 0 : maximum. u(h) = u(h−1) − γ∇f (u(h−1) )
Si f ′′ (x ∗ ) > 0 : minimum.
Arrêt : Quand ∥u(h) − u(h−1) ∥ < ϵ.
Méthode de Newton par coordonnée.

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 43/43
Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 44/43
Si le temps le permet

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 45/43
Critère des moindres carrés : dérivées

Algorithme de Newton. Il faut calculer les dérivées du critères C par rapport à a et b.

Pour calculer ces dérivées, on introduit les fonctions

Ub (a) = C (a, b), Va (b) = C (a, b)

Pour chaque 1 ≤ i ≤ n, on définit les fonctions

ub,xi (a) = ga,b (xi ), va,xi (b) = ga,b (xi )

et on obtient
n
X n
X
Ub (a) = C (a, b) = (yi − ga,b (xi ))2 = (yi − ub,xi (a))2 ,
i=1 i=1
n 
X  n
X
Ub′ (a) = ′
2(−ub,x i
(a))(yi − ub,xi (a)) = −2 ′
ub,xi
(a)(yi − ub,xi (a)),
i=1 i=1
n 
X 
Ub′′ (a) = −2 ′′
ub,x i
′
(a)(yi − ub,xi (a)) − (ub,xi
(a))2 .
i=1

Les dérivées de la fonction Va s’obtiennent par symétrie.

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 46/43
Dérivées de C (a, b) pour ga,b (x) = a(1 − e −bx )
Fonction ga,b (x) = a(1 − e −bx )

ub,x (a) = a(1 − e −bx ), va,x (b) = a(1 − e −bx ) = a − ae −bx

donc
′
ub,x (a) = (1 − e −bx ), ′′
ub,x (a) = 0, ′
va,x (b) = axe −bx , ′′
va,x (b) = −ax 2 e −bx .

Dérivées de Ub :
n
X
Ub′ (a) = −2 (1 − e −bxi )(yi − a(1 − e −bxi )),
i=1
Xn  
Ub′′ (a) = −2 0 × (yi − a(1 − e −bxi ) − (1 − e −bxi )2
i=1
n
X
=2 (1 − e −bxi )2 ,
i=1

Dérivées de Va :
n
X n
X
Va′ (b) = −2 axi e −bxi (yi − a(1 − e −bxi )) = −2a xi e −bxi (yi − a(1 − e −bxi )),
i=1 i=1
Xn  
Va′′ (b) = −2 −axi2 e −bxi (yi − a(1 − e −bxi )) − (axi e −bxi )2
Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 47/43
Cours #5 : Optimisation numérique d’une fonction
Plan du cours

1 Annulation d’une fonction

Méthode par dichotomie
Méthode du point fixe
Méthode de Newton

2 Minimisation d’une fonction

Méthode de Newton
Cas des moindres carrés

3 Minimisation d’une fonction de plusieurs variables

Méthode de Newton par coordonnée
Cas des moindres carrés
Dérivée partielle, gradient
Descente de gradient

4 Démonstrations

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 48/43
Démonstrations

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 49/43
Rappels

Démonstration de l’équation (1). Pas définition de la pente de la tangente, on sait que

b0 = f ′ (x0 ). Il reste à vérifier que cette droite passe par le point (x0 , f (x0 )), c’est-à-dire

f (x0 ) = a0 + f ′ (x0 )x0 ⇔ a = f (x0 ) − f ′ (x0 )x0

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 50/43
Méthode de Newton

Démonstration de l’équation (2). Il suffit d’utiliser l’équation de la tangente (1) appliquée à f

en x0 :
y = (f (x0 ) − f ′ (x0 )x0 ) + f ′ (x0 )x
et de résoudre en x
f (x0 )
0 = (f (x0 ) − f ′ (x0 )x0 ) + f ′ (x0 )x ⇔ x = x0 − .
f ′ (x0 )

Stéphane Robin — Cours #5 : Optimisation numérique d’une fonction — Sciences des données — 2023–2024 51/43