020TMCCS4
Techniques mathématiques en génie chimique
Partie 1 : Optimisation
Semestre académique S4, 2022/2023
Département Génie chimique
Chapitre 4 : Optimisation sans contraintes – recherche multidimensionnelle
SLIDES PRÉPARÉES PAR : MANSOUR TAWK
Slides préparées par : Mansour Tawk
Sommaire
Généralisation
Méthodes basées sur les valeurs de la fonction
Recherche aléatoire
Recherche sur grilles
Méthode avec la dérivée première
Méthodes de gradient
Méthodes de gradient à pas optimal
Méthode de gradient à pas fixe
Méthode du gradient conjugué
Méthode de Newton
Méthode de Quasi-Newton
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 2
Partie 1 : Optimisation
1. Généralisation
Dans ce chapitre, on s’intéresse à la recherche des optimums ( maximum ou minimum) des fonctions
multidimensionnelles . Les méthodes sont similaires aux méthodes décrites pour le cas
monodimensionnelle .
Vu qu’il s’agit d’un problème à plusieurs variables, la recherche se fait dans plusieurs directions . On peut
résumer la méthode de recherche comme suit :
Choisir une direction 𝑑𝑑𝑘𝑘 ( direction de descente)
Choisir un point de départ 𝑥𝑥0
Déterminer un critère de convergence ( test d’arrêt)
Minimiser le long de cette direction
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 + 𝑡𝑡𝑘𝑘 𝑑𝑑𝑘𝑘 , avec 𝑡𝑡𝑘𝑘 : facteur ou pas de descente
Reproduire l’analyse sur une autre direction
Choix possibles pour les directions :
Un axe (𝑥𝑥, 𝑦𝑦, 𝑧𝑧), on commence par un axe 𝑥𝑥, ou , 𝑦𝑦, ou, 𝑧𝑧
𝑑𝑑1 conjugué de 𝑑𝑑0 par rapport à 𝐻𝐻, c’est-à-dire
𝑑𝑑1 𝑇𝑇 . 𝐻𝐻. 𝑑𝑑0 = 0
𝑑𝑑1 𝑇𝑇 . 𝑑𝑑0 = 0, ou 𝑑𝑑1 et 𝑑𝑑0 sont orthogonaux
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 3
Partie 1 : Optimisation
Exemple 4.1
Pour minimiser 𝑓𝑓 𝑥𝑥 , comment chercher les directions ?
Soit 𝑓𝑓 𝑥𝑥 = 5𝑥𝑥12 + 𝑥𝑥22 + 2𝑥𝑥1 𝑥𝑥2 − 12𝑥𝑥1 − 4𝑥𝑥2 + 8
1. Choisir une direction de départ 𝑑𝑑0 axe 𝑥𝑥1 ou axe 𝑥𝑥2
2. Commencer par un point de départ , ex. le point (0,-2)
3. Prendre une direction 𝑑𝑑1 conjugué à l’axe 𝑥𝑥1
4. Trouver une autre direction 𝑑𝑑2 conjugué à 𝑑𝑑1
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 4
Partie 1 : Optimisation
Exemple 4.1
Choisir une direction de départ 𝑑𝑑0 axe 𝑥𝑥1 ou axe 𝑥𝑥2
𝑇𝑇
𝑑𝑑0 ≡ 𝑎𝑎𝑎𝑎𝑎𝑎 𝑥𝑥1 = 1 0
Prendre une direction 𝑑𝑑1 conjugué à 𝑑𝑑0 (l’axe 𝑥𝑥1 )
𝑑𝑑1 conjugué de 𝑑𝑑0 → 𝑑𝑑1 𝑇𝑇 . 𝐻𝐻. 𝑑𝑑0 = 0, soit 𝑑𝑑1 𝑇𝑇
= 𝑎𝑎 𝑏𝑏
𝜕𝜕2 𝑓𝑓 𝜕𝜕2 𝑓𝑓
10𝑥𝑥1 + 2𝑥𝑥2 − 12 𝜕𝜕𝑥𝑥12 𝜕𝜕𝑥𝑥1 𝜕𝜕𝑥𝑥2 10 2
→ 𝐻𝐻 = =
2𝑥𝑥2 + 2𝑥𝑥1 − 4 𝜕𝜕2 𝑓𝑓 𝜕𝜕2 𝑓𝑓 2 2
𝜕𝜕𝜕𝜕𝜕𝜕𝜕𝜕 𝜕𝜕𝑦𝑦 2
10 2 1 1 𝑇𝑇
𝑑𝑑1 vérifie 𝑎𝑎 𝑏𝑏 =0 → 𝑎𝑎 = − 𝑏𝑏 → 𝑑𝑑1 = 1 −5
2 2 0 5
Trouver une autre direction 𝑑𝑑2 conjugué à 𝑑𝑑1
𝑑𝑑2 conjugué de 𝑑𝑑1 → 𝑑𝑑2 𝑇𝑇 . 𝐻𝐻. 𝑑𝑑1 = 0, soit 𝑑𝑑2 𝑇𝑇
= 𝑎𝑎 𝑏𝑏
10 2 1 𝑇𝑇
𝑑𝑑2 vérifie 𝑎𝑎 𝑏𝑏 =0 → 𝑎𝑎 = 1, 𝑏𝑏 = 0 → 𝑑𝑑2 = 1 0
2 2 −5
Pour une fonction quadratique on revient toujours à la même direction 𝑑𝑑0
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 5
Partie 1 : Optimisation
Exemple 4.2
2 1 2
a. Trouver 2 directions orthogonales à 𝑥𝑥 𝑇𝑇 = 3
−
3
−
3
et entre elle
b. Trouver 2 directions conjugués au vecteur 𝑥𝑥 et entre elle par rapport à la
2 1 0
matrice 1 2 1
0 1 3
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 6
Partie 1 : Optimisation
2. Méthodes basées sur les valeurs de la fonction
Dans ce cas, on n’a pas besoin des dérivées. Cette méthode est efficace et
rapide dans les cas où on a une fonction non linéaire ou discontinu. Dans
un cas général (fonction bien déterminé), elle s’avère complexe et couteuse .
Plusieurs méthodes de recherche d’optimisation existent :
Recherche aléatoire
Recherche sur grille
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 7
Partie 1 : Optimisation
2. Méthodes basées sur les valeurs de la fonction
2.1 Recherche aléatoire
Choix de 𝑥𝑥0 et calcul de 𝑓𝑓(𝑥𝑥0 ) d’une fonction aléatoire
Aléatoirement sélectionner un autre vecteur 𝑥𝑥1 et calculer 𝑓𝑓 𝑥𝑥1
A chaque étape on compare 𝑓𝑓(𝑥𝑥𝑘𝑘 ) à la valeur minimales de 𝑓𝑓(𝑥𝑥) des étapes
précédentes
Décision d’arrêter ou de continuer
La solution optimale est obtenue avec une probabilité de 1 quand 𝑘𝑘 → ∞
Cette méthode est inefficace mais être utilisée comme un bon point de
départ pour une autre méthode
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 8
Partie 1 : Optimisation
2. Méthodes basées sur les valeurs de la fonction
2.2 Recherche sur grilles
Le choix des 𝑥𝑥 n’est pas aléatoire. Il suit une certaine grille. Les autres étapes sont les
mêmes. 𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 + Δ𝑥𝑥
𝑥𝑥1 𝑥𝑥2
𝑥𝑥4
𝑥𝑥1
𝑥𝑥5 𝑥𝑥7
𝑥𝑥2 𝑥𝑥6 𝑥𝑥3
𝑥𝑥3
𝑥𝑥5 𝑥𝑥4
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 9
Partie 1 : Optimisation
3. Méthode avec la dérivée première
Il y’a un grand nombre de méthodes numériques de minimisation qui diffèrent suivant le
choix qui est fait sur 𝑑𝑑𝑘𝑘 et 𝑡𝑡𝑘𝑘 .
3.1 Méthodes de gradient
L’idée dans cette méthode est de prendre comme direction de descente
𝑑𝑑𝑘𝑘 = −𝛻𝛻𝛻 xk
En effet, 𝑓𝑓(𝑥𝑥𝑘𝑘 ) est orthogonal à la ligne de niveau de 𝑓𝑓 au point 𝑥𝑥𝑘𝑘 et la fonction 𝑓𝑓 diminue dans la
direction −𝛻𝛻𝛻 x𝑘𝑘 .
Le gradient est le vecteur qui donne localement la direction de la plus grande variation , donc:
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 − 𝑡𝑡𝑘𝑘 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )
Les facteurs de descente 𝑡𝑡𝑘𝑘 sont à choisir. Il y a plusieurs méthodes de gradient suivant le choix de 𝑡𝑡𝑘𝑘
3.2 Méthodes de gradient à pas optimal
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 − 𝑡𝑡𝑘𝑘 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 ) , avec 𝑡𝑡𝑘𝑘 ∈ ℝ
𝑓𝑓 𝑥𝑥𝑘𝑘 − 𝑡𝑡 𝑘𝑘 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 = min 𝑓𝑓( 𝑥𝑥𝑘𝑘 − 𝑡𝑡𝑘𝑘 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )) = min 𝑓𝑓( 𝑥𝑥𝑘𝑘+1 )
𝑡𝑡∈ℝ 𝑡𝑡
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 10
Partie 1 : Optimisation
Exemple 4.3
On veut minimiser 𝑓𝑓 𝑥𝑥 = 10𝑥𝑥12 + 𝑥𝑥22 en utilisant la méthode de
gradient à pas optimal. Commencer par 𝑥𝑥0 = 1 1 𝑇𝑇 . Peut-on attreindre
le minimum en deux itérations ?
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 11
Partie 1 : Optimisation
3. Méthode avec la dérivée première
3.3 Méthode de gradient à pas fixe
Cette méthode exige que 𝑡𝑡 soit constant durant toutes les étapes. A chaque itération
on calcule :
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 − 𝑡𝑡𝑘𝑘 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )
Le choix de 𝑡𝑡 est essentiel pour cette méthode. Il faut le choisir de facon que la
méthode converge. Ce choix est fortement lié à la forme de la fonction 𝑓𝑓 à optimiser
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 12
Partie 1 : Optimisation
3. Méthode avec la dérivée première
3.4 Méthode du gradient conjugué
Il s’agit d’une amélioration des méthodes des gradients en améliorant la direction de descente :
𝑘𝑘
𝑑𝑑𝑘𝑘 = ∑𝑖𝑖=0 𝛼𝛼𝑖𝑖 𝛻𝛻𝑓𝑓(𝑥𝑥𝑖𝑖 )
C’est une combinaison des informations sur le gradient de l’itération en cours et des itérations
antérieur.
Algorithme
Etape 1 : choisir 𝑥𝑥0 et calculer 𝑓𝑓 𝑥𝑥0 . Prendre 𝑑𝑑0 = 𝛻𝛻𝑓𝑓(𝑥𝑥0 )
Etape 2 : Calculer 𝑥𝑥1 = 𝑥𝑥0 + 𝛼𝛼0 𝑑𝑑0 en minimisant 𝑓𝑓 𝑥𝑥1 par rapport à 𝛼𝛼0 dans la direction 𝑑𝑑0 (recherche
monodimensionnelle)
Etape 3 : Calculer 𝑓𝑓(𝑥𝑥1 ) et 𝛻𝛻𝑓𝑓(𝑥𝑥1 )
𝑇𝑇 𝑇𝑇
𝛻𝛻𝑓𝑓 𝑥𝑥1 .𝛻𝛻𝑓𝑓 𝑥𝑥1 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘+1 .𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘+1
𝑑𝑑1 = − 𝛻𝛻𝑓𝑓 𝑥𝑥1 + 𝑑𝑑0 𝑇𝑇
Soit : 𝑑𝑑𝑘𝑘+1 = − 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘+1 + 𝑑𝑑0 𝑇𝑇
𝛻𝛻𝑓𝑓 𝑥𝑥0 .𝛻𝛻𝑓𝑓 𝑥𝑥0 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 .𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘
Etape 4 : Tester la convergence
Si la convergence est atteinte, arrêter , sinon, retourner à l’étape précédente.
Etape n : Terminer l’algorithme quant 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 <ℰ
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 13
Partie 1 : Optimisation
4. Méthode de Newton
D’une façon similaire à la méthode monodimensionnelle, on cherche un
minimum de la forme
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 − 𝐻𝐻 𝑥𝑥𝑘𝑘 −1 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘
Ou 𝐻𝐻 𝑥𝑥𝑘𝑘 −1 est l’inverse de la matrice hessienne 𝐻𝐻 𝑥𝑥𝑘𝑘 .
On peut améliorer la méthode en améliorant la direction de descente . Soit :
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 − 𝛼𝛼𝑘𝑘 𝐻𝐻 𝑥𝑥𝑘𝑘 −1 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘
La direction de descente est donnée par : 𝑑𝑑𝑘𝑘 = − 𝐻𝐻 𝑥𝑥𝑘𝑘 −1 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘
Notons que si on prend 𝛼𝛼 = 1 et que le point de départ est loin du minimum,
on ne converge pas nécessairement.
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 14
Partie 1 : Optimisation
Exemple 4.4
Minimiser la fonction 𝑓𝑓 𝑥𝑥 = 4𝑥𝑥12 + 𝑥𝑥22 − 2𝑥𝑥1 𝑥𝑥2 en prenant comme
point de départ 𝑥𝑥0 = 1 1 𝑇𝑇 .
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 15
Partie 1 : Optimisation
4. Méthode de Newton
Quelques remarques sur la méthode de Newton
Nécessite en général le moins d’itération pour se converger
On ne trouve pas forcement la solution globale si plusieurs extremum existent
Nécessite la résolution de 𝑛𝑛 équations linéaire symétriques
Nécessite les dérivées 1ère et 2ème , parfois compliqués à obtenir mais elle peuvent être
remplacées par des différences finies
Si le pas =1 , la méthode ne converge pas forcement.
Problème
Si 𝐻𝐻(𝑥𝑥) n’est pas définie positive la méthode ne converge pas
Solution
� 𝑥𝑥 = [𝐻𝐻 𝑥𝑥 + 𝛽𝛽𝛽𝛽] avec 𝛽𝛽 constante > 0
Utiliser une matrice modifiée ( décalage spatial) 𝐻𝐻
� 𝑥𝑥 définie positive
assez large pour avoir 𝐻𝐻
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 16
Partie 1 : Optimisation
4. Méthode de Newton
Critère d’arrêt
Comme toute méthode de descente, un critère d’arrêt est nécessaire
On peut prendre comme critère
𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘+1 2 ≤ 𝜖𝜖 2
Mais souvent, on préfère utiliser le critère
Δ 𝑥𝑥 ≤ 𝜖𝜖
Où : Δ 𝑥𝑥 = 𝐻𝐻 𝑥𝑥 −1 𝛻𝛻𝑓𝑓 𝑥𝑥 , 𝛻𝛻𝑓𝑓(𝑥𝑥) = − 𝑑𝑑 , 𝛻𝛻𝑓𝑓(𝑥𝑥)
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 17
Partie 1 : Optimisation
5. Méthode de Quasi-Newton
Elle utilise uniquement les dérivées 1ère , pas besoin de la matrice hessienne
On remplace 𝐻𝐻(𝑥𝑥𝑘𝑘 ) par une matrice définie positive 𝐻𝐻 � 𝑥𝑥𝑘𝑘
on résout 𝑑𝑑𝑘𝑘 →pour → 𝐻𝐻 �𝑘𝑘 𝑑𝑑𝑘𝑘 = −𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 ) avec 𝑑𝑑𝑘𝑘 = 𝑥𝑥𝑘𝑘+1 − 𝑥𝑥𝑘𝑘
� 𝑘𝑘 est initialisée à n’importe quelle matrice symétrique définie positive (
𝐻𝐻
souvent𝐻𝐻 �0 est une matrice identité ou diagonale → 𝐻𝐻 �0 = 𝐼𝐼 (Matrice identité ) ou
�0 = 𝛽𝛽𝐼𝐼 , 𝛽𝛽 > 0
𝐻𝐻
On prend comme 1er valeur 𝐻𝐻 �0 𝑑𝑑0 = −𝛻𝛻𝑓𝑓(𝑥𝑥0 )
Une fois 𝑑𝑑 𝑘𝑘 trouvé
𝑦𝑦𝑘𝑘 𝑦𝑦𝑘𝑘 𝑇𝑇 � 𝑘𝑘 𝑑𝑑𝑘𝑘 𝐻𝐻
𝐻𝐻 � 𝑘𝑘 𝑑𝑑𝑘𝑘 𝑇𝑇
�𝑘𝑘+1 =
On cherche𝐻𝐻 �𝑘𝑘 +
𝐻𝐻 −
𝑦𝑦𝑘𝑘 𝑑𝑑𝑘𝑘 𝑇𝑇 �𝑘𝑘 𝑑𝑑𝑘𝑘
𝑑𝑑𝑘𝑘 𝑇𝑇 𝐻𝐻
avec : 𝑦𝑦 𝑘𝑘 = 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘+1 − 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 18
Partie 1 : Optimisation
Exemple 4.5
Trouver le maximum de la fonction
𝑓𝑓 𝑥𝑥 = 100 − 10 − 𝑥𝑥1 2 − 5 − 𝑥𝑥2 2
a. Analytiquement
b. Méthode de Newton
c. Méthode de Quasi-Newton
𝑇𝑇
On prend comme point de départ 𝑥𝑥0 = 0 0
Techniques mathématiques en génie chimique
Slides préparées par : Mansour Tawk 19
Partie 1 : Optimisation
