Techniques d’optimisation Tome 1

Max Cerf

Description

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 :
• les algorithmes sans gradient qui peuvent s’appliquer à tout type de fonction ;
• les algorithmes sans contraintes basés sur des méthodes de descente de type Newton ;
• les algorithmes avec contraintes : méthodes de pénalisation, primales, duales et primales-duales ;
• la programmation linéaire avec la méthode du simplexe et les méthodes de point intérieur.
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. 

Ce livre fait partie de la sélection finale du « Prix Roberval 2023 » dans la catégorie «Enseignement supérieur ».

1. Optimisation continue 1

1.1 Formulation 2

1.1.1 Forme standard 2

1.1.2 Fonction de plusieurs variables 3

1.1.3 Lignes de niveau 5

1.1.4 Direction de descente 6

1.1.5 Variation directionnelle 7

1.1.6 Solution 10

1.2 Dérivées numériques 14

1.2.1 Dérivées premières 15

1.2.2 Dérivées secondes 15

1.2.3 Réglage de l’incrément 16

1.2.4 Dérivée complexe 19

1.2.5 Dérivées par extrapolation 20

1.3 Réduction du problème 25

1.3.1 Réduction linéaire 25

1.3.2 Réduction généralisée 31

1.4 Optimum global 37

1.4.1 Problème dual 37

1.4.2 Point-selle 40

1.4.3 Programmation linéaire 45

1.5 Optimum local 49

1.5.1 Directions admissibles 49

1.5.2 Conditions de Karush, Kuhn etTucker 54

1.5.3 Interprétation géométrique 70

1.5.4 Problème linéaire-quadratique 76

1.5.5 Analyse de sensibilité 77

1.6 Conclusion 82

1.6.1 Les points essentiels 82

1.6.2 Pour aller plus loin 82

2. Optimisation sans gradient 85

2.1 Optimisation difficile 86

2.1.1 Variables discrètes 86

2.1.2 Minima locaux 88

2.1.3 Méthodes locales et globales 93

2.2 Optimisation unidimensionnelle 96

2.2.1 Partage d’intervalles 96

2.2.2 Positionnement des points 97

2.2.3 Méthode du nombre d’or 99

2.2.4 Interpolation quadratique 102

2.3 Méthode DIRECT 105

2.3.1 Fonction lipschitzienne 105

2.3.2 Algorithme en dimension 1 107

2.3.3 Algorithme en dimension n 118

2.4 Méthode de Nelder-Mead 131

2.4.1 Polytope 131

2.4.2 Nouveau point 134

2.4.3 Améliorations 136

2.5 Affine shaker 140

2.5.1 Principe 140

2.5.2 Transformation affine 142

2.5.3 Algorithme 144

2.6 CMAES 146

2.6.1 Principe 146

2.6.2 Adaptation de la covariance 147

2.6.3 Algorithme 150

2.7 Recuit simulé 153

2.7.1 Principe 153

2.7.2 Probabilité de transition 154

2.7.3 Algorithme 155

2.8 Recherche avec tabou 161

2.8.1 Principe 161

2.8.2 Liste taboue et voisinage 161

2.8.3 Affectation quadratique 163

2.9 Essaims de particules 171

2.9.1 Principe 171

2.9.2 Déplacement des particules 171

2.9.3 Voisinage 173

2.9.4 Algorithme 174

2.10 Colonies de fourmis 176

2.10.1 Principe 176

2.10.2 Mouvement des fourmis 177

2.10.3 Problème du voyageur de commerce177

2.11 Algorithmes évolutionnaires 179

2.11.1 Principe 179

2.11.2 Mécanismes d’évolution 180

2.11.3 Algorithme 181

2.12 Conclusion 186

2.12.1 Les points essentiels 186

2.12.2 Pour aller plus loin 186

3. Optimisation sans contraintes 189

3.1 Méthode de Newton 190

3.1.1 Système d’équations 190

3.1.2 Méthode d’homotopie 196

3.1.3 Minimisation 204

3.1.4 Moindres carrés 207

3.2 Méthodes de quasi-Newton 213

3.2.1 Méthode de Broyden 213

