Ce document décrit diverses méthodes d'optimisation sans contraintes, notamment les méthodes analytiques, les méthodes de descente et les critères d'arrêt. De nombreuses méthodes numériques itératives sont présentées comme la méthode du gradient, la méthode de Newton, etc.
0 évaluation0% ont trouvé ce document utile (0 vote)
177 vues10 pages
Ce document décrit diverses méthodes d'optimisation sans contraintes, notamment les méthodes analytiques, les méthodes de descente et les critères d'arrêt. De nombreuses méthodes numériques itératives sont présentées comme la méthode du gradient, la méthode de Newton, etc.
Ce document décrit diverses méthodes d'optimisation sans contraintes, notamment les méthodes analytiques, les méthodes de descente et les critères d'arrêt. De nombreuses méthodes numériques itératives sont présentées comme la méthode du gradient, la méthode de Newton, etc.
Ce document décrit diverses méthodes d'optimisation sans contraintes, notamment les méthodes analytiques, les méthodes de descente et les critères d'arrêt. De nombreuses méthodes numériques itératives sont présentées comme la méthode du gradient, la méthode de Newton, etc.
Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
Télécharger au format pdf ou txt
Vous êtes sur la page 1/ 10
Cours d’optimisation M1 (AS et AII) N.
DJEGHALI Département Automatique UMMTO, 2021/2022
Chapitre 2. Optimisation sans contraintes : Méthodes locales
2.1 Introduction : Dans ce chapitre, nous allons étudier les méthodes de résolution d’un problème d’optimisation sans contraintes. Ces méthodes sont qualifiées de méthodes locales pour souligner le fait que le minimum (ou maximum) trouvé est local.
2.2 Méthodes d’optimisation
Les problèmes d’optimisation sans contraintes peuvent être résolus analytiquement ou avec des méthodes numériques itératives. Dans ce qui suit, nous étudions les méthodes permettant de résoudre un problème d’optimisation sans contraintes.
2.2.1 Méthode analytique
Considérons le problème d’optimisation suivant :
Min ou Max f ( x ) P: x∈Rn
où f : R n → R est une fonction donnée.
La méthode analytique est basée sur le calcul des points critiques et l’analyse de la matrice hessienne aux points critiques. Les étapes de cette méthode sont : a) Recherche des points critiques b) Pour chaque point critique x* : • Si ∇ 2 f ( x*) est définie positive (resp. négative) alors x* est un point de minimum (resp. point de maximum) local. • Si ∇ 2 f ( x*) est indéfinie alors x* est un point selle ou point col (x* n’est pas un point d’extremum). • Si ∇ 2 f ( x*) est semi-définie positive (resp. négative) alors on ne peut pas conclure. Exemple 2.1 : Déterminer les extrema de la fonction f ( x 1 , x 2 ) = x 12 + x 32 − 2 x 1 x 2 − x 2 Solution : a) Calcul des points critiques : Les points critiques sont les points qui annulent le gradient : ∂f ∂x 2 x − 2 x 2 0 ∇f ( x 1 , x 2 ) = 1 = 2 1 = ∂f 3x 2 − 2 x 1 − 1 0 ∂x 2
djeghalinadial2csp@gmail.com Chapitre 2. Optimisation sans contraintes : Méthodes locales N. DJEGHALI
−1 −1 ⇒ (x1 , x 2 ) = ( , ) et ( x1 , x 2 ) = (1,1) . 3 3 −1 −1 Donc on a deux points critiques : ( , ) et (1,1) . 3 3 b) Calcul de la matrice hessienne 2 −2 H ( x1 , x 2 ) = ∇ 2 f ( x1 , x 2 ) = − 2 6x 2
−1 −1 2 −2 • H( , )= 3 3 − 2 − 2
∆1 = 2 > 0 −1 −1 Les mineurs principaux de H( , ) sont : −1 −1 3 3 ∆ 2 = det(H( , )) = −8 < 0 3 3 −1 −1 −1 −1 On a n=2 (‘n’ est pair) et ∆ 2 <0 ⇒ H( , ) est indéfinie ⇒ ( , ) est un point selle. 3 3 3 3 2 −2 • H(1,1) = − 2 6 Les mineurs principaux de H (1,1) , sont : ∆1 = 2 > 0 ⇒ H(1,1) est définie positive ⇒ (1,1) est un point de minimum local. ∆ 2 = det(H(1,1)) = 8 > 0 La valeur de ce minimum local est donnée par : f (1,1) = −1. Remarque 2.1 : Ce minimum n’est pas global puisque par exemple f(0,-2)=-6<f(1,1).
2.2.2 Méthodes de descente (Méthodes numériques itératives)
Ces méthodes considèrent le problème de minimisation sans contraintes suivant : Min f ( x ) x∈Rn Quant à la recherche du maximum d’une fonction f(x), il revient à chercher le minimum de – f(x). • Notion de direction de descente : Soit f : R n → R et x ∈ R n , le vecteur d ∈ R n est une direction de descente pour f en x, s’il existe γ>0 tel que : f ( x + αd ) < f ( x ), ∀α ∈]0, γ ] .
2 Chapitre 2. Optimisation sans contraintes : Méthodes locales N. DJEGHALI
Les méthodes de descente sont des méthodes numériques qui permettent de trouver le minimum local d’une fonction en partant d’un point x 0 ∈ R n arbitrairement choisi. Les méthodes de descente génèrent une suite de points x 0 , x 1 , ......, x k , tel que :
∀ k ∈ N f ( x k +1 ) ≤ f ( x k )
Avec : x k +1 = x k + α k d k , α k > 0
Le vecteur d k est la direction de descente de f en x k , c'est-à-dire la direction dans laquelle la
valeur de f décroit. Le scalaire α k est appelé le pas de descente. Proposition 2.1: Soit d ∈ R n vérifiant ∇f ( x ) T d < 0 Alors ‘’d’’ est une direction de descente en x. Démonstration : On écrit le développement de Taylor de f ( x + αd ), α > 0 comme suit :
f ( x + αd ) = f ( x ) + α ∇f ( x ) T d + αε (α)
Avec lim ε(α ) = 0 .
α→0
Pour α suffisamment petit, on aura :
f ( x + αd ) − f ( x ) < 0 si ∇f ( x ) T d < 0 ⇒ d est une direction de descente. 2 Ainsi si on prend d= − ∇f ( x ) alors − ∇f ( x ) T ∇f ( x ) = − ∇f ( x ) < 0 .
• Méthodes de descente
a) Méthode du gradient à pas fixe (ou à pas constant)
A partir d’un point x 0 ∈ R n , on construit la suite des points suivante :
k=0,1,2,…..
x k +1 = x k − α∇f ( x k ) où la direction de descente est d k = −∇f ( x k ) α > 0 : est le pas de descente fixé a priori. b) Méthode du gradient à pas optimal Partant d’un point x 0 , l’algorithme du gradient à pas optimal est donné comme suit :
k=0,1,2,….. 1°. Calculer un pas optimal α k , solution de : Min f ( x k − α k ∇f ( x k ))
2°. x k +1 = x k − α k ∇f ( x k )
3 Chapitre 2. Optimisation sans contraintes : Méthodes locales N. DJEGHALI
Remarque 2.2: La méthode du gradient est également appelée méthode de la plus grande descente (ou pente). Remarque 2.3 : ( x k +1 − x k ) ⊥ ( x k − x k −1 ) . c) Méthode du gradient conjugué L’algorithme du gradient conjugué prend la forme suivante : On donne x 0 et on pose d 0 = −∇f ( x 0 ) k=0,1,2,….. 1°. Calculer un pas optimal α k , la solution de : Min f ( x k + α k d k )
2°. x k +1 = x k + α k d k 2 ∇f ( x k +1 ) 3°. B = k 2 ∇f ( x k )
4°. d k +1 = −∇f ( x k +1 ) + B k d k Remarque 2.4 : Cette méthode converge plus rapidement que la méthode du gradient. Remarque 2.5 : . est la norme euclidienne. Soit le vecteur [x 1 . . . x n ] , alors : T
n x = ∑x i =1 2 i
d) Méthode de Newton : Soit f : R n → R , f ∈ C 2 .
Le principe de la méthode de Newton est de calculer une approximation p(x) de f(x) autour d’un point xk par son développement de Taylor du second ordre, comme suit : 1 f ( x ) ≈ p( x ) = f ( x k ) + ( x − x k ) T ∇f ( x k ) + ( x − x k ) T ∇ 2 f ( x k )( x − x k ) 2 On calcule alors un nouveau point x k +1 qui minimise p(x), comme suit : ∇p( x ) = ∇f ( x k ) + ∇ 2 f ( x k )( x − x k ) = 0
Si la matrice hessienne ∇ 2 f ( x k ) est inversible alors :
x k +1 = x k − (∇ 2f ( x k )) −1 ∇f ( x k ) e) Méthode de Newton modifiée : L’algorithme de cette méthode est donné comme suit : Pour k=0,1,2,…… 1°. Calcul de α k , la solution de : Min f ( x k − α k (H ( x k )) −1 ∇f ( x k ))
2°. x k +1 = x k − α k (H ( x k )) −1 ∇f ( x k )
Avec H ( x k ) = ∇ 2 f ( x k ) .
4 Chapitre 2. Optimisation sans contraintes : Méthodes locales N. DJEGHALI
f) Méthode de Levenberg-Marquardt Cette méthode est la combinaison du gradient et Newton, l’algorithme de cette méthode est : Soit x 0 , v 0 , ∇f ( x 0 ) et H 0 ( x 0 )
Pour k=0,1,2,….. 1°. H k = H ( x k ) + v k I , avec v k : terme de régularisation tel que : H k > 0 2°. Si H k > 0 ⇒ v k = c 0 v k ⇒ 1° 3°. x k +1 = x k − α k (H k ) −1 ∇f ( x k ) 4°. Calculer f ( x k +1 ) 5°. Si f ( x k +1 ) ≥ f ( x k ) ⇒ v k = c1v k , x k +1 = x k ⇒ 1° vk Sinon v k +1 = c2 Avec c 0 , c1 , c3 > 1 et H ( x k ) = ∇ 2f ( x k ) .
g) Méthodes Quasi –Newton : Pour des problèmes de grandes dimensions, le calcul du
hessien et de son inverse sont trop coûteux, on peut alors utiliser des algorithmes dits quasi- Newton qui calculent une approximation Mk de (H ( x k )) −1 en fonction de Mk-1,
∇f ( x k ), ∇f ( x k −1 ), x k et x k −1 . On trouve notamment deux méthodes de calcul :
Méthode de Davidson-Flecher-Powell (DFP) Méthode de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
• Critères d’arrêt Un test d’arrêt devra être choisi pour garantir que les algorithmes s’arrêtent toujours après un nombre fini d’itérations et que le dernier point calculé soit suffisamment proche du point de minimum local de f. Soit ε > 0 la précision demandée. Plusieurs critères sont à notre disposition, on en distingue : 1. ∇f ( x k ) < ε (Ce critère vient des conditions nécessaires d’optimalité du 1er ordre)
2. x k +1 − x k < ε (Stagnation de la solution)
Donc l’un des critères ci-dessus peut être utilisé.
Exemple 2.2 : Déterminer le minimum de la fonction suivante en utilisant la méthode du gradient à pas optimal, la méthode du gradient conjugué et la méthode du Newton.
x 22 f ( x1 , x 2 ) = x 12 + − 3( x 1 + x 2 ) 2 On donne le point initial : x 0 = [ x10 x 02 ]T = [3 2] . Le critère d’arrêt est donné comme suit : T
5 Chapitre 2. Optimisation sans contraintes : Méthodes locales N. DJEGHALI
∇f ( x k ) ≤ ε avec ε = 10 −2 .
Solution: a) Par la méthode du gradient à pas optimal 2x − 3 3 ∇f ( x ) = ∇f ( x1 , x 2 ) = 1 ; x 0 = [ x10 x 02 ]T = [3 2] ; ∇f ( x 0 ) = ∇f ( x10 , x 02 ) = T
x2 − 3 − 1 Itération 1 : k=0 1°. Calculer un pas optimal α 0 > 0, solution de : Min f ( x 0 − α 0∇f ( x 0 )) 3 0 3 3 − 3α 0 x − α ∇f ( x ) = − α = 0 0 0 0 2 − 1 2 + α (2 + α 0 ) 2 f ( x 0 − α 0∇f ( x 0 )) = f (3 − 3α 0 ,2 + α 0 ) = (3 − 3α 0 ) 2 + − 3(5 − 2α 0 ) 2 19 02 D’où : f ( x 0 − α 0∇f ( x 0 )) = α − 10α 0 − 4 2 ∂f ( x 0 − α 0∇f ( x 0 )) 10 = 19α 0 − 10 = 0 ⇒ α 0 = = 0.5263 ∂α 0 19 ∂ 2 f ( x 0 − α 0∇f ( x 0 )) α 0 = 0.5263 est un point de minimum parce que = 19 > 0 ∂ 2α 0 3 − 3α 0 1.4211 x11 2°. x = x − α ∇f ( x ) = 1 0 0 0 0 = = 1 2 + α 2.5263 x 2 2 x11 − 3 − 0.1578 ∇f ( x ) = 1 1 = x 2 − 3 − 0.4737
1.5 ∇f ( x 2 ) = 0 < ε ⇒ x 2 = est le point de minimum de f. 3 Avec la méthode du gradient conjugué, le minimum de f est atteint en deux itérations.
c) Par la méthode de Newton
2x1 − 3 On a : ∇f ( x ) = ∇f ( x1 , x 2 ) = ; x 0 = [3 2] ; T x2 − 3 3 2 0 ∇f ( x 0 ) = ∇f ( x 10 , x 02 ) = ; ∇ 2 f ( x ) = ∇ 2 f ( x 1 , x 2 ) = − 1 0 1
9 Chapitre 2. Optimisation sans contraintes : Méthodes locales N. DJEGHALI
Itération 1 : k=0
x1 = x 0 − (∇ 2 f ( x 0 )) −1 ∇f ( x 0 )
3 2 0 0.5 0 On a ∇f ( x 0 ) = , ∇ 2 f ( x 0 ) = , (∇ 2 f ( x 0 )) −1 = − 1 0 1 0 1 3 0.5 0 3 1.5 x1 = x 0 − (∇ 2 f ( x 0 )) −1 ∇f ( x 0 ) = − = 2 0 1 − 1 3 0 ∇f ( x 1 ) = 0 1.5 ∇f ( x1 ) = 0 < ε ⇒ x1 = est le point de minimum de f. Min f = f ( x1 ) = −6.75. 3 On constate qu’avec la méthode de Newton, le minimum de f est obtenu en une seule itération. 2.3 Méthodes de recherche unidimensionnelle On s’intéresse dans cette partie à l’optimisation de fonctions monovariables (fonctions d’une seule variable). Plusieurs méthodes ont été proposées, on en distingue : a) Méthode analytique: Soit x* le point critique de f ( f ′( x*) = 0 ).
• si f ′′( x*) > 0 alors est x* est un point de minimum local
• si f ′′( x*) < 0 alors est x* est un point de maximum local
• si f ′′( x*) = 0 alors x* peut être est un point d’inflexion b) Méthode de dichotomie : Soit f une fonction unimodale. La première étape consiste en la a+b recherche de a et b tels que f ′(a ) < 0 et f ′(b) > 0 . Après cette étape, on pose x = . Si 2 f ′( x ) > 0 , on remplace b par x, sinon on remplace a par x. on répète l’opération jusqu’à b − a < ε. Remarque 2.6: On dit qu’une fonction est unimodale s’il existe un réel x* pour lequel la fonction est strictement décroissante sur ] − ∞, x*] et strictement croissante sur [ x*,+∞[. c) Méthodes de descente : Les méthodes de descente présentées précédemment peuvent être utilisées dans le cas d’une fonction monovariable.
