Un cours d'Optimisation pour les grands systèmes (par G. Cohen)

Sujets

• exercice
• cours
• mathématiques
• exercices
• mathématique
• cours de

Informations

• Publié par: Tidus
• Nombre de lectures: 227
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

´DEA Modelisation´ et Methodes´ Mathematiques´ en Economie Cours de DEA 2004 `OPTIMISATION DES GRANDS SYSTEMES Guy Cohen ´CERMICS Ecole Nationale des Ponts et Chaussees´ et INRIATable des Matier` es 1 Introduction 1 1.1 Sur les “Grands Systemes”` . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Tentative de caracterisation´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Quelques exemples typiques de grands systemes` . . . . . . . . . . . . . . . . . . . . . . 1 1.1.3 Idees´ et problematiques´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.4 Cadre du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Decomposition coordination´ en optimisation : gen´ eralit´ es´ . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Inter´ etˆ de l’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Avantages de la decomposition´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.3 Coordination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.4 Un exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Aperc ¸u du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Prerequis´ du cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Corrige´ des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5.1 Corrige´ de l’Exercice 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5.2e´ de l’Exercice 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5.3 Corrige´ de l’Exercice 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 ´ ´ ´ ´ ´2 Presentation elementaire des methodes de decomposition coordination 9 `2.1 Premier modele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 `2.1.1 Introduction du premier modele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 ´2.1.2 Decomposition “par les prix” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 ´ ´2.1.3 D “par les quantites” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 ´ ´2.1.4 D “par prediction” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.5 Une classification politico economique´ des methodes´ de decomposition coordination´ . . . 25 2.2 Deuxieme` modele` . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.1 Introduction du second modele` . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.2 Decomposition´ par les prix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.3 D´ par les quantites´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.4 D´ “par prediction”´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 `2.3 Annexe : A propos des series´ divergentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4 Annexe : Exercices sur la dualite´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.5 Corrige´ des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.5.1 Corrige´ de l’Exercice 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.5.2e´ de l’Exercice 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.5.3 Corrige´ de l’Exercice 2.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.5.4e´ de l’Exercice 2.13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5.5 Corrige´ de l’Exercice 2.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5.6e´ de l’Exercice 2.16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5.7 Corrige´ de l’Exercice 2.19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5.8e´ de l’Exercice 2.21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5.9 Corrige´ de l’Exercice 2.23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5.10e´ de l’Exercice 2.24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5.11 Corrige´ de l’Exercice 2.25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 i`ii OPTIMISATION DES GRANDS SYSTEMES — GUY COHEN 2.5.12 Corrige´ de l’Exercice 2.27 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.5.13e´ de l’Exercice 2.29 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.5.14 Corrige´ de l’Exercice 2.30 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.15e´ de l’Exercice 2.31 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.5.16 Corrige´ de l’Exercice 2.32 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3 Le Principe du Probleme` Auxiliaire 43 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2 Le Principe du Probleme` Auxiliaire en optimisation sur un ensemble admissible . . . . . . . . . . 44 3.2.1 Cadre gen´ eral´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2.2 Idee´ et algorithme de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2.3 Utilisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2.3.1 Algorithme “prox” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2.3.2 du gradient et du gradient projete´ . . . . . . . . . . . . . . . . . . 46 3.2.3.3 Algorithme de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2.3.4 Decomposition´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 ´3.2.4 Etude de la convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.4.1 Schema´ gen´ eral´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.4.2 Convergence de l’Algorithme 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.4.3 Un cas de convergence de toute la suite . . . . . . . . . . . . . . . . . . . . . . 53 J3.2.4.4 Vitesse de convergence dans le casJJ fortement convexe . . . . . . . . . . . . . 54 3.2.4.5 Quelques mots du cas sous differentiable´ . . . . . . . . . . . . . . . . . . . . . 55 3.2.5 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2.5.1 Augmentation de la fonction auxiliaire . . . . . . . . . . . . . . . . . . . . . . 55 3.2.5.2 Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.5.3 Version sequentielle´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 ´3.2.5.4 Linearisation partielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2.6 Une application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2.6.1 Expose´ du probleme` . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2.6.2 Approche “ad hoc” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.2.6.3 par le PPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3 Le Principe du Probleme` Auxiliaire en optimisation sous contraintes explicites . . . . . . . . . . 59 3.3.1 Le PPA et les problemes` de point selle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.3.2 Le PPA et la decomposition´ par les prix . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.3.2.1 Obtention de l’algorithme gen´ eral´ . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.3.2.2 Utilisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.3.2.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.3.3 Le PPA et la decomposition´ par prediction´ . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.3.3.1 Obtention de l’algorithme de point fixe . . . . . . . . . . . . . . . . . . . . . . 68 3.3.3.2 Utilisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3.3.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.3.3.4 Discussion de la condition geom´ etrique´ . . . . . . . . . . . . . . . . . . . . . . 72 3.3.3.5 Obtention de l’algorithme d’Arrow Hurwicz . . . . . . . . . . . . . . . . . . . 73 3.4 Annexe : Monotonie, forte monotonie et forte convexite´ . . . . . . . . . . . . . . . . . . . . . . . 76 3.5 Annexe : Propriet´ e´ de Lipschitz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.6 Annexe :et´ e´ de Dunn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.7 Annexe : Problemes` sous contraintes et dualite´ . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.7.1 Formulation et relation d’ordre dans un espace de Hilbert . . . . . . . . . . . . . . . . . . 80 3.7.2 Convexite´ et croissance en relation avec un coneˆ positif . . . . . . . . . . . . . . . . . . . 81 3.7.3 Coneˆ positif dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.7.4 Lagrangien et dualite´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.8 Corrige´ des exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.8.1 Corrige´ de l’Exercice 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.8.2e´ de l’Exercice 3.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 3.8.3 Corrige´ de l’Exercice 3.13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84`TABLE DES MATIERE