Remerciez-le!

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

République Algérienne Démocratique et populaire Ministère de l’enseignement Sup

République Algérienne Démocratique et populaire Ministère de l’enseignement Supérieur et de la Recherche Scientifique Université 08 Mai 1945 Guelma Faculté de Mathématiques et Informatique Et Science de L a Matière Département de Mathématiques Polycopie de Cours Présentés aux Etudiants Licence Académique en mathématiques Option : Analyse Par Dr.Amel Berhail Intitulé Février 2016 Octobre 2016 Optimisation Sans Contraintes Optimisation sans Contraintes Dr. A. BERHAIL Page 1 Table des matières INTRODUCTION………………………………………………………...…………. .………… …03 Chapitre I : NOTIONS DE CONVEXITE 04 I.1. Ensembles convexe……………………………………………………………..……………….05 I.1.1. Opérations sur les ensembles convexes…………………………………..………………06 I.1.2. Enveloppe convexe…………………………………………………………..………...…06 I.1.3. Théorème de séparation……………………….…………………………..……………...09 I.2. Fonctions convexes………………………………………………………………..…………….11 I.2.1. Définitions et propriétés d’une fonction convexe ……………………………….…….….11 I.2.2.Continuité des fonctions convexes……………………………………...………………….12 I.2.3. Différentiabilité et fonctions convexes……………………………………...………….….13 I.2.4. Sous différentiel et fonctions convexes…………………………………………...….……13 I.2.5. Caractérisation des fonctions convexe………………………………………..…...………15 I.3. Exercices ………………………………………..…………………………..……………….……22 Chapitre II : OPTIMISATION SANS CONTRAINTES 24 II.1. Généralités………………………………………………………………..………………...…...24 II.2. Quelques exemples……………………………………………………………..…..………….. 26 II.3. Solution Optimale…………………………………………………………..………..……...…..28 II.4. Résultats d’existence et d’unicité……………………………………..…………………………28 II.5. Direction de descente ………………………………………………..………………………….32 II.6. Conditions d’optimalité ……………………………………………………………….…….. …33 II.6.1.Condition d’optimalité nécessaires du premier ordre ………………………….....………33 II.6.2.Condition d’optimalité nécessaires du deuxième ordre…………………………….…… 34 II.6.3.Condition d’optimalité suffisante du deuxième ordre ……………………………….……35 II.7.Exercices…………………………………………………………………...…………………..…38 Optimisation sans Contraintes Dr. A. BERHAIL Page 2 Chapitre III : METHODES ITERATIVES d’OPTIMISATION SANS CONTRAINTES 41 III.1. Notion d’algorithme………………………………………………………………………....…41 III.2. Modes de Convergence…………………………………………………………………..….…41 III.3. Schémas général des algorithmes d’optimalité………………………………….……………. 42 III. 4. Méthode de Gradient………………………………………………………………..………....43 III.4.1. Méthode de Gradient à pas optimal…………………...…………………………….…43 III.4.2. Méthode de Gradient à pas fixe…………………………...……………………..…….46 III.5. Méthode des gradients conjugués ………………………………………….…………….……49 III.6 . Méthode de Newton …………………………………..…………………………………… ..52 III.7. Méthode de Quasi-Newton …………………………………….……...……………………....56 III.8. Exercices……………………………………………………………..………….…………....57 Corrigées des exercices………………………………………………………………………………59 BIBLIOGRAPHIE……………………………………………….…………………………..……..69 Optimisation sans Contraintes Dr. A. BERHAIL Page 3 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. Elle est aussi un sujet très vaste qui touche aussi bien au calcul des variations qu'a la recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande. Aujourd'hui, tous les systèmes susceptibles d’être décrits par un modèle mathématique sont optimisés. La qualité des résultats et des prédictions dépend de la pertinence du modèle, de l’efficacité de l’algorithme et des moyens pour le traitement numérique. De façon générale, les techniques d'optimisations jouent un rôle de plus en plus important pour la conception des systèmes et des équipements de toute nature, et toutes les décisions technique ou économiques. Puisque les gens en général recherchent ce qu'il ya de meilleur et lorsque plusieurs possibilités se présentent, leur choix se porte tout naturellement vers la variante « optimal ». Ce mot provient du latin « optimum » qui veut dire meilleur et parfait. Euclide formulait déjà des problème d'optimisation au IIIème siècle avant J-C. Sir Isaac Newton (1642-1727), auteur du célèbre « Mathematical Principales of Natural Philosophy », ainsi que Gottfried Wilhelm Leibniz (1646-1716) offrirent, si c'est à l'antiquité que remonte les premiers problèmes de maximum et de minimum, on peut dire que c'est à la fin du dix-septième et au dix- huitième siècle qu'apparaissent les premières méthodes générales de solutions. Le développement de l'analyse mathématique en particulier le calcul différentiel (newton, Pappus), l'introduction de fonctionnelle (Euler, Lagrange) a permis à l'optimisation de jouer un rôle important dans le secteur des sciences exactes, ou la plupart des principes physiques peuvent s'énoncer sous forme variationnelle. Optimiser, c'est donner les meilleurs conditions de fonctionnement de rendement et d'un point de vue mathématique l'optimisation consiste à rechercher le minimum ou le maximum d'une fonction avec ou sans contraintes, cependant on limite souvent l'optimisation à une recherche de minimum. Plus précisément on cherche par exemple à caractériser le point qui réalise un minimum d'une fonction différentiable dans tous l'espace ou lorsque ce minimum est réalisé à l'intérieure de l'ensemble des contraintes. Optimisation sans Contraintes Dr. A. BERHAIL Page 4 Les problèmes considérés ici s'écrivent sous la forme standard suivant: optimiser le problème   n R x x f  ), ( où la fonction f est linéaire ou non ; donc pour choisir la possibilité optimal, on est amené à résoudre les problèmes de recherche d'un maximum ou d'un minimum qui sont appelés « Problèmes d'extrémums ». Dans ce cours, nous nous intéressons aux méthodes numériques pour l’optimisation continue, différentiable. Le premier chapitre traite des notions mathématiques fondamentales à maîtriser avant de s’intéresser à la résolution à proprement parler de tout problème d’optimisation : nous allons donner quelques définitions et concepts de la théorie convexe. Dans le deuxième chapitre, nous entrons dans le vif du sujet en nous intéressant à la résolution de problèmes d’optimisation sans contrainte, nous tenterons de répondre aux questions suivantes : Existe- t-il une solution du problème considéré ? si oui, a-t-on unicité ? Comment la caractériser ? (conditions d’optimalité). Enfin, dans le chapitre 3 ; nous donnerons quelques méthodes numériques pour la résolution des problèmes d’optimisation sans contraintes où on va répondre aux questions suivantes : Comment calculer la solution optimal? et quel type d’algorithme choisir ? Optimisation sans Contraintes Dr. A. BERHAIL Page 5 Chapitre I NOTIONS DE CONVEXITE En mathématiques, le mot « convexe » est utilisé dans la désignation de deux notions bien distinctes quoique apparentées : Lorsqu'il se rapporte à une forme géométrique, un ensemble de points, il renvoie au concept d'ensemble convexe. Lorsqu'il se rapporte à une fonction, il renvoie au concept de fonction convexe. En économie, la convexité est un indicateur de risque de taux directement lié au concept mathématique de fonction convexe. Dans la langue courante le mot « convexité » a un sens directement relié au concept mathématique d'ensemble convexe, la convexité d'un objet désignant la partie de celui-ci qui a une forme bombée. On retrouve ce même sens en optique géométrique, notamment pour qualifier des miroirs ou des lentilles. Dans ce chapitre nous introduisons la notion d'ensemble et fonction convexe, démontrons leurs principales propriétés géométriques et topologiques. I.1. Ensembles convexes Définition : Un ensemble S de Rn est dite convexe si :     . 1 , 1 , 0 , 2 1 2 , 1 S x x S x x           où bien . , 1 , , , 2 1 2 , 1 S x x R S x x                En d’autre terme, Un objet géométrique S est dit convexe lorsque, chaque fois qu'on y prend deux points x et y de S, le segment [x ,y] qui les joint est entièrement contenu dans S. Exemples : -Tout disque, ainsi un cube plein, une boule sont convexes. - La couronne n’est pas un ensemble convexe. Ainsi tous objet creux ne l'est pas. - Toutes partie affine est convexe car un ensemble S de Rn est dit affine si :   . 1 , , 2 1 2 , 1 S x x R S x x           - La partie de Rn définie par {x de Rn ; x positif} est un convexe appelé orthant positif. Convexe Non convexe Optimisation sans Contraintes Dr. A. BERHAIL Page 6 I.1.1. Opérations sur les ensembles convexes Proposition 1: 1-Soit ) , ( N I i Si   convexe de n R , alors ( i I i S   ) est un convexe mais ( i n i S , 1   ) n’est pas nécessairement un ensemble convexe. 2- Soit n R S  un ensemble convexe, alors S est un convexe. 3- Soit n R S  un ensemble convexe avec   ) int( S , alors ) int( S est un convexe. 4- La somme de deux convexes est un convexe. 5- Le produit d’un convexe avec un scalaire est un convexe. 6-L’image directe et l’image réciproque d’un convexe par une application linéaire est un convexe. Preuve : Exercices Combinaison convexe Définition : On appelle combinaison convexe d’un ‘n’ éléments n i R x  tout élément y de Rn s’écrit sous la forme: i i n i x y     1 avec les points . 1 0 1     i n i i et   I.1.2. Enveloppe convexe Définition : L’enveloppe convexe d’un ensemble n R S  d’éléments n i R x  est l’ensemble de toutes les combinaisons convexes des points n i R x  . C’est aussi le plus petit convexe contenant S qui est donc l’intersection de tous les convexes contenants S, on le note par H(S) ou Conv(S) :             n i i i i n i n n x uploads/Science et Technologie/ cours-optimisation-2017-5.pdf