Remerciez-le!

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

N° d'ordre: lBS THE8E présentée li L'UNIVERSITE PAUL SABATIER DE TOULOUSE (Scie

N° d'ordre: lBS THE8E présentée li L'UNIVERSITE PAUL SABATIER DE TOULOUSE (Sciences) pour obtenir le DOCTORAT de L'UNIVERSITE PAUL SABATIER Spécialité: Calcul Scientifique par Soumana Beidi HAMMA ETUDE DE METHODES NUMERIQUES D'OPTIMISATION GLOBALE soutenue publiquement le 13 Mars 1992, devant le jury composé de: BONNEMOY C. HIRIART-URRUTY J.-B. MALIVERT Ch. PHAM DINH T. RAYMOND J.-P. ROUZE M. Professeur. Université d'Auvergne. Clermont-Ferrand Professeur. Université Paul Sabatier de Toulouse Professeur. Université de Limoges Professeur. I.N.S.A. de Rouen Professeur. Université Paul Sabatier de Toulouse Chef du département Projet et Analyse C.N.E.S.• Centre Spatial Guyanais. Kourou. Laboratoire d'Analyse Numérique Formation Doctorale de Mathématiques Appliquées Université Paul Sabatier Travail réalisé dans le cadre d'un marché C.N.E.S. "Etude de problèmes d'optimisation globale" (marché N° 873 - CNES - 87 - 4937) REMERCIEMENTS •••••••••••••••••••••••••• C'est en sortant de l'EN.A.C. (Ecole Nationale de l'Aviation Civile) de Toulouse que j'ai eu la chance de rencontrer le Professeur Jean-Baptiste HIRIART-URRUTY. Il m'a fait reprendre le goût des mathématiques, m'a initié à la recherche et a dirigé mes recherches durant tourie travail de thëse. Pour tous ses conseils, toute son aide et sa disponiblùé régulière je lui suis infiniment reconnaissant de m'avoir guidé. Le département Mathématiques Appliquées et Analyse Numérique du Centre National d'Etudes Spatiales (CN.E.S.) de Toulouse est à l'origine de ce travail. Je remercie donc tous les membres du département, en particulier Mmes C. AUBERT, P. DORIO et MM. F. BONNEAU, G. LASSAllE-BALlER et P. LEGENDRE. Mr. ROUZE a été notre premier contact avec le département. Il a suivi ce travail de trés près. Son aide et ses conseils ont été précieux. De plus il a accepté de faire le déplacement (depuis Kourou) pour participer à mon jury. Pour tout cela je le remercie vivement. Avec le Professeur C. BONNEMOY de l'Université d'Auvergne on a eu une coopération trës fructueuse.ll a aussi accepté de présider mon jury. Je l'en remercie beaucoup. Je remercie également les Professeurs C. MAL/VERT de l'Université de Limoges, PHAM DINH Tao de l'IN.S.A. de ROUEN, J.-P. RAYMOND de l'Université Paul Sabatier de Toulouse pour avoir accepté d'être les rapporteurs et examinateurs de ce travail et pour leurs corrections et critiques constructives. J'adresse ma reconnaissance à mes deux "nègres" en informatique: l'un Blanc, Mr K. YAZDANIAN ( C.E.R.T. et Sup'Aéro de Toulouse), l'autre... Noir, J.-C. HOCI/ON ingénieur en Informatique de l'E.N.S.E.E.I.H.T. de Toulouse. Je remercie aussi le Département de Mathématiques de la Faculté des Sciences de Limoges, qui en m'accueillant depuis Octobre 1991 m'a permis de terminer la rédaction de ce travail et de bénéficier des conseils et de /' expérience de son équipe d'optimisation dirigée par le Professeur M. THERA. Que tous les membres (chercheurs, techniciens et administratifs) du Laboratoire d'Analyse Numérique de L'université Paul Sabatier de Toulouse trouvent ici ma reconnaissance pour m'avoir aidé a accomplir ce travail. Je ne terminerai pas celle liste de gratitude sans remercier Thierry & Marie BELTAN et tous mes amis Baha'is pour leur amitésincère et leur soutien moral. Par la possesion du don idéal de la recherche scientifique, l'homme est le produit le plus noble de la création, le régulateur de la nature,., Ce don est le pouvoir le plus louable de l'homme car, par l'utilisation qui en est faite, l'amélioration de la race humaine s'accomplit, et le développement des vertus de l'humanité est rendu possible... Abdu'l-bahà (1844-1921) "Les bases de J'unité du monde" Certaines personnes dépourvues de génie personnel sont quelquefois douées du pouvoir de le stimuler... Anonyme Baba, Maman, Permettez-moi de dédier ce travail A celui qui, en maîtrisant la tête du serpent, M'a permis de jouer avec la queue... A mon tour, à présent, de prendre La tête du serpent pour nos enfants; Même si cette fois-ci, 11 s'agit plutôt ... d'une pieuvre! PRESENTATION GENERALE Le présent travail qui porte sur les méthodes numériques d'optimisation globale, a pour origine un sujet proposé par le C.N.E.S. (Centre National d'Etudes Spatiales) de Toulouse "Etude de problèmes d'optimisation globale" (marché N° 873-CNES-87-4937). Le but était de développer des codes d'optimisation globale en vue d'applications à des problèmes spécifiques. Au chapitre l , nous rappelons les problématiques de l'optimisation locale et de l'optimisation globale d'un point de vue numérique. Nous nous attachons, au chapitre 2, à faire l'état de l'art des méthodes et codes existants en optimisation globale, en les classant suivant différents critères: leur philosophie, leur stratégie, leur garantie de convergence, etc. Ensuite, nous étudions de près, au chapitre 3, certaines méthodes numériques: le Recuit Simulé, la méthode du Tunnelier, le Polytope Mouvant. Dans ce chapitre, nous présentons aussi des résultats numériques de codes que nous avons écrits, testés et améliorés. Ce chapitre contient également, à la suite de plusieurs expérimentations numériques, des détails de choix de paramètres, conseils d'utilisation, etc. pour certains algorithmes. Enfin nous abordons, au chapitre 4, le problème d'optimisation de trajectoires interplanétaires tel qu'il nous a été présenté par le C.N.E.S. A la fin de chaque chapitre (ou paragraphe indépendant) nous donnons les références bibliographiques qui s'y rapportent. En fin de document, nous proposons une (proposition de) traduction en Français de différents termes anglais couramment utilisés en optimisation globale numérique. C'est la traduction que nous avons utilisée dans ce mémoire. Une annexe propose les programmes et les détails de plusieurs résultats numériques expérimentaux. TABLES DES MATIERES INTRODUCTION GENERALE Chapitre 1 OPTIMISATION LOCALE vs OPTIMISATION GLOBALE 4 1.1. GENERALITES 1.1.1. Convention de vocabulaire 1.1.2. Position des Problèmes 1.1.3. Solutions numériques 1.1.4. Diversités des méthodes 1.1.5. Difficultés rencontrées pour notre étude 1.2. OPTIMISATION LOCALE 1.2.1. Rappels sur la théorie de l'optimisation locale 1.2.2. Quelques exemples d'algorithmes efficaces 1.2.2.1. l'algorithme de D.F.P. 1.2.2.2. les algorithmes de Quasi-Newton 1.2.3. Transition vers l'optimisation globale référen ces 7 8 9 Il Il 13 14 16 17 18 19 20 Chapitre 2 METHODES NUMERIQUES D'OPTIMISATION GLOBALE 2.0. Rappel du problème 2.1. Classification des problèmes 2.1.1. Problèmes avec/ou sans contraintes. 2.1.2. Problèmes particuliers/généraux 2.2. Classification des méthodes 2.2.1. Selon l'approche 2.2.2. Selon la philosophie 2.2.3. Selon la garantie de convergence 2.2.4. Autres classifications 2.3. Choix d'une classirication 2.3.1. Méthodes avec garantie de convergence 2.3.2. Méthodes directes 2.3.3. Méthodes indirectes 2.4. Caractéritiques générales des méthodes 2.4.1. Optimisation sur un compact S 2.4.2. Schémas généraux 22 23 23 23 24 25 26 27 28 29 30 31 38 39 39 40 2.5. Difficultés Numériques 2.5.1. Critères d'arrêt - Convergence des codes 44 2.5.2. Difficultés liées aux contraintes 45 2.5.3. Propriétés minimales pour un code d'optimisation globale 45 2.5.4. Caractérisation d'un minimum global 46 2.6. Parallélisation 48 2.6.1. Motivations 48 2.6.2. Machines parallèles 48 2.6.3. Parallélisation 49 2.6.4. Conclusion 50 2.7. Quelques applications de l'optimisation globale 50 2.7.1. Les moindres carrés 51 2.7.2. Autres exemples 53 2.8. Conlusion 53 références 55 Chapitre 3 EXEMPLES D'ALGORITHMES NUMERIQUES D'OPTIMISATION GLOBALE 3.1. LE RECUIT SIMULE en optimisation "continue" 59 3.1.1. Philosophie 60 3.1.2. Algorithme général du Recuit Simulé 61 3.1.3. Application à l'optimisation dans Rn 64 3.1.4. Améliorations du Recuit: utilisation de cycles de Réchauffement 69 3.1.5. Résultats Numériques 81 3.1.6. Conclusion 91 références 92 3.2. LE "POLYTOPE MOUVANT" OU SIMPLEXE DE NELDER & MEAD 94 3.2.1 Principe 95 3.2.2 Algorithmes du Polytope Mouvant 96 3.2.2.1. Algorithme séquentiel 98 3.2.2.2. L'algorithme parallélisable 99 3.2.2.3. Description détaillée de la version séquentielle 101 3.2.3. L'algorithme à recherche adapté 107 3.2.4. Convergence de la méthode du Polytope Mouvant 110 3.2.5 Résultats Numériques 113 3.2.6. Conclusion 115 références 1 15 3.3. LA METHODE DU TUNNELIER 3.3.1. Principe 3.3.2. Algorithme du Tunnelier 3.3.3. Choix des paramètres 3.3.4. Convergence de la méthode du Tunnelier 3.3.4. Résultats Numériques références 1 17 1 17 1 18 12 1 123 123 124 Chapitre 4 OPTIMISATION DE TRAJECTOIRES INTERPLANETAIRES 4.8.2.2. 4.9 Conclusion références 4.0. 4.1. 4.2. 4.3. 4.4. 4.5. 4.6. 4.7. 4.8. Introduction Présentation de la mission VESTA Notations Position du problème Résolution du problème Le problème d'optimisation Calcul de la fonction coût Code général HOPTIMA Résultats numériques 4.8.1 Trajectoires initiales 4.8.2 Résultats 4.8.2.1. Exemples de résultats complets d'optimisation locale Résultats d'optimisation globale 126 127 128 129 129 13 1 132 136 140 140 143 143 147 149 150 Conclusion générale Glossaire 15 1 153 4 INTRODUCTION GENERALE Soit f: Rn --+ R une fonction objectif, continue. La programmation non linéaire ou optimisation (locale) non linéaire consiste en un ensemble de méthodes pour trouver un optimum local (minimum ou maximum). Mais comme maximiser f revient à minimiser -f, nous considérerons donc tout problème d'optimisation comme un problème de minimisation c'est-à-dire (Ploc): trouver un point Xloc de Rn tel qu'il existe un voisinage V de Xloc avec f(Xloc) 1 f(X) V X eV (R.O.I.) Cependant en pratique, il existe, en général, locaux avec des valeurs de fonction différentes. l'optimisation globale se veut de : (Pg): trouver un point x* de Rn tel que f(X*) 1 f(X) plusieurs minimiseurs Ainsi le problème de V X e Rn (R.O.2) Nous nous intéressons dans ce travail à la résolution numérique de ce problème. Pour des raisons numériques (Le. informatiques cf 1.1.2.) on suppose l'existence d'un compact S contenant x* comme point intérieur, et le problème (Pg) devient celui que nous allons considérer uploads/Science et Technologie/ cs-01341-pdf.pdf