3.2.2 Méthodes DFP, BFGS et SR1 217

3.2.3 Améliorations BFGS 227

3.3 Recherche linéaire 231

3.3.1 Direction de descente 232

3.3.2 Pas de déplacement 248

3.3.3 Algorithme 251

3.4 Région de confiance 256

3.4.1 Modèle quadratique 257

3.4.2 Solution directe 259

3.4.3 Solution dogleg 261

3.4.4 Algorithme 265

3.5 Méthodes proximales 268

3.5.1 Opérateur proximal 268

3.5.2 Interprétations 272

3.5.3 Gradient proximal 275

3.5.4 Méthode primale-duale 278

3.5.5 Calcul de l’opérateur proximal 280

3.6 Convergence 284

3.6.1 Convergence globale 284

3.6.2 Vitesse de convergence 286

3.6.3 Précision numérique 290

3.7 Conclusion 292

3.7.1 Les points essentiels 292

3.7.2 Pour aller plus loin 292

4. Optimisation avec contraintes 295

4.1 Classification des méthodes 296

4.1.1 Formulations du problème 296

4.1.2 Méthodes primales, primales-dualeset duales 298

4.1.3 Mesure de l’amélioration 301

4.2 Pénalisation 308

4.2.1 Problème pénalisé 308

4.2.2 Pénalisation différentiable 311

4.2.3 Pénalisation exacte 312

4.2.4 Pénalisation quadratique 315

4.2.5 Pénalisation barrière 322

4.3 Gradient réduit 323

4.3.1 Déplacement dans l’espace tangent323

4.3.2 Déplacement de restauration 330

4.3.3 Recherche linéaire 332

4.3.4 Méthode de quasi-Newton 336

4.3.5 Algorithme 337

4.4 Programmation quadratique séquentielle 341

4.4.1 Modèle quadratique local 341

4.4.2 Globalisation 347

4.4.3 Gestion des contraintes 352

4.4.4 Méthode de quasi-Newton 356

4.4.5 Algorithme 358

4.5 Point intérieur 362

4.5.1 Problème barrière 362

4.5.2 Globalisation 365

4.5.3 Hauteur de barrière 366

4.6 Lagrangien augmenté 367

4.6.1 Problème dual 367

4.6.2 Problème dual augmenté 371

4.6.3 Contraintes inégalité 375

4.6.4 Algorithme 377

4.7 Conclusion 381

4.7.1 Les points essentiels 381

4.7.2 Pour aller plus loin 381

5.Programmation linéaire 383

5.1 Simplexe 384

5.1.1 Forme standard 384

5.1.2 Base 387

5.1.3 Pivotage 398

5.1.4 Tableau du simplexe 404

5.1.5 Problème auxiliaire 410

5.1.6 Méthode des deux phases 415

5.1.7 Simplexe révisé 422

5.1.8 Simplexe dual 423

5.1.9 Simplexe complémentaire 430

5.2 Point intérieur 436

5.2.1 Chemin central 436

5.2.2 Direction de déplacement 443

5.2.3 Pas de déplacement 448

5.2.4 Algorithme deprédiction-correction 455

5.2.5 Extensions 458

5.3 Conclusion 460

5.3.1 Les points essentiels 460

5.3.2 Pour aller plus loin 461

Index

Bibliographie

Sujets

• Sciences formelles
• Mathématiques appliquées
• Mathématiques appliquées
• Applied
• Sciences et techniques
• mathématiques
• Mathematics
• Mathématiques
• Ingénierie
• Informatique
• Mathématiques pures
• Mathématiques générales
• Mathématiques fondamentales

Informations

• Publié par: EDP Sciences
• Date de parution: 01 décembre 2022
• Nombre de lectures: 16
• EAN13: 9782759827695
• Langue: Français
• Poids de l'ouvrage: 11 Mo

Extrait

