Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre 3 : Optimisation 1- Introduction : L'optimisation est une branche des

Chapitre 3 : Optimisation 1- Introduction : L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble. L'optimisation consiste en l’étude des problèmes qui s'expriment de la manière suivante : Étant donné une fonction R A f → : définie sur un ensemble A à valeurs dans l'ensemble R des nombres réels trouver un élément x de A tel que ( ) ( ) f x f x ≤ pour tous les x dans A On dit que l'on cherche à minimiser la fonction f sur l'ensemble A et on note : ( ) x f A x∈ inf ou ( ) { } A x x f ∈ / inf La fonction f est appelée sous différents noms : fonction-coût ou simplement coût, fonction- objectif ou simplement objectif, critère, etc. Le point x est appelé solution du problème d'optimisation (ou minimum). On l'appelle aussi parfois une solution globale pour le distinguer des solutions locales. On dit qu'il s'agit d'un minimum strict si l’élément A x ∈ et ( ) ( ) x f x f < pour tout { } x A x − ∈ Remarque : Le problème de minimisation peut être vu aussi comme un problème de maximisation en écrivant : ( ) ( ) ( ) x f x f A x A x − − = ∈ ∈ inf sup Les domaines d’application de l’optimisation sont très variés, on peut citer : optimisation d’un trajet, de la forme d’un objet, d’un prix de vente, d’une réaction chimique, du contrôle aérien, du rendement d’un appareil, du fonctionnement d'un moteur, de la gestion des lignes ferroviaires, du choix des investissements économiques, de la construction d’un navire, etc. 2- Types d’optimisation : Les problèmes d’optimisation se divisent en deux types: l’optimisation sans contrainte et l’optimisation avec contraintes. Dans les deux cas, le but consiste à trouver les valeurs qui maximisent ou minimisent une fonction. Toutefois, dans l’optimisation avec contraintes, les solutions sont soumises à des restrictions (contraintes). 1 3- Algorithmes d’optimisation : 3-1- Définition : Un algorithme d’optimisation est une procédure mathématique qui permet d’obtenir les minimums (ou maximums) d’une fonction réelle f .En général la solution recherchée est un sous-espace A⊂ Rn qui est soumis à un ensemble de contraintes (conditions sur les variables), qui sont exprimées comme un système d’équations et inéquations. Les éléments de A sont appelés solutions admissibles et possèdent souvent des bornes supérieures et inférieures A x x x u l ∈ ≤ ≤ Les algorithmes d’optimisation sont des processus itératifs que génèrent une séquence de valeurs 1 + n x à partir d’un point de départ 0 x . Un algorithme est convergent quand pour n’importe quel point de départ, la séquence arrive à la solution (maximum ou minimum). Les algorithmes d’optimisation ont besoin en général des dérivées de premier et deuxième degré de la fonction. Pour le calcul du gradient d’une fonction, on peut utiliser une approximation par exemple par les différences finies. 3-2- Catégories de problèmes résolus par les algorithmes d’optimisation : Les algorithmes d’optimisation s’utilisent en de nombreux problèmes : pour trouver les zéros de fonctions, pour minimiser la distance entre des points de mesure et une courbe (moindres carrés), intersections de fonctions et pour résoudre des systèmes d’équations à une ou plusieurs variables. En général, il n’y a pas de méthode idéale et ça dépend de la forme de la fonction à étudier et du type du problème à analyser. 3-3 Paramètres d’un algorithme d’optimisation 3-3-1. Approximation Initiale Pour initialiser l’algorithme, il est nécessaire d’avoir une approximation initiale 0 x de la solution (point de départ). Le choix d’une bonne approximation initiale détermine la convergence ou non à la solution. 3-3.2. Nombre d’Itérations Un algorithme d’optimisation utilise un processus récursif en calculant à chaque une nouvelle itération une nouvelle solution jusqu’à ce que le critère de convergence soit atteint. En résumé, c’est une boucle de répétition où la nouvelle solution est construite à partir des solutions antérieures. 3-3.3. Vitesse de convergence Quand on parle de convergence proche d’une solution, on parle de la vitesse à laquelle la solution à chaque itération approche de sa valeur finale. Le choix d’un algorithme avec une haute convergence est important pour les problèmes d’une certaine complexité ou avec de multiples paramètres. 3-3.4. Critère d’arrêt C’est un choix déterminé utilisé pour arrêter le processus de calcul. Il existe plusieurs critères d’arrêt. Les plus utilisées sont : a) Nombre maximal d’itérations Nmax 2 b) Comparaison d’une norme à une valeur très petite : ( ) ε < n x f c) Différence entre deus solutions successives : ε < − −1 n n x x en général la valeur de ε est prise très petite (de l’ordre de 10-4, 10-6, …). 4- Algorithmes sans contraintes : Il existe deux catégories d’algorithmes sans contraintes : a)- Les algorithmes déterministes : avec les mêmes données et les mêmes points de départ, ces algorithmes exécuteront toujours la même suite d'opérations et les solutions seront prévisibles. b)- Les algorithmes stochastiques : ce sont des algorithmes qui reposent sur des estimations aléatoires et qui doivent deviner à chaque itération quelle est la solution la plus adéquate. 4-1- L’algorithme de descente du gradient : L’algorithme de descente du gradient s'applique lorsqu’on cherche le minimum d'une fonction dont on connaît l'expression analytique, qui est dérivable, mais dont le calcul direct du minimum est difficile. L’algorithme de descente du gradient (à pas fixe) est résumé comme suit : tel que : ( ) ( ) ( ) ( ) ( )       ∂ ∂ ∂ ∂ ∂ ∂ = ∇ n k x x f x x f x x f x f ,...., , 2 1 et α est le pas de convergence. On peut améliorer la vitesse de convergence de l’algorithme en utilisant un pas variable. On aura alors l’algorithme de descente du gradient (à pas variable) qui est résumé comme suit : étape 1 : choisir un point de départ ( ) 0 0 x x = pour k =1, 2,….,N étape 2 : calculer ( ) ( ) ( ) 1 1 − − ∇ = k k x f g étape 3 : calculer ( ) ( ) ( ) 1 1 − −− = k k k g x x α finpour k étape 1 : choisir un point de départ ( ) 0 0 x x = pour k =1, 2,….,N étape 2 : calculer ( ) ( ) ( ) 1 1 − − ∇ = k k x f g étape 3 : calculer k k 1 = α étape 4 : calculer ( ) ( ) ( ) 1 1 − −− = k k k k g x x α finpour k 3 4-2- L’algorithme du gradient conjugué: L’algorithme du gradient conjugué est une version améliorée de l’algorithme de descente du gradient dans lequel on utilise deux gradients ( k d et k β ). Les étapes de cet algorithme sont résumées comme suit : 4-3- L’algorithme de Newton : Le principe de l’algorithme de Newton repose sur l’idée que la fonction f à minimiser est deux fois dérivables ce qui permet d’utiliser la deuxième dérivée pour construire la matrice hessienne H tel que : si on a l’expression du gradient ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) [ ] k n k k k x g x g x g x g ,...., , 2 1 = alors la matrice hessienne sera de la forme suivante : ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) =                         ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ ∂ = k n k n k k n k k n k n k k k k k k n k k k k k k x x g x x g x x g x x g x x g x x g x x g x x g x x g x H . . . . . . . . . . . . . . . . 2 1 2 2 2 1 2 1 2 1 1 1 Les étapes de cet algorithme sont résumées comme suit : Etape 1 : choisir un point de départ ( ) 0 0 x x = Etape 2 : calculer ( ) ( ) 0 0 uploads/Voyage/ chapitre-3.pdf