Cours : Méthodes numériques pour l’optimisation
(Leçon 2)
Formation Data Science
Objectifs de la leçon
• Comprendre les principes fondamentaux de l’optimisation numérique et son appli-
cation dans la data science.
• Maîtriser les méthodes de recherche de minimums locaux et globaux dans des fonc-
tions multivariées.
• Appliquer les méthodes d’optimisation de base telles que la méthode du gradient,
la méthode de Newton, et l’optimisation contraint.
Partie 1 : Introduction à l’optimisation numérique
L’optimisation numérique est une branche des mathématiques appliquées qui permet de
trouver la meilleure solution possible pour un problème donné, souvent en minimisant ou
maximisant une fonction. Elle est essentielle en data science pour ajuster des modèles,
réduire les erreurs et améliorer les performances des algorithmes.
Partie 2 : Types d’optimisation
L’optimisation peut être divisée en plusieurs catégories en fonction du problème à résoudre
:
• Optimisation sans contrainte : Trouver le minimum (ou maximum) d’une fonc-
tion sans restrictions supplémentaires.
• Optimisation avec contrainte : Résoudre un problème d’optimisation en tenant
compte de certaines restrictions (par exemple, des limites sur les variables).
Partie 3 : Méthodes d’optimisation sans contrainte
3.1 Méthode du Gradient
La méthode du gradient est une technique itérative qui consiste à se déplacer dans la
direction du gradient négatif de la fonction à minimiser. Cette méthode est simple et
largement utilisée, mais elle peut être sensible aux choix des pas de mise à jour.
1
Formule du gradient :
xk+1 = xk − αk ∇f (xk )
- xk : vecteur de paramètres à l’itération k - αk : pas d’apprentissage (taux d’apprentissage)
- ∇f (xk ) : gradient de la fonction à l’itération k
Exemple avec Python
1 import numpy as np
2
3 # Fonction minimiser : f ( x ) = x ^2 + 4 x + 4
4 def f ( x ) :
5 return x **2 + 4* x + 4
6
7 # Gradient de la fonction
8 def grad_f ( x ) :
9 return 2* x + 4
10
11 # Gradient Descent
12 def gradient_descent ( learning_rate =0.1 , n_iterations =100) :
13 x = 0 # point de d p a r t
14 for i in range ( n_iterations ) :
15 x -= learning_rate * grad_f ( x )
16 print ( f " Iteration { i +1}: x = { x } , f ( x ) = { f ( x ) } " )
17 return x
18
19 # Appliquer la m t h o d e de gradient
20 minimum = gradient_descent ( learning_rate =0.1)
21 print ( f " Minimum t r o u v : x = { minimum } " )
Listing 1: Exemple de méthode du gradient en Python
3.2 Méthode de Newton
La méthode de Newton est plus rapide que la méthode du gradient, car elle utilise la
deuxième dérivée de la fonction (la matrice Hessienne) pour ajuster la direction du pas.
Elle est particulièrement utile lorsque la fonction est bien "comportée" (c’est-à-dire si sa
Hessienne est définie positive).
Formule de la méthode de Newton :
xk+1 = xk − H −1 ∇f (xk )
- H : Hessienne de la fonction f
Exemple avec Python
1 from scipy . optimize import minimize
2
3 # Fonction minimiser : f ( x ) = x ^2 + 4 x + 4
2
4 def f ( x ) :
5 return x **2 + 4* x + 4
6
7 # Appliquer la m t h o d e de Newton avec SciPy
8 result = minimize (f , 0 , method = ’ Newton - CG ’)
9 print ( f " Minimum t r o u v avec Newton : x = { result . x [0]} , f ( x ) = {
result . fun } " )
Listing 2: Exemple de méthode de Newton avec SciPy
Partie 4 : Méthodes d’optimisation avec contrainte
Les problèmes d’optimisation avec contrainte apparaissent fréquemment dans les do-
maines de la data science et de l’ingénierie. Par exemple, un modèle peut nécessiter
de minimiser une fonction tout en respectant certaines contraintes sur les variables (par
exemple, les paramètres d’un modèle ne doivent pas dépasser une certaine limite).
Méthode des multiplicateurs de Lagrange
La méthode des multiplicateurs de Lagrange permet de résoudre un problème d’optimisation
sous contrainte. On introduit des multiplicateurs de Lagrange λ qui ajustent la fonction
objective pour tenir compte des contraintes.
Formule des multiplicateurs de Lagrange :
L(x, λ) = f (x) + λ(g(x) − c)
- f (x) : fonction objective à minimiser - g(x) : fonction de contrainte - c : constante de
la contrainte
Exemple avec Python (optimisation avec contrainte)
1 from scipy . optimize import minimize
2
3 # Fonction minimiser
4 def f ( x ) :
5 return x [0]**2 + x [1]**2
6
7 # Contrainte : x1 + x2 = 1
8 def constraint ( x ) :
9 return x [0] + x [1] - 1
10
11 # D f i n i r la contrainte
12 con = { ’ type ’: ’ eq ’ , ’ fun ’: constraint }
13
14 # Appliquer l ’ optimisation sous contrainte
15 result = minimize (f , [0 , 0] , constraints = con )
16 print ( f " Solution sous contrainte : x1 = { result . x [0]} , x2 = {
result . x [1]} , f ( x ) = { result . fun } " )
Listing 3: Exemple d’optimisation sous contrainte avec Python
3
Partie 5 : Exercices pratiques
Exercice 1 : Optimisation sans contrainte
Appliquez la méthode du gradient à la fonction suivante et trouvez son minimum :
f (x) = x3 − 6x2 + 9x + 5
Exercice 2 : Optimisation avec contrainte
Résolvez le problème suivant sous contrainte : minimisez f (x, y) = x2 + y 2 sous la con-
trainte x + y = 3.
Partie 6 : Conclusion
L’optimisation numérique est un outil clé en data science pour ajuster les modèles,
améliorer les performances et résoudre des problèmes complexes. Les méthodes abor-
dées, comme le gradient, la méthode de Newton, et les multiplicateurs de Lagrange,
permettent de résoudre efficacement des problèmes d’optimisation dans divers contextes.
