Cours : Méthodes Numériques pour l’Optimisation
Formation Data Science
Objectifs du cours
• Comprendre les principes fondamentaux des méthodes d’optimisation.
• Explorer les algorithmes d’optimisation utilisés en data science et ingénierie.
• Développer des compétences pratiques pour résoudre des problèmes d’optimisation
avec Python.
Partie 1 : Introduction aux méthodes d’optimisation (2
heures)
1.1 Pourquoi l’optimisation est-elle importante ?
L’optimisation est au cœur de nombreux problèmes en data science et ingénierie. Elle
permet de trouver la solution optimale à un problème donné sous certaines contraintes.
Applications typiques :
• Optimisation des coûts dans une chaîne logistique.
• Ajustement des hyperparamètres en apprentissage automatique.
• Optimisation des performances des systèmes industriels.
1.2 Concepts fondamentaux
• Fonction objectif : La fonction que nous cherchons à maximiser ou minimiser.
• Variables de décision : Les paramètres que nous ajustons pour optimiser la
fonction objectif.
• Contraintes : Les limites ou conditions imposées sur les variables de décision.
Exemple simple :
• Problème : Maximiser f (x) = −x2 + 4x.
• Solution analytique : Trouver la dérivée première, f ′ (x) = −2x + 4, et résoudre
f ′ (x) = 0.
1
Partie 2 : Optimisation convexe et non convexe (4 heures)
2.1 Optimisation convexe
• Une fonction est convexe si f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ).
• Les problèmes convexes ont une propriété clé : tout minimum local est un minimum
global.
Exemple : f (x) = x2 + 2x + 1 est convexe car sa dérivée seconde est positive.
Exemple Python :
1 import numpy as np
2 import matplotlib . pyplot as plt
3
4 # D f i n i r une fonction convexe
5 x = np . linspace ( -10 , 10 , 100)
6 y = x **2 + 2* x + 1
7
8 plt . plot (x , y , label = ’f ( x ) = x ^2 + 2 x + 1 ’)
9 plt . title ( ’ Exemple de fonction convexe ’)
10 plt . xlabel ( ’x ’)
11 plt . ylabel ( ’f ( x ) ’)
12 plt . legend ()
13 plt . grid ()
14 plt . show ()
2.2 Optimisation non convexe
• Les fonctions non convexes peuvent avoir plusieurs minima locaux.
• Résoudre ces problèmes nécessite des algorithmes spécifiques (e.g., recuit simulé,
algorithmes génétiques).
Partie 3 : Méthodes analytiques et numériques (8 heures)
3.1 Méthode de la descente de gradient
• Algorithme itératif qui ajuste les variables dans la direction opposée au gradient de
la fonction objectif.
• Formule : xn+1 = xn − α∇f (xn ), où α est le pas d’apprentissage.
Exemple Python :
1 def gradient_descent (f , grad_f , x0 , learning_rate , tol ) :
2 x = x0
3 while abs ( grad_f ( x ) ) > tol :
4 x = x - learning_rate * grad_f ( x )
5 return x
6
2
7 # Exemple : f ( x ) = x ^2 , grad_f ( x ) = 2 x
8 f = lambda x : x **2
9 grad_f = lambda x : 2* x
10 result = gradient_descent (f , grad_f , x0 =10 , learning_rate =0.1 , tol
=1 e -6)
11 print ( " Minimum t r o u v x = " , result )
3.2 Méthode de Newton
• Utilise la dérivée seconde pour ajuster la direction et la vitesse de la descente.
f ′ (xn )
• Formule : xn+1 = xn − f ′′ (xn )
.
Exemple Python :
1 def newton_method (f , f_prime , f_double_prime , x0 , tol ) :
2 x = x0
3 while abs ( f_prime ( x ) ) > tol :
4 x = x - f_prime ( x ) / f_double_prime ( x )
5 return x
6
7 # Exemple : f ( x ) = x ^2 , f ’( x ) = 2x , f ’ ’( x ) = 2
8 f = lambda x : x **2
9 f_prime = lambda x : 2* x
10 f_double_prime = lambda x : 2
11 result = newton_method (f , f_prime , f_double_prime , x0 =10 , tol =1 e
-6)
12 print ( " Minimum t r o u v x = " , result )
Partie 4 : Optimisation stochastique (4 heures)
4.1 Descente de gradient stochastique (SGD)
• Approximations du gradient calculées sur des sous-ensembles aléatoires de données.
• Particulièrement utile pour les grands ensembles de données.
4.2 Recuit simulé et algorithmes génétiques
• Recuit simulé : inspiré du processus de refroidissement des métaux.
• Algorithmes génétiques : s’appuient sur les concepts de mutation et sélection
naturelle.
Exercices et projets
Exercice 1 : Résolution d’un problème d’optimisation convexe
Problème : Minimiser f (x) = x2 − 6x + 9 en utilisant la descente de gradient.
3
Projet : Optimisation des hyperparamètres d’un modèle de ma-
chine learning
Objectif : Utiliser des techniques comme la recherche sur grille ou la descente de gradient
pour optimiser un modèle SVM sur un jeu de données.