- Max CERF
PROfl
Techniques d’optimisation Tome I
PROfl
Techniques d’optimisation Tome I
Optimisation continue
Max CERF
PROfl
C et 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 :
• les algorithmes sans gradient qui peuvent s’appliquer à tout type de fonction ;
• les algorithmes sans contraintes basés sur des méthodes de descente de type Newton ;
• le s algorithmes avec contraintes : méthodes de pénalisation, primales, duales et primales-duales ; Techniques d’optimisation
• la programmation linéaire avec la méthode du simplexe et les méthodes de point intérieur.
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 Tome Iidé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.
Optimisation continue
Max Cerf, est ingénieur expert en analyse de mission à ArianeGroup. Ses activités
portent sur l’optimisation des véhicules spatiaux et de leurs trajectoires. Il
exerce également des fonctions d’enseignement en écoles d’ingénieurs et à
l’université.
Max CERF
Les ouvrages de la collection PROfl ont 978-2-7598-2768-8
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
9 782759 827688 www.edpsciences.org et l’information des professionnels.49 €
9782759827688-COUV_TechOptimi_T1.indd 1 21/10/2022 12:2621/10/2022 12:26 - Max CERF
PROfl
Techniques d’optimisation Tome I
PROfl
Techniques d’optimisation Tome I
Optimisation continue
Max CERF
PROfl
C et 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 :
• les algorithmes sans gradient qui peuvent s’appliquer à tout type de fonction ;
• les algorithmes sans contraintes basés sur des méthodes de descente de type Newton ;
• le s algorithmes avec contraintes : méthodes de pénalisation, primales, duales et primales-duales ; Techniques d’optimisation
• la programmation linéaire avec la méthode du simplexe et les méthodes de point intérieur.
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 Tome Iidé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.
Optimisation continue
Max Cerf, est ingénieur expert en analyse de mission à ArianeGroup. Ses activités
portent sur l’optimisation des véhicules spatiaux et de leurs trajectoires. Il
exerce également des fonctions d’enseignement en écoles d’ingénieurs et à
l’université.
Max CERF
Les ouvrages de la collection PROfl ont 978-2-7598-2768-8
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
9 782759 827688 www.edpsciences.org et l’information des professionnels.
9782759827688-COUV_TechOptimi_T1.indd 1 21/10/2022 12:2621/10/2022 12:26Techniques
d’optimisation
Tome 1
Optimisation continue
Max CERF Imprimé en France
ISBN (papier) : 978-2-7598-2768-8 – ISBN (ebook) : 978-2-7598-2769-5
Tous droits de traduction, d’adaptation et de reproduction par tous procédés, réservés pour tous
pays. La loi du 11 mars 1957 n’autorisant, aux termes des alinéas 2 et 3 de l’article 41, d’une part,
que les « copies ou reproductions strictement réservées à l’usage prive du copiste et non destinées
à une utilisation collective », et d’autre part, que les analyses et les courtes citations dans un but
d’exemple et d’illustration, « toute représentation intégrale, ou partielle, faite sans le
consenteerment de l’auteur ou de ses ayants droit ou ayants cause est illicite » (alinéa 1 de l’article 40).
Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc une
contrefaçon sanctionnée par les articles 425 et suivants du code pénal.
© EDP Sciences, 2022









J’adresse mes plus sincères remerciements aux personnes qui m’ont aidé à réaliser
ce livre, en particulier :

France Citrini pour en avoir accepté la publication aux éditions EDP ;
Nathalie Legros pour sa relecture du texte et l’amélioration de la présentation ;
Sophie Hosotte et Magalie Jolivet pour leur assistance au processus éditorial ;
Thomas Haberkorn pour sa vérification minutieuse du contenu scientifique, et
pour les innombrables astuces numériques qu’il m’a partagées ;
Emmanuel Trélat pour sa préface, sa relecture et ses conseils d’exposé, mais
aussi pour notre collaboration de longue date et la compétence que j’ai acquise
à ses côtés ;
Claude Blouvac† mon professeur de lycée qui m’a mis en 1982 sur la voie des
mathématiques et qui aurait été très heureux de voir cet ouvrage.



Préface


