Cours:
Techniques d’Optimisation en Ingénierie
Dr/Col. T. BOULKERAA
Techniques d’optimisation
Méthodes Déterministes
Deux raisons majeures pour lesquelles l'approche d'optimisation standard
directe est rarement utilisée dans la pratique :
• Les équations du point stationnaire ne peuvent souvent pas être résolues
explicitement (Limites de l'algèbre)
• étant donné qu'il existe une équation de point stationnaire pour chaque variable,
seulement les problèmes d'optimisation avec relativement peu de variables sont
pratiques (Limitations de taille).
nous nous concentrerons sur une classe de méthodes basées sur des
calculs familiers. La procédure de base pour une telle optimisation est
"basée sur les dérivées" est généralement exprimé comme suit :
1. Initialiser l'estimation actuelle (du vecteur de design regroupant les variables).
2. Mise à jour (déterminez une nouvelle estimation à partir de l'estimation actuelle).
3. Arrêter ou répéter (Si le critère d'arrêt n'est pas satisfait et que la progression est en cours,
utilisez la nouvelle estimation comme estimation actuelle et répétez le processus de l'étape 2.)
Fonctions de remplacement
les stratégies d'optimisation dites de calcul directe ne
peuvent pas être utilement appliqué à la plupart des
problèmes d'optimisation réels.
Une approche de base, utilisée en pratique, consiste à
remplacer la fonction objectif par une fonction plus
simple, qui ressemble à la fonction objectif proche de
l'estimation actuelle, et dont les points stationnaires sont
facilement trouvés.
Les valeur initiale successives sont guidées
par les fonctions de remplacement.
La clé de cette méthode sont les fonctions de remplacement.
Ils doivent être assez simples pour que leurs points fixes soient faciles à trouver
mais assez compliqués pour capturer les caractéristiques pertinentes des fonctions
d'origine.
Le plus simple des fonctions de remplacement qui satisfont ces exigences sont des
fonctions quadratiques.
Fonctions de remplacement
Fonctions quadratiques.
Toute fonction quadratique à deux variables x et y peut s'écrire:
Évidemment, les quadratiques simples satisfont au premier critère (calcul simples des
points stationnaires), il ne reste donc qu'à voir s'ils satisfont également au deuxième
critère (capturer les caractéristiques pertinentes des fonctions).
Fonctions de remplacement
Fonctions quadratiques.
Un choix qui satisfait le deuxième critère est la forme quadratique de Taylor
ഥ, 𝒚
associé à f au point de base (𝒙 ഥ) qui représente l'estimation courante :
Matrice Hessienne
Forme quadratique générale
2
3
Si le point de base est (1,2),
par exemple, alors les
dérivées partielles évaluées
en ce point sont :
3
Fonctions de remplacement
Fonctions quadratiques.
La méthode d'optimisation de Newton est une célèbre méthode d'optimisation
dont l'essence est de résoudre les équations (1) où les constantes sont données dans
(2), qui dans la forme matricielle est juste:
Rappel:
Matrice Inverse
Non nul
4
La mise à jour dans la méthode d'optimisation de Newton est définie en résolvant
l'équation de matricielle (4) pour la nouvelle estimation (xnew, ynew) = (x, y) en fonction de
ഥ, 𝒚
l'estimation actuelle (xold, yold) = (𝒙 ഥ), qui peut être exprimé de manière compacte avec une
notation matricielle:
Graphiquement, cette formule de mise à jour indique que le nouveau vecteur de design
est obtenu à partir de l'ancien par ajouter du vecteur :
N.B: La méthode. d'optimisation de Newton se terminera généralement à un point presque
stationnaire dont le gradient est proche du vecteur zéro.
En analyse numérique, la méthode de Newton ou méthode de Newton-Raphson est, dans
son application la plus simple, un algorithme efficace pour trouver numériquement une
approximation précise d'un zéro (ou racine) d'une fonction réelle d'une variable réelle.
Rempler F
Par F’
det(𝜆𝐼𝑛 − 𝐻) = 0
Polynôme caractéristique
𝑯
Hessienne du Lagrangien
définie positive
Techniques d’optimisation
Méthodes Déterministes
Les méthodes déterministes sont basées sur le concept de recherche
successive, généralement appelée recherche pas à pas, dans laquelle la fonction
objectif est évaluée et une décision est prise quant à la direction à suivre pour
atteindre une meilleure valeur de la fonction objectif sans violer les contraintes.
Cette direction d'amélioration locale maximale de la fonction objectif peut être
trouvée en utilisant des dérivées d'équations gouvernantes ou des méthodes de
différences finies (méthodes de recherche de gradient), et est appelée la direction
de la plus grande Descente. Après avoir déterminé la meilleure direction pour se
déplacer, un "pas" d'une certaine distance définie est effectué dans cette direction
jusqu'à un point qui devient l'origine du calcul et du pas suivants.
Les recherches pas à pas sont susceptibles de trouver un optimum local plutôt
que le « meilleur » global, en fonction de l'emplacement du point de départ. Une
façon d'éviter cela s'appelle le multi-start, dans lequel l'optimisation est réexécutée
plusieurs fois, à partir de différents points de départ.
Techniques d’optimisation
Méthodes Déterministes
La plupart des méthodes performantes mettent à jour le design par la relation:
X q1 X q Sq
XLe X q Sq est la modification du design à l'étape actuelle et q est le
q1 produit
numéro d'itération,
Sleq vecteur de conception, Sq est une direction du vecteur de recherche
1 X q est
X q
q Sqet est un paramètre de déplacement scalaire déterminant la quantité de
X q1 X
modification du vecteur design.
N.B: Les recherches pas à pas sont fréquemment utilisées en raison de leur
nature robuste et déterministe.
Optimization Techniques
Modified Method of Feasible Direction (MMFD)
Successive search using the gradient direction
Design modification to improve the objective function
X0
q q 1
F ( X q 1 ), g ( X q 1 )
Fletcher-Reeves
) S
q 1 q 1
S F ( X
q
q
S Search direction
X q X q -1 * S q Design modification
No Stopping
criterion
Steepest descent
q 1
S F ( X
q
)
44
Code: gradient_descent
Code: gradient_descent_3d algorithm
Exercice position du problème/Solution Graphique
Exemple LP
Une entreprise de meubles produit des chaises et des tables de bureau.
L'entreprise prévoit la demande d'au moins 100 chaises et 50 tables par
jour. L'entreprise ne peut produire plus de 120 chaises et 70 tables par
jour. L'entreprise doit expédier au plus 150 unités de chaises et de tables
par jour pour remplir le contrat d'expédition. Chaque table vendue génère
un bénéfice de 50 et chaque chaise génère un bénéfice de 15.
a) Combien d'unités de chaises et de tables faut-il fabriquer chaque jour
pour maximiser le profit ?
b) Calculez le profit maximal que l'entreprise peut réaliser en une journée ?
La solution
1- Définir d'abord les variables.
Le nombre de chaises vendues quotidiennement = x
Le nombre de tables vendues quotidiennement = y
L'équation s'écrira ainsi : P= 15x+ 50y
2- Définir les contraintes.
Il est indiqué dans le problème qu'il y a une demande projetée d'au moins 100 chaises
par jour et que l'entreprise ne peut pas produire plus de 150 chaises.
On écrira donc cette contrainte sous la forme d'une inégalité comme ceci :
100 ≤ x ≤ 150
Le problème indique qu'il existe une demande prévue pour au moins 50 tables par jour
et que l'entreprise ne peut pas produire plus de 70 tables.
On écrira donc cette contrainte sous la forme d'une inégalité comme ceci :
50 ≤ y ≤ 70
Pour satisfaire au contrat d'expédition, l'entreprise doit expédier au maximum 150
unités de chaises et de tables par jour.
Nous écrirons cette contrainte sous la forme :
x + y ≤ 150
Nous allons représenter graphiquement les inégalités suivantes dans un plan xy :
Solution graphique du LP
C1
C3
C2
Le profit maximum peut être calculé
en remplaçant x = 100 et y = 50 dans
l'équation suivante, P = 15x + 50y
P = 1500 + 2500 = 4000
