EDP Sciences 1775774411 20260409 fre

laboutique.edpsciences.fr-002180 03 01 01 002180 03 9782759827688 15 9782759827688 00 BA 02 16 mm 01 24 mm 10 01 02 PROfil Les ouvrages de la collection « PROfil » ont pour vocation la transmission des savoirs professionnels dans différentes disciplines. Ils sont rédigés par des experts reconnus dans leurs domaines et contribuent à la formation et l'information des professionnels. 01 01 Techniques d’optimisation Tome 1 Optimisation continue 1 A01 01 A2081 Max Cerf Cerf, Max Max Cerf Max CERF est ingénieur à Ariane Group depuis 1990. Ses activités portent sur l’optimisation des trajectoires et véhicules de transport spatial. Ancien élève de l’Ecole Centrale de Paris (1989), il est titulaire d’une habilitation à diriger des recherches (2019) et exerce des fonctions d’enseignement à l’université. Il a reçu le grade de Chevalier de l’Ordre National du Mérite (2015). Max CERF is an expert engineer in mission analysis at Ariane Group. His activities focus on the optimization of space vehicles and their trajectories. He also teaches at engineering schools and universities. 01 fre 00 484 03 02 24 Izibook:Subject Mathématiques 24 Izibook:Subject Informatique 24 Izibook:Subject Ingénierie 24 Izibook:Subject Sustainable Development Goals (SDG) 24 Izibook:SubjectAndCategoryAndTags |Mathématiques| 24 Izibook:SubjectAndCategoryAndTags |Informatique| 24 Izibook:SubjectAndCategoryAndTags |Ingénierie| 24 Izibook:SubjectAndCategoryAndTags |Sustainable Development Goals (SDG)| 20 optimisation;optimisation mathématique;mathématiques;optimisation continue;algorithme 10 2011 MAT003000 01 510 06 06 05 03 00 <blockquote style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">Cet ouvrage en deux tomes propose un panorama des techniques d’optimisation continue, discrète et fonctionnelle. Ce premier tome est consacré à l’optimisation continue qui traite des problèmes à variables réelles, sans ou avec contraintes. Après des rappels sur les conditions d’optimalité et leur interprétation géométrique, les thèmes abordés sont : <span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes sans gradient qui peuvent s’appliquer à tout type de fonction ; <span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes sans contraintes basés sur des méthodes de descente de type Newton ; <span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes avec contraintes : méthodes de pénalisation, primales, duales et primales-duales ; <span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• la programmation linéaire avec la méthode du simplexe et les méthodes de point intérieur. <span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">L’accent est mis sur la compréhension des principes plutôt que sur la rigueur mathématique. Chaque notion ou algorithme est accompagné d’un exemple détaillé aidant à s’approprier les idées principales. Cet ouvrage issu de 30 années d’expérience s’adresse aux étudiants, chercheurs et ingénieurs désireux d’acquérir une culture générale dans le domaine de l’optimisation. </blockquote><blockquote style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging">Ce livre fait partie de la sélection finale du « Prix Roberval 2023 » dans la catégorie «Enseignement supérieur ».</blockquote> <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">Cet ouvrage en deux tomes proposeun panorama des techniques d’optimisation continue, discrète et fonctionnelle.Ce premier tome est consacré à l’optimisation continue qui traite des problèmesà variables réelles, sans ou avec contraintes. Après des rappels sur lesconditions d’optimalité et leur interprétation géométrique, les thèmes abordéssont : <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes sansgradient qui peuvent s’appliquer à tout type de fonction ; <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes sanscontraintes basés sur des méthodes de descente de type Newton ; <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes aveccontraintes : méthodes de pénalisation, primales, duales et primales-duales ; <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• la programmation linéaireavec la méthode du simplexe et les méthodes de point intérieur. <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">L’accent est mis sur lacompréhension des principes plutôt que sur la rigueur mathématique. Chaquenotion ou algorithme est accompagné d’un exemple détaillé aidant à s’approprierles idées principales. Cet ouvrage issu de 30 années d’expérience s’adresse auxétudiants, chercheurs et ingénieurs désireux d’acquérir une culture généraledans le domaine de l’optimisation.  02 00 Cet ouvrage en deux tomes propose un panorama des techniques d’optimisation continue, discrète et fonctionnelle. Ce premier tome est consacré à l’optimisation continue qui traite des problèmes à variables réelles, sans ou avec contraintes. 04 00 1. Optimisation continue 1<o:p></o:p>1.1 Formulation 2<o:p></o:p>1.1.1 Forme standard 2<o:p></o:p>1.1.2 Fonction de plusieurs variables 3<o:p></o:p>1.1.3 Lignes de niveau 5<o:p></o:p>1.1.4 Direction de descente 6<o:p></o:p>1.1.5 Variation directionnelle 7<o:p></o:p>1.1.6 Solution 10<o:p></o:p>1.2 Dérivées numériques 14<o:p></o:p>1.2.1 Dérivées premières 15<o:p></o:p>1.2.2 Dérivées secondes 15<o:p></o:p>1.2.3 Réglage de l’incrément 16<o:p></o:p>1.2.4 Dérivée complexe 19<o:p></o:p>1.2.5 Dérivées par extrapolation 20<o:p></o:p>1.3 Réduction du problème 25<o:p></o:p>1.3.1 Réduction linéaire 25<o:p></o:p>1.3.2 Réduction généralisée 31<o:p></o:p>1.4 Optimum global 37<o:p></o:p>1.4.1 Problème dual 37<o:p></o:p>1.4.2 Point-selle 40<o:p></o:p>1.4.3 Programmation linéaire 45<o:p></o:p>1.5 Optimum local 49<o:p></o:p>1.5.1 Directions admissibles 49<o:p></o:p>1.5.2 Conditions de Karush, Kuhn etTucker 54<o:p></o:p>1.5.3 Interprétation géométrique 70<o:p></o:p>1.5.4 Problème linéaire-quadratique 76<o:p></o:p>1.5.5 Analyse de sensibilité 77<o:p></o:p>1.6 Conclusion 82<o:p></o:p>1.6.1 Les points essentiels 82<o:p></o:p>1.6.2 Pour aller plus loin 82<o:p></o:p>2. Optimisation sans gradient 85<o:p></o:p>2.1 Optimisation difficile 86<o:p></o:p>2.1.1 Variables discrètes 86<o:p></o:p>2.1.2 Minima locaux 88<o:p></o:p>2.1.3 Méthodes locales et globales 93<o:p></o:p>2.2 Optimisation unidimensionnelle 96<o:p></o:p>2.2.1 Partage d’intervalles 96<o:p></o:p>2.2.2 Positionnement des points 97<o:p></o:p>2.2.3 Méthode du nombre d’or 99<o:p></o:p>2.2.4 Interpolation quadratique 102<o:p></o:p>2.3 Méthode DIRECT 105<o:p></o:p>2.3.1 Fonction lipschitzienne 105<o:p></o:p>2.3.2 Algorithme en dimension 1 107<o:p></o:p>2.3.3 Algorithme en dimension n 118<o:p></o:p>2.4 Méthode de Nelder-Mead 131<o:p></o:p>2.4.1 Polytope 131<o:p></o:p>2.4.2 Nouveau point 134<o:p></o:p>2.4.3 Améliorations 136<o:p></o:p>2.5 Affine shaker 140<o:p></o:p>2.5.1 Principe 140<o:p></o:p>2.5.2 Transformation affine 142<o:p></o:p>2.5.3 Algorithme 144<o:p></o:p>2.6 CMAES 146<o:p></o:p>2.6.1 Principe 146<o:p></o:p>2.6.2 Adaptation de la covariance 147<o:p></o:p>2.6.3 Algorithme 150<o:p></o:p>2.7 Recuit simulé 153<o:p></o:p>2.7.1 Principe 153<o:p></o:p>2.7.2 Probabilité de transition 154<o:p></o:p>2.7.3 Algorithme 155<o:p></o:p>2.8 Recherche avec tabou 161<o:p></o:p>2.8.1 Principe 161<o:p></o:p>2.8.2 Liste taboue et voisinage 161<o:p></o:p>2.8.3 Affectation quadratique 163<o:p></o:p>2.9 Essaims de particules 171<o:p></o:p>2.9.1 Principe 171<o:p></o:p>2.9.2 Déplacement des particules 171<o:p></o:p>2.9.3 Voisinage 173<o:p></o:p>2.9.4 Algorithme 174<o:p></o:p>2.10 Colonies de fourmis 176<o:p></o:p>2.10.1 Principe 176<o:p></o:p>2.10.2 Mouvement des fourmis 177<o:p></o:p>2.10.3 Problème du voyageur de commerce177<o:p></o:p>2.11 Algorithmes évolutionnaires 179<o:p></o:p>2.11.1 Principe 179<o:p></o:p>2.11.2 Mécanismes d’évolution 180<o:p></o:p>2.11.3 Algorithme 181<o:p></o:p>2.12 Conclusion 186<o:p></o:p>2.12.1 Les points essentiels 186<o:p></o:p>2.12.2 Pour aller plus loin 186<o:p></o:p>3. Optimisation sans contraintes 189<o:p></o:p>3.1 Méthode de Newton 190<o:p></o:p>3.1.1 Système d’équations 190<o:p></o:p>3.1.2 Méthode d’homotopie 196<o:p></o:p>3.1.3 Minimisation 204<o:p></o:p>3.1.4 Moindres carrés 207<o:p></o:p>3.2 Méthodes de quasi-Newton 213<o:p></o:p>3.2.1 Méthode de Broyden 213<o:p></o:p>3.2.2 Méthodes DFP, BFGS et SR1 217<o:p></o:p>3.2.3 Améliorations BFGS 227<o:p></o:p>3.3 Recherche linéaire 231<o:p></o:p>3.3.1 Direction de descente 232<o:p></o:p>3.3.2 Pas de déplacement 248<o:p></o:p>3.3.3 Algorithme 251<o:p></o:p>3.4 Région de confiance 256<o:p></o:p>3.4.1 Modèle quadratique 257<o:p></o:p>3.4.2 Solution directe 259<o:p></o:p>3.4.3 Solution dogleg 261<o:p></o:p>3.4.4 Algorithme 265<o:p></o:p>3.5 Méthodes proximales 268<o:p></o:p>3.5.1 Opérateur proximal 268<o:p></o:p>3.5.2 Interprétations 272<o:p></o:p>3.5.3 Gradient proximal 275<o:p></o:p>3.5.4 Méthode primale-duale 278<o:p></o:p>3.5.5 Calcul de l’opérateur proximal 280<o:p></o:p>3.6 Convergence 284<o:p></o:p>3.6.1 Convergence globale 284<o:p></o:p>3.6.2 Vitesse de convergence 286<o:p></o:p>3.6.3 Précision numérique 290<o:p></o:p>3.7 Conclusion 292<o:p></o:p>3.7.1 Les points essentiels 292<o:p></o:p>3.7.2 Pour aller plus loin 292<o:p></o:p>4. Optimisation avec contraintes 295<o:p></o:p>4.1 Classification des méthodes 296<o:p></o:p>4.1.1 Formulations du problème 296<o:p></o:p>4.1.2 Méthodes primales, primales-dualeset duales 298<o:p></o:p>4.1.3 Mesure de l’amélioration 301<o:p></o:p>4.2 Pénalisation 308<o:p></o:p>4.2.1 Problème pénalisé 308<o:p></o:p>4.2.2 Pénalisation différentiable 311<o:p></o:p>4.2.3 Pénalisation exacte 312<o:p></o:p>4.2.4 Pénalisation quadratique 315<o:p></o:p>4.2.5 Pénalisation barrière 322<o:p></o:p>4.3 Gradient réduit 323<o:p></o:p>4.3.1 Déplacement dans l’espace tangent323<o:p></o:p>4.3.2 Déplacement de restauration 330<o:p></o:p>4.3.3 Recherche linéaire 332<o:p></o:p>4.3.4 Méthode de quasi-Newton 336<o:p></o:p>4.3.5 Algorithme 337<o:p></o:p>4.4 Programmation quadratique séquentielle 341<o:p></o:p>4.4.1 Modèle quadratique local 341<o:p></o:p>4.4.2 Globalisation 347<o:p></o:p>4.4.3 Gestion des contraintes 352<o:p></o:p>4.4.4 Méthode de quasi-Newton 356<o:p></o:p>4.4.5 Algorithme 358<o:p></o:p>4.5 Point intérieur 362<o:p></o:p>4.5.1 Problème barrière 362<o:p></o:p>4.5.2 Globalisation 365<o:p></o:p>4.5.3 Hauteur de barrière 366<o:p></o:p>4.6 Lagrangien augmenté 367<o:p></o:p>4.6.1 Problème dual 367<o:p></o:p>4.6.2 Problème dual augmenté 371<o:p></o:p>4.6.3 Contraintes inégalité 375<o:p></o:p>4.6.4 Algorithme 377<o:p></o:p>4.7 Conclusion 381<o:p></o:p>4.7.1 Les points essentiels 381<o:p></o:p>4.7.2 Pour aller plus loin 381<o:p></o:p>5.Programmation linéaire 383<o:p></o:p>5.1 Simplexe 384<o:p></o:p>5.1.1 Forme standard 384<o:p></o:p>5.1.2 Base 387<o:p></o:p>5.1.3 Pivotage 398<o:p></o:p>5.1.4 Tableau du simplexe 404<o:p></o:p>5.1.5 Problème auxiliaire 410<o:p></o:p>5.1.6 Méthode des deux phases 415<o:p></o:p>5.1.7 Simplexe révisé 422<o:p></o:p>5.1.8 Simplexe dual 423<o:p></o:p>5.1.9 Simplexe complémentaire 430<o:p></o:p>5.2 Point intérieur 436<o:p></o:p>5.2.1 Chemin central 436<o:p></o:p>5.2.2 Direction de déplacement 443<o:p></o:p>5.2.3 Pas de déplacement 448<o:p></o:p>5.2.4 Algorithme deprédiction-correction 455<o:p></o:p>5.2.5 Extensions 458<o:p></o:p>5.3 Conclusion 460<o:p></o:p>5.3.1 Les points essentiels 460<o:p></o:p>5.3.2 Pour aller plus loin 461<o:p></o:p>Index<o:p></o:p>Bibliographie<o:p></o:p> 1. Optimisationcontinue 1<o:p></o:p>1.1 Formulation 2<o:p></o:p>1.1.1 Forme standard 2<o:p></o:p>1.1.2 Fonction de plusieurs variables 3<o:p></o:p>1.1.3 Lignes de niveau 5<o:p></o:p>1.1.4 Direction de descente 6<o:p></o:p>1.1.5 Variation directionnelle 7<o:p></o:p>1.1.6 Solution 10<o:p></o:p>1.2 Dérivées numériques 14<o:p></o:p>1.2.1 Dérivées premières 15<o:p></o:p>1.2.2 Dérivées secondes 15<o:p></o:p>1.2.3 Réglage de l’incrément 16<o:p></o:p>1.2.4 Dérivée complexe 19<o:p></o:p>1.2.5 Dérivées par extrapolation 20<o:p></o:p>1.3 Réduction du problème 25<o:p></o:p>1.3.1 Réduction linéaire 25<o:p></o:p>1.3.2 Réduction généralisée 31<o:p></o:p>1.4 Optimum global 37<o:p></o:p>1.4.1 Problème dual 37<o:p></o:p>1.4.2 Point-selle 40<o:p></o:p>1.4.3 Programmation linéaire 45<o:p></o:p>1.5 Optimum local 49<o:p></o:p>1.5.1 Directions admissibles 49<o:p></o:p>1.5.2 Conditions de Karush, Kuhn etTucker 54<o:p></o:p>1.5.3 Interprétation géométrique 70<o:p></o:p>1.5.4 Problème linéaire-quadratique 76<o:p></o:p>1.5.5 Analyse de sensibilité 77<o:p></o:p>1.6 Conclusion 82<o:p></o:p>1.6.1 Les points essentiels 82<o:p></o:p>1.6.2 Pour aller plus loin 82<o:p></o:p>2. Optimisationsans gradient 85<o:p></o:p>2.1 Optimisation difficile 86<o:p></o:p>2.1.1 Variables discrètes 86<o:p></o:p>2.1.2 Minima locaux 88<o:p></o:p>2.1.3 Méthodes locales et globales 93<o:p></o:p>2.2 Optimisation unidimensionnelle 96<o:p></o:p>2.2.1 Partage d’intervalles 96<o:p></o:p>2.2.2 Positionnement des points 97<o:p></o:p>2.2.3 Méthode du nombre d’or 99<o:p></o:p>2.2.4 Interpolation quadratique 102<o:p></o:p>2.3 Méthode DIRECT 105<o:p></o:p>2.3.1 Fonction lipschitzienne 105<o:p></o:p>2.3.2 Algorithme en dimension 1 107<o:p></o:p>2.3.3 Algorithme en dimension n 118<o:p></o:p>2.4 Méthode de Nelder-Mead 131<o:p></o:p>2.4.1 Polytope 131<o:p></o:p>2.4.2 Nouveau point 134<o:p></o:p>2.4.3 Améliorations 136<o:p></o:p>2.5 Affine shaker 140<o:p></o:p>2.5.1 Principe 140<o:p></o:p>2.5.2 Transformation affine 142<o:p></o:p>2.5.3 Algorithme 144<o:p></o:p>2.6 CMAES 146<o:p></o:p>2.6.1 Principe 146<o:p></o:p>2.6.2 Adaptation de la covariance 147<o:p></o:p>2.6.3 Algorithme 150<o:p></o:p>2.7 Recuit simulé 153<o:p></o:p>2.7.1 Principe 153<o:p></o:p>2.7.2 Probabilité de transition 154<o:p></o:p>2.7.3 Algorithme 155<o:p></o:p>2.8 Recherche avec tabou 161<o:p></o:p>2.8.1 Principe 161<o:p></o:p>2.8.2 Liste taboue et voisinage 161<o:p></o:p>2.8.3 Affectation quadratique 163<o:p></o:p>2.9 Essaims de particules 171<o:p></o:p>2.9.1 Principe 171<o:p></o:p>2.9.2 Déplacement des particules 171<o:p></o:p>2.9.3 Voisinage 173<o:p></o:p>2.9.4 Algorithme 174<o:p></o:p>2.10 Colonies de fourmis 176<o:p></o:p>2.10.1 Principe 176<o:p></o:p>2.10.2 Mouvement des fourmis 177<o:p></o:p>2.10.3 Problème du voyageur de commerce177<o:p></o:p>2.11 Algorithmes évolutionnaires 179<o:p></o:p>2.11.1 Principe 179<o:p></o:p>2.11.2 Mécanismes d’évolution 180<o:p></o:p>2.11.3 Algorithme 181<o:p></o:p>2.12 Conclusion 186<o:p></o:p>2.12.1 Les points essentiels 186<o:p></o:p>2.12.2 Pour aller plus loin 186<o:p></o:p>3. Optimisationsans contraintes 189<o:p></o:p>3.1 Méthode de Newton 190<o:p></o:p>3.1.1 Système d’équations 190<o:p></o:p>3.1.2 Méthode d’homotopie 196<o:p></o:p>3.1.3 Minimisation 204<o:p></o:p>3.1.4 Moindres carrés 207<o:p></o:p>3.2 Méthodes de quasi-Newton 213<o:p></o:p>3.2.1 Méthode de Broyden 213<o:p></o:p>3.2.2 Méthodes DFP, BFGS et SR1 217<o:p></o:p>3.2.3 Améliorations BFGS 227<o:p></o:p>3.3 Recherche linéaire 231<o:p></o:p>3.3.1 Direction de descente 232<o:p></o:p>3.3.2 Pas de déplacement 248<o:p></o:p>3.3.3 Algorithme 251<o:p></o:p>3.4 Région de confiance 256<o:p></o:p>3.4.1 Modèle quadratique 257<o:p></o:p>3.4.2 Solution directe 259<o:p></o:p>3.4.3 Solution dogleg 261<o:p></o:p>3.4.4 Algorithme 265<o:p></o:p>3.5 Méthodes proximales 268<o:p></o:p>3.5.1 Opérateur proximal 268<o:p></o:p>3.5.2 Interprétations 272<o:p></o:p>3.5.3 Gradient proximal 275<o:p></o:p>3.5.4 Méthode primale-duale 278<o:p></o:p>3.5.5 Calcul de l’opérateur proximal 280<o:p></o:p>3.6 Convergence 284<o:p></o:p>3.6.1 Convergence globale 284<o:p></o:p>3.6.2 Vitesse de convergence 286<o:p></o:p>3.6.3 Précision numérique 290<o:p></o:p>3.7 Conclusion 292<o:p></o:p>3.7.1 Les points essentiels 292<o:p></o:p>3.7.2 Pour aller plus loin 292<o:p></o:p>4. Optimisationavec contraintes 295<o:p></o:p>4.1 Classification des méthodes 296<o:p></o:p>4.1.1 Formulations du problème 296<o:p></o:p>4.1.2 Méthodes primales, primales-dualeset duales 298<o:p></o:p>4.1.3 Mesure de l’amélioration 301<o:p></o:p>4.2 Pénalisation 308<o:p></o:p>4.2.1 Problème pénalisé 308<o:p></o:p>4.2.2 Pénalisation différentiable 311<o:p></o:p>4.2.3 Pénalisation exacte 312<o:p></o:p>4.2.4 Pénalisation quadratique 315<o:p></o:p>4.2.5 Pénalisation barrière 322<o:p></o:p>4.3 Gradient réduit 323<o:p></o:p>4.3.1 Déplacement dans l’espace tangent323<o:p></o:p>4.3.2 Déplacement de restauration 330<o:p></o:p>4.3.3 Recherche linéaire 332<o:p></o:p>4.3.4 Méthode de quasi-Newton 336<o:p></o:p>4.3.5 Algorithme 337<o:p></o:p>4.4 Programmation quadratiqueséquentielle 341<o:p></o:p>4.4.1 Modèle quadratique local 341<o:p></o:p>4.4.2 Globalisation 347<o:p></o:p>4.4.3 Gestion des contraintes 352<o:p></o:p>4.4.4 Méthode de quasi-Newton 356<o:p></o:p>4.4.5 Algorithme 358<o:p></o:p>4.5 Point intérieur 362<o:p></o:p>4.5.1 Problème barrière 362<o:p></o:p>4.5.2 Globalisation 365<o:p></o:p>4.5.3 Hauteur de barrière 366<o:p></o:p>4.6 Lagrangien augmenté 367<o:p></o:p>4.6.1 Problème dual 367<o:p></o:p>4.6.2 Problème dual augmenté 371<o:p></o:p>4.6.3 Contraintes inégalité 375<o:p></o:p>4.6.4 Algorithme 377<o:p></o:p>4.7 Conclusion 381<o:p></o:p>4.7.1 Les points essentiels 381<o:p></o:p>4.7.2 Pour aller plus loin 381<o:p></o:p>5.Programmation linéaire 383<o:p></o:p>5.1 Simplexe 384<o:p></o:p>5.1.1 Forme standard 384<o:p></o:p>5.1.2 Base 387<o:p></o:p>5.1.3 Pivotage 398<o:p></o:p>5.1.4 Tableau du simplexe 404<o:p></o:p>5.1.5 Problème auxiliaire 410<o:p></o:p>5.1.6 Méthode des deux phases 415<o:p></o:p>5.1.7 Simplexe révisé 422<o:p></o:p>5.1.8 Simplexe dual 423<o:p></o:p>5.1.9 Simplexe complémentaire 430<o:p></o:p>5.2 Point intérieur 436<o:p></o:p>5.2.1 Chemin central 436<o:p></o:p>5.2.2 Direction de déplacement 443<o:p></o:p>5.2.3 Pas de déplacement 448<o:p></o:p>5.2.4 Algorithme deprédiction-correction 455<o:p></o:p>5.2.5 Extensions 458<o:p></o:p>5.3 Conclusion 460<o:p></o:p>5.3.1 Les points essentiels 460<o:p></o:p>5.3.2 Pour aller plus loin 461<o:p></o:p>Index<o:p></o:p>Bibliographie<o:p></o:p> 21 00 06 01 https://laboutique.edpsciences.fr/produit/1299/9782759827695/techniques-d-optimisation-tome-1 01 00 03 02 https://laboutique.edpsciences.fr/system/product_pictures/data/009/982/786/original/9782759827688-Optimisation-T1_couv-sofedis.jpg 17 14 20240913T173227+0200 15 00 03 02 https://laboutique.edpsciences.fr/system/product_pictures/data/009/982/787/original/9782759827688-Optimisation-T1_couv-THUMBNAIL.jpg 17 14 20240913T172719+0200 01 P1 EDP Sciences 01 01 P1 EDP Sciences 17 avenue du Hoggar - PA de Courtaboeuf - 91944 Les Ulis cedex A http://publications.edpsciences.org/ 04 11 00 20221201 01 00 20221201 19 00 20221201 2026 06 3052868830012 01 WORLD 27 03 9782759827695 15 9782759827695 WORLD 08 EDP Sciences 04 01 00 20221201 03 01 D1 EDP Sciences 21 04 05 01 02 1 00 49.00 01 5.50 2.55 EUR laboutique.edpsciences.fr-R001828 03 01 01 R001828 00 ED E107 00 01 01 Techniques d’optimisation Tome 1 Optimisation continue 01 fre 08 485 03 22 12580089 17 01 P1 EDP Sciences 01 01 P1 EDP Sciences 17 avenue du Hoggar - PA de Courtaboeuf - 91944 Les Ulis cedex A http://publications.edpsciences.org/ 11 00 20221201 02 01 002181 03 9782759827695 15 9782759827695 03 01 D1 EDP Sciences 45 03 laboutique.edpsciences.fr-002181 03 01 01 002181 03 9782759827695 15 9782759827695 10 EA E107 10 00 01 R001828 ED E107 1 10 01 02 PROfil Les ouvrages de la collection « PROfil » ont pour vocation la transmission des savoirs professionnels dans différentes disciplines. Ils sont rédigés par des experts reconnus dans leurs domaines et contribuent à la formation et l'information des professionnels. 01 01 Techniques d’optimisation Tome 1 Optimisation continue 1 A01 01 A2081 Max Cerf Cerf, Max Max Cerf Max CERF est ingénieur à Ariane Group depuis 1990. Ses activités portent sur l’optimisation des trajectoires et véhicules de transport spatial. Ancien élève de l’Ecole Centrale de Paris (1989), il est titulaire d’une habilitation à diriger des recherches (2019) et exerce des fonctions d’enseignement à l’université. Il a reçu le grade de Chevalier de l’Ordre National du Mérite (2015). Max CERF is an expert engineer in mission analysis at Ariane Group. His activities focus on the optimization of space vehicles and their trajectories. He also teaches at engineering schools and universities. 01 fre 08 484 03 02 24 Izibook:Subject Mathématiques 24 Izibook:Subject Informatique 24 Izibook:Subject Ingénierie 24 Izibook:Subject Sustainable Development Goals (SDG) 24 Izibook:SubjectAndCategoryAndTags |Mathématiques| 24 Izibook:SubjectAndCategoryAndTags |Informatique| 24 Izibook:SubjectAndCategoryAndTags |Ingénierie| 24 Izibook:SubjectAndCategoryAndTags |Sustainable Development Goals (SDG)| 20 optimisation;optimisation mathématique;mathématiques;optimisation continue;algorithme 10 2011 MAT003000 01 510 06 06 05 03 00 <blockquote style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">Cet ouvrage en deux tomes propose un panorama des techniques d’optimisation continue, discrète et fonctionnelle. Ce premier tome est consacré à l’optimisation continue qui traite des problèmes à variables réelles, sans ou avec contraintes. Après des rappels sur les conditions d’optimalité et leur interprétation géométrique, les thèmes abordés sont : <span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes sans gradient qui peuvent s’appliquer à tout type de fonction ; <span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes sans contraintes basés sur des méthodes de descente de type Newton ; <span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes avec contraintes : méthodes de pénalisation, primales, duales et primales-duales ; <span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• la programmation linéaire avec la méthode du simplexe et les méthodes de point intérieur. <span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">L’accent est mis sur la compréhension des principes plutôt que sur la rigueur mathématique. Chaque notion ou algorithme est accompagné d’un exemple détaillé aidant à s’approprier les idées principales. Cet ouvrage issu de 30 années d’expérience s’adresse aux étudiants, chercheurs et ingénieurs désireux d’acquérir une culture générale dans le domaine de l’optimisation. </blockquote><blockquote style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging">Ce livre fait partie de la sélection finale du « Prix Roberval 2023 » dans la catégorie «Enseignement supérieur ».</blockquote> <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">Cet ouvrage en deux tomes proposeun panorama des techniques d’optimisation continue, discrète et fonctionnelle.Ce premier tome est consacré à l’optimisation continue qui traite des problèmesà variables réelles, sans ou avec contraintes. Après des rappels sur lesconditions d’optimalité et leur interprétation géométrique, les thèmes abordéssont : <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes sansgradient qui peuvent s’appliquer à tout type de fonction ; <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes sanscontraintes basés sur des méthodes de descente de type Newton ; <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• les algorithmes aveccontraintes : méthodes de pénalisation, primales, duales et primales-duales ; <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">• la programmation linéaireavec la méthode du simplexe et les méthodes de point intérieur. <p style="language:fr;line-height:107%;margin-top:0pt;margin-bottom:0pt;margin-left:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-line-break-override:none;word-break:normal;punctuation-wrap:hanging"><span style="font-size:12.0pt;font-family:Calibri;mso-ascii-font-family:Calibri;mso-fareast-font-family:Calibri;mso-bidi-font-family:"Times New Roman";color:black;mso-color-index:1;mso-font-kerning:12.0pt;language:fr;mso-style-textfill-type:solid;mso-style-textfill-fill-themecolor:text1;mso-style-textfill-fill-color:black;mso-style-textfill-fill-alpha:100.0%">L’accent est mis sur lacompréhension des principes plutôt que sur la rigueur mathématique. Chaquenotion ou algorithme est accompagné d’un exemple détaillé aidant à s’approprierles idées principales. Cet ouvrage issu de 30 années d’expérience s’adresse auxétudiants, chercheurs et ingénieurs désireux d’acquérir une culture généraledans le domaine de l’optimisation.  02 00 Cet ouvrage en deux tomes propose un panorama des techniques d’optimisation continue, discrète et fonctionnelle. Ce premier tome est consacré à l’optimisation continue qui traite des problèmes à variables réelles, sans ou avec contraintes. 04 00 1. Optimisation continue 1<o:p></o:p>1.1 Formulation 2<o:p></o:p>1.1.1 Forme standard 2<o:p></o:p>1.1.2 Fonction de plusieurs variables 3<o:p></o:p>1.1.3 Lignes de niveau 5<o:p></o:p>1.1.4 Direction de descente 6<o:p></o:p>1.1.5 Variation directionnelle 7<o:p></o:p>1.1.6 Solution 10<o:p></o:p>1.2 Dérivées numériques 14<o:p></o:p>1.2.1 Dérivées premières 15<o:p></o:p>1.2.2 Dérivées secondes 15<o:p></o:p>1.2.3 Réglage de l’incrément 16<o:p></o:p>1.2.4 Dérivée complexe 19<o:p></o:p>1.2.5 Dérivées par extrapolation 20<o:p></o:p>1.3 Réduction du problème 25<o:p></o:p>1.3.1 Réduction linéaire 25<o:p></o:p>1.3.2 Réduction généralisée 31<o:p></o:p>1.4 Optimum global 37<o:p></o:p>1.4.1 Problème dual 37<o:p></o:p>1.4.2 Point-selle 40<o:p></o:p>1.4.3 Programmation linéaire 45<o:p></o:p>1.5 Optimum local 49<o:p></o:p>1.5.1 Directions admissibles 49<o:p></o:p>1.5.2 Conditions de Karush, Kuhn etTucker 54<o:p></o:p>1.5.3 Interprétation géométrique 70<o:p></o:p>1.5.4 Problème linéaire-quadratique 76<o:p></o:p>1.5.5 Analyse de sensibilité 77<o:p></o:p>1.6 Conclusion 82<o:p></o:p>1.6.1 Les points essentiels 82<o:p></o:p>1.6.2 Pour aller plus loin 82<o:p></o:p>2. Optimisation sans gradient 85<o:p></o:p>2.1 Optimisation difficile 86<o:p></o:p>2.1.1 Variables discrètes 86<o:p></o:p>2.1.2 Minima locaux 88<o:p></o:p>2.1.3 Méthodes locales et globales 93<o:p></o:p>2.2 Optimisation unidimensionnelle 96<o:p></o:p>2.2.1 Partage d’intervalles 96<o:p></o:p>2.2.2 Positionnement des points 97<o:p></o:p>2.2.3 Méthode du nombre d’or 99<o:p></o:p>2.2.4 Interpolation quadratique 102<o:p></o:p>2.3 Méthode DIRECT 105<o:p></o:p>2.3.1 Fonction lipschitzienne 105<o:p></o:p>2.3.2 Algorithme en dimension 1 107<o:p></o:p>2.3.3 Algorithme en dimension n 118<o:p></o:p>2.4 Méthode de Nelder-Mead 131<o:p></o:p>2.4.1 Polytope 131<o:p></o:p>2.4.2 Nouveau point 134<o:p></o:p>2.4.3 Améliorations 136<o:p></o:p>2.5 Affine shaker 140<o:p></o:p>2.5.1 Principe 140<o:p></o:p>2.5.2 Transformation affine 142<o:p></o:p>2.5.3 Algorithme 144<o:p></o:p>2.6 CMAES 146<o:p></o:p>2.6.1 Principe 146<o:p></o:p>2.6.2 Adaptation de la covariance 147<o:p></o:p>2.6.3 Algorithme 150<o:p></o:p>2.7 Recuit simulé 153<o:p></o:p>2.7.1 Principe 153<o:p></o:p>2.7.2 Probabilité de transition 154<o:p></o:p>2.7.3 Algorithme 155<o:p></o:p>2.8 Recherche avec tabou 161<o:p></o:p>2.8.1 Principe 161<o:p></o:p>2.8.2 Liste taboue et voisinage 161<o:p></o:p>2.8.3 Affectation quadratique 163<o:p></o:p>2.9 Essaims de particules 171<o:p></o:p>2.9.1 Principe 171<o:p></o:p>2.9.2 Déplacement des particules 171<o:p></o:p>2.9.3 Voisinage 173<o:p></o:p>2.9.4 Algorithme 174<o:p></o:p>2.10 Colonies de fourmis 176<o:p></o:p>2.10.1 Principe 176<o:p></o:p>2.10.2 Mouvement des fourmis 177<o:p></o:p>2.10.3 Problème du voyageur de commerce177<o:p></o:p>2.11 Algorithmes évolutionnaires 179<o:p></o:p>2.11.1 Principe 179<o:p></o:p>2.11.2 Mécanismes d’évolution 180<o:p></o:p>2.11.3 Algorithme 181<o:p></o:p>2.12 Conclusion 186<o:p></o:p>2.12.1 Les points essentiels 186<o:p></o:p>2.12.2 Pour aller plus loin 186<o:p></o:p>3. Optimisation sans contraintes 189<o:p></o:p>3.1 Méthode de Newton 190<o:p></o:p>3.1.1 Système d’équations 190<o:p></o:p>3.1.2 Méthode d’homotopie 196<o:p></o:p>3.1.3 Minimisation 204<o:p></o:p>3.1.4 Moindres carrés 207<o:p></o:p>3.2 Méthodes de quasi-Newton 213<o:p></o:p>3.2.1 Méthode de Broyden 213<o:p></o:p>3.2.2 Méthodes DFP, BFGS et SR1 217<o:p></o:p>3.2.3 Améliorations BFGS 227<o:p></o:p>3.3 Recherche linéaire 231<o:p></o:p>3.3.1 Direction de descente 232<o:p></o:p>3.3.2 Pas de déplacement 248<o:p></o:p>3.3.3 Algorithme 251<o:p></o:p>3.4 Région de confiance 256<o:p></o:p>3.4.1 Modèle quadratique 257<o:p></o:p>3.4.2 Solution directe 259<o:p></o:p>3.4.3 Solution dogleg 261<o:p></o:p>3.4.4 Algorithme 265<o:p></o:p>3.5 Méthodes proximales 268<o:p></o:p>3.5.1 Opérateur proximal 268<o:p></o:p>3.5.2 Interprétations 272<o:p></o:p>3.5.3 Gradient proximal 275<o:p></o:p>3.5.4 Méthode primale-duale 278<o:p></o:p>3.5.5 Calcul de l’opérateur proximal 280<o:p></o:p>3.6 Convergence 284<o:p></o:p>3.6.1 Convergence globale 284<o:p></o:p>3.6.2 Vitesse de convergence 286<o:p></o:p>3.6.3 Précision numérique 290<o:p></o:p>3.7 Conclusion 292<o:p></o:p>3.7.1 Les points essentiels 292<o:p></o:p>3.7.2 Pour aller plus loin 292<o:p></o:p>4. Optimisation avec contraintes 295<o:p></o:p>4.1 Classification des méthodes 296<o:p></o:p>4.1.1 Formulations du problème 296<o:p></o:p>4.1.2 Méthodes primales, primales-dualeset duales 298<o:p></o:p>4.1.3 Mesure de l’amélioration 301<o:p></o:p>4.2 Pénalisation 308<o:p></o:p>4.2.1 Problème pénalisé 308<o:p></o:p>4.2.2 Pénalisation différentiable 311<o:p></o:p>4.2.3 Pénalisation exacte 312<o:p></o:p>4.2.4 Pénalisation quadratique 315<o:p></o:p>4.2.5 Pénalisation barrière 322<o:p></o:p>4.3 Gradient réduit 323<o:p></o:p>4.3.1 Déplacement dans l’espace tangent323<o:p></o:p>4.3.2 Déplacement de restauration 330<o:p></o:p>4.3.3 Recherche linéaire 332<o:p></o:p>4.3.4 Méthode de quasi-Newton 336<o:p></o:p>4.3.5 Algorithme 337<o:p></o:p>4.4 Programmation quadratique séquentielle 341<o:p></o:p>4.4.1 Modèle quadratique local 341<o:p></o:p>4.4.2 Globalisation 347<o:p></o:p>4.4.3 Gestion des contraintes 352<o:p></o:p>4.4.4 Méthode de quasi-Newton 356<o:p></o:p>4.4.5 Algorithme 358<o:p></o:p>4.5 Point intérieur 362<o:p></o:p>4.5.1 Problème barrière 362<o:p></o:p>4.5.2 Globalisation 365<o:p></o:p>4.5.3 Hauteur de barrière 366<o:p></o:p>4.6 Lagrangien augmenté 367<o:p></o:p>4.6.1 Problème dual 367<o:p></o:p>4.6.2 Problème dual augmenté 371<o:p></o:p>4.6.3 Contraintes inégalité 375<o:p></o:p>4.6.4 Algorithme 377<o:p></o:p>4.7 Conclusion 381<o:p></o:p>4.7.1 Les points essentiels 381<o:p></o:p>4.7.2 Pour aller plus loin 381<o:p></o:p>5.Programmation linéaire 383<o:p></o:p>5.1 Simplexe 384<o:p></o:p>5.1.1 Forme standard 384<o:p></o:p>5.1.2 Base 387<o:p></o:p>5.1.3 Pivotage 398<o:p></o:p>5.1.4 Tableau du simplexe 404<o:p></o:p>5.1.5 Problème auxiliaire 410<o:p></o:p>5.1.6 Méthode des deux phases 415<o:p></o:p>5.1.7 Simplexe révisé 422<o:p></o:p>5.1.8 Simplexe dual 423<o:p></o:p>5.1.9 Simplexe complémentaire 430<o:p></o:p>5.2 Point intérieur 436<o:p></o:p>5.2.1 Chemin central 436<o:p></o:p>5.2.2 Direction de déplacement 443<o:p></o:p>5.2.3 Pas de déplacement 448<o:p></o:p>5.2.4 Algorithme deprédiction-correction 455<o:p></o:p>5.2.5 Extensions 458<o:p></o:p>5.3 Conclusion 460<o:p></o:p>5.3.1 Les points essentiels 460<o:p></o:p>5.3.2 Pour aller plus loin 461<o:p></o:p>Index<o:p></o:p>Bibliographie<o:p></o:p> 1. Optimisationcontinue 1<o:p></o:p>1.1 Formulation 2<o:p></o:p>1.1.1 Forme standard 2<o:p></o:p>1.1.2 Fonction de plusieurs variables 3<o:p></o:p>1.1.3 Lignes de niveau 5<o:p></o:p>1.1.4 Direction de descente 6<o:p></o:p>1.1.5 Variation directionnelle 7<o:p></o:p>1.1.6 Solution 10<o:p></o:p>1.2 Dérivées numériques 14<o:p></o:p>1.2.1 Dérivées premières 15<o:p></o:p>1.2.2 Dérivées secondes 15<o:p></o:p>1.2.3 Réglage de l’incrément 16<o:p></o:p>1.2.4 Dérivée complexe 19<o:p></o:p>1.2.5 Dérivées par extrapolation 20<o:p></o:p>1.3 Réduction du problème 25<o:p></o:p>1.3.1 Réduction linéaire 25<o:p></o:p>1.3.2 Réduction généralisée 31<o:p></o:p>1.4 Optimum global 37<o:p></o:p>1.4.1 Problème dual 37<o:p></o:p>1.4.2 Point-selle 40<o:p></o:p>1.4.3 Programmation linéaire 45<o:p></o:p>1.5 Optimum local 49<o:p></o:p>1.5.1 Directions admissibles 49<o:p></o:p>1.5.2 Conditions de Karush, Kuhn etTucker 54<o:p></o:p>1.5.3 Interprétation géométrique 70<o:p></o:p>1.5.4 Problème linéaire-quadratique 76<o:p></o:p>1.5.5 Analyse de sensibilité 77<o:p></o:p>1.6 Conclusion 82<o:p></o:p>1.6.1 Les points essentiels 82<o:p></o:p>1.6.2 Pour aller plus loin 82<o:p></o:p>2. Optimisationsans gradient 85<o:p></o:p>2.1 Optimisation difficile 86<o:p></o:p>2.1.1 Variables discrètes 86<o:p></o:p>2.1.2 Minima locaux 88<o:p></o:p>2.1.3 Méthodes locales et globales 93<o:p></o:p>2.2 Optimisation unidimensionnelle 96<o:p></o:p>2.2.1 Partage d’intervalles 96<o:p></o:p>2.2.2 Positionnement des points 97<o:p></o:p>2.2.3 Méthode du nombre d’or 99<o:p></o:p>2.2.4 Interpolation quadratique 102<o:p></o:p>2.3 Méthode DIRECT 105<o:p></o:p>2.3.1 Fonction lipschitzienne 105<o:p></o:p>2.3.2 Algorithme en dimension 1 107<o:p></o:p>2.3.3 Algorithme en dimension n 118<o:p></o:p>2.4 Méthode de Nelder-Mead 131<o:p></o:p>2.4.1 Polytope 131<o:p></o:p>2.4.2 Nouveau point 134<o:p></o:p>2.4.3 Améliorations 136<o:p></o:p>2.5 Affine shaker 140<o:p></o:p>2.5.1 Principe 140<o:p></o:p>2.5.2 Transformation affine 142<o:p></o:p>2.5.3 Algorithme 144<o:p></o:p>2.6 CMAES 146<o:p></o:p>2.6.1 Principe 146<o:p></o:p>2.6.2 Adaptation de la covariance 147<o:p></o:p>2.6.3 Algorithme 150<o:p></o:p>2.7 Recuit simulé 153<o:p></o:p>2.7.1 Principe 153<o:p></o:p>2.7.2 Probabilité de transition 154<o:p></o:p>2.7.3 Algorithme 155<o:p></o:p>2.8 Recherche avec tabou 161<o:p></o:p>2.8.1 Principe 161<o:p></o:p>2.8.2 Liste taboue et voisinage 161<o:p></o:p>2.8.3 Affectation quadratique 163<o:p></o:p>2.9 Essaims de particules 171<o:p></o:p>2.9.1 Principe 171<o:p></o:p>2.9.2 Déplacement des particules 171<o:p></o:p>2.9.3 Voisinage 173<o:p></o:p>2.9.4 Algorithme 174<o:p></o:p>2.10 Colonies de fourmis 176<o:p></o:p>2.10.1 Principe 176<o:p></o:p>2.10.2 Mouvement des fourmis 177<o:p></o:p>2.10.3 Problème du voyageur de commerce177<o:p></o:p>2.11 Algorithmes évolutionnaires 179<o:p></o:p>2.11.1 Principe 179<o:p></o:p>2.11.2 Mécanismes d’évolution 180<o:p></o:p>2.11.3 Algorithme 181<o:p></o:p>2.12 Conclusion 186<o:p></o:p>2.12.1 Les points essentiels 186<o:p></o:p>2.12.2 Pour aller plus loin 186<o:p></o:p>3. Optimisationsans contraintes 189<o:p></o:p>3.1 Méthode de Newton 190<o:p></o:p>3.1.1 Système d’équations 190<o:p></o:p>3.1.2 Méthode d’homotopie 196<o:p></o:p>3.1.3 Minimisation 204<o:p></o:p>3.1.4 Moindres carrés 207<o:p></o:p>3.2 Méthodes de quasi-Newton 213<o:p></o:p>3.2.1 Méthode de Broyden 213<o:p></o:p>3.2.2 Méthodes DFP, BFGS et SR1 217<o:p></o:p>3.2.3 Améliorations BFGS 227<o:p></o:p>3.3 Recherche linéaire 231<o:p></o:p>3.3.1 Direction de descente 232<o:p></o:p>3.3.2 Pas de déplacement 248<o:p></o:p>3.3.3 Algorithme 251<o:p></o:p>3.4 Région de confiance 256<o:p></o:p>3.4.1 Modèle quadratique 257<o:p></o:p>3.4.2 Solution directe 259<o:p></o:p>3.4.3 Solution dogleg 261<o:p></o:p>3.4.4 Algorithme 265<o:p></o:p>3.5 Méthodes proximales 268<o:p></o:p>3.5.1 Opérateur proximal 268<o:p></o:p>3.5.2 Interprétations 272<o:p></o:p>3.5.3 Gradient proximal 275<o:p></o:p>3.5.4 Méthode primale-duale 278<o:p></o:p>3.5.5 Calcul de l’opérateur proximal 280<o:p></o:p>3.6 Convergence 284<o:p></o:p>3.6.1 Convergence globale 284<o:p></o:p>3.6.2 Vitesse de convergence 286<o:p></o:p>3.6.3 Précision numérique 290<o:p></o:p>3.7 Conclusion 292<o:p></o:p>3.7.1 Les points essentiels 292<o:p></o:p>3.7.2 Pour aller plus loin 292<o:p></o:p>4. Optimisationavec contraintes 295<o:p></o:p>4.1 Classification des méthodes 296<o:p></o:p>4.1.1 Formulations du problème 296<o:p></o:p>4.1.2 Méthodes primales, primales-dualeset duales 298<o:p></o:p>4.1.3 Mesure de l’amélioration 301<o:p></o:p>4.2 Pénalisation 308<o:p></o:p>4.2.1 Problème pénalisé 308<o:p></o:p>4.2.2 Pénalisation différentiable 311<o:p></o:p>4.2.3 Pénalisation exacte 312<o:p></o:p>4.2.4 Pénalisation quadratique 315<o:p></o:p>4.2.5 Pénalisation barrière 322<o:p></o:p>4.3 Gradient réduit 323<o:p></o:p>4.3.1 Déplacement dans l’espace tangent323<o:p></o:p>4.3.2 Déplacement de restauration 330<o:p></o:p>4.3.3 Recherche linéaire 332<o:p></o:p>4.3.4 Méthode de quasi-Newton 336<o:p></o:p>4.3.5 Algorithme 337<o:p></o:p>4.4 Programmation quadratiqueséquentielle 341<o:p></o:p>4.4.1 Modèle quadratique local 341<o:p></o:p>4.4.2 Globalisation 347<o:p></o:p>4.4.3 Gestion des contraintes 352<o:p></o:p>4.4.4 Méthode de quasi-Newton 356<o:p></o:p>4.4.5 Algorithme 358<o:p></o:p>4.5 Point intérieur 362<o:p></o:p>4.5.1 Problème barrière 362<o:p></o:p>4.5.2 Globalisation 365<o:p></o:p>4.5.3 Hauteur de barrière 366<o:p></o:p>4.6 Lagrangien augmenté 367<o:p></o:p>4.6.1 Problème dual 367<o:p></o:p>4.6.2 Problème dual augmenté 371<o:p></o:p>4.6.3 Contraintes inégalité 375<o:p></o:p>4.6.4 Algorithme 377<o:p></o:p>4.7 Conclusion 381<o:p></o:p>4.7.1 Les points essentiels 381<o:p></o:p>4.7.2 Pour aller plus loin 381<o:p></o:p>5.Programmation linéaire 383<o:p></o:p>5.1 Simplexe 384<o:p></o:p>5.1.1 Forme standard 384<o:p></o:p>5.1.2 Base 387<o:p></o:p>5.1.3 Pivotage 398<o:p></o:p>5.1.4 Tableau du simplexe 404<o:p></o:p>5.1.5 Problème auxiliaire 410<o:p></o:p>5.1.6 Méthode des deux phases 415<o:p></o:p>5.1.7 Simplexe révisé 422<o:p></o:p>5.1.8 Simplexe dual 423<o:p></o:p>5.1.9 Simplexe complémentaire 430<o:p></o:p>5.2 Point intérieur 436<o:p></o:p>5.2.1 Chemin central 436<o:p></o:p>5.2.2 Direction de déplacement 443<o:p></o:p>5.2.3 Pas de déplacement 448<o:p></o:p>5.2.4 Algorithme deprédiction-correction 455<o:p></o:p>5.2.5 Extensions 458<o:p></o:p>5.3 Conclusion 460<o:p></o:p>5.3.1 Les points essentiels 460<o:p></o:p>5.3.2 Pour aller plus loin 461<o:p></o:p>Index<o:p></o:p>Bibliographie<o:p></o:p> 21 00 06 01 https://laboutique.edpsciences.fr/produit/1299/9782759827695/techniques-d-optimisation-tome-1 01 00 03 02 https://laboutique.edpsciences.fr/system/product_pictures/data/009/982/786/original/9782759827688-Optimisation-T1_couv-sofedis.jpg 17 14 20240913T173227+0200 15 00 03 02 https://laboutique.edpsciences.fr/system/product_pictures/data/009/982/787/original/9782759827688-Optimisation-T1_couv-THUMBNAIL.jpg 17 14 20240913T172719+0200 01 P1 EDP Sciences 01 01 P1 EDP Sciences 17 avenue du Hoggar - PA de Courtaboeuf - 91944 Les Ulis cedex A http://publications.edpsciences.org/ 04 11 00 20221201 01 00 20221201 19 00 20221201 2026 06 3052868830012 01 WORLD 13 03 9782759827688 15 9782759827688 WORLD 08 EDP Sciences 04 01 00 20221201 03 01 D1 EDP Sciences 20 04 05 01 02 1 00 33.99 01 5.50 1.77 EUR 04 06 01 02 1 00 119.99 01 5.50 1.77 EUR 01 04 06 01 02 1 00 131.99 01 5.50 6.88 USD 01