Les algorithmes sont omniprésents dans notre monde moderne. Ils nous indiquent
les trajets optimaux, préviennent et évaluent les risques, fournissent des
prévisions, anticipent ou assistent nos décisions. Ils sont devenus des éléments
essentiels de notre quotidien. Ces algorithmes reposent la plupart du temps sur des
processus d'optimisation et consistent à minimiser ou maximiser un critère sous
certaines contraintes, nous indiquant ainsi des solutions faisables et plus
intelligentes que d'autres, permettant de planifier au mieux un processus à
exécuter.
Il existe de très nombreuses méthodes d'optimisation, basées sur des heuristiques
diverses et variées, parfois simples et intuitives, parfois plus élaborées et
nécessitant des développements mathématiques fins.
C'est à travers cette jungle d'algorithmes, résultant de dizaines d'années de
recherches et développements, que Max Cerf nous guide avec toute son expertise,
son intuition et son pragmatisme.
Max Cerf est ingénieur senior à ArianeGroup depuis 30 ans. Spécialiste reconnu
de trajectographie, il élabore et optimise les trajets des engins spatiaux, sous de
multiples contraintes. Il a ainsi acquis et développé une connaissance très
complète des meilleurs algorithmes en optimisation continue, en optimisation
discrète (sur des graphes), en contrôle optimal. C'est de plus un pédagogue
exceptionnel, avec un véritable talent à expliquer de manière limpide et intuitive
des concepts parfois compliqués.
Avec ce double ouvrage, il offre un guide inestimable au lecteur non spécialiste
qui souhaite comprendre ou résoudre des problèmes d'optimisation de la manière
la plus efficace possible.

Emmanuel Trélat, Sorbonne Université, Paris



Introduction


L’optimisation mathématique est en développement constant depuis les années
1950 et l’apparition des premiers ordinateurs. Devant la variété des algorithmes
et des logiciels disponibles, il est parfois difficile pour un non spécialiste de s’y
retrouver. L’objectif de ce livre en deux tomes est de donner un aperçu d’ensemble
du domaine. Il s’adresse aux étudiants, enseignants, ingénieurs et chercheurs
désireux d’acquérir une connaissance générale sur les techniques d’optimisation
mathématique.
L’optimisation vise à contrôler les entrées (variables) d’un système, d’un
processus ou d’un modèle pour obtenir les sorties souhaitées (contraintes) au
meilleur coût. Selon la nature des entrées à contrôler, on distingue l’optimisation
continue, discrète ou fonctionnelle.
L’optimisation continue (chapitres 1 à 5 du tome I) traite des problèmes à
variables réelles. Le chapitre 1 expose les conditions d’optimalité dans le cas de
fonctions différentiables ainsi que le calcul numérique de dérivées. Les chapitres
2, 3 et 4 donnent un panorama des méthodes d’optimisation sans gradient, sans
contraintes et avec contraintes. Le chapitre 5 est consacré à la programmation
linéaire continue, avec les méthodes du simplexe et de point intérieur.
L’optimisation discrète (chapitres 1 et 2 du tome II) traite des problèmes à
variables entières. Le chapitre 1 concerne la programmation linéaire en variables
mixtes par méthodes de coupes ou méthodes arborescentes. Le chapitre 2 présente
un panorama des problèmes combinatoires, leur modélisation par des graphes et
les algorithmes spécialisés aux problèmes de chemin, de flot ou d’affectation.
L’optimisation fonctionnelle (chapitres 3 à 5 du tome II) traite des problèmes en
dimension infinie. L’entrée à contrôler est une fonction et non plus un nombre fini
de variables. Le chapitre 3 introduit les notions de fonctionnelle et de calcul des
variations. Le chapitre 4 présente les problèmes de contrôle optimal et les
conditions d’optimalité. Le chapitre 5 est consacré aux méthodes numériques
(intégration d’équations différentielles, méthodes directes et indirectes).
Dans chaque chapitre, les développements théoriques et démonstrations se
limitent à l’essentiel. Les algorithmes sont accompagnés d’exemples détaillés en
vue de faciliter leur compréhension.
Table des matières


1. Optimisation continue 1
1.1 Formulation 2
1.1.1 Forme standard 2
1.1.2 Fonction de plusieurs variables 3
1.1.3 Lignes de niveau 5
1.1.4 Direction de descente 6
1.1.5 Variation directionnelle 7
1.1.6 Sol