Remerciez-le!

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

Faculté des Sciences Appliquées Optimisation contrainte et non-contrainte par r

Faculté des Sciences Appliquées Optimisation contrainte et non-contrainte par régions de conﬁance et avec approximations locales quadratiques Jérôme Walmag Thèse de doctorat en sciences appliquées Promoteur : Éric J. M. Delhez 2010 2 L’homme raisonnable s’adapte au monde ; l’homme déraisonnable s’obstine à essayer d’adapter le monde à lui-même. Tout progrès dépend donc de l’homme déraisonnable. Georges Bernard Shaw Remerciements Il n’est un secret pour personne que la rédaction d’une thèse est un exercice qui met à contribution bien plus de personnes que celles dont le nom ﬁgure sur la couverture de l’ouvrage. De nombreuses personnes ont par leur participation — parfois inconsciente — contribué au bon déroulement de ce projet. Je voudrais en tout premier lieu remercier Éric Delhez, à qui je dois cette aventure. Je voudrais d’abord le remercier pour sa conﬁance, son soutien, son attention, son intérêt pour l’évolution de mes recherches, ses bons conseils, ses qualités humaines et sa grande compréhension face à mes choix de vie qui ne furent pas exactement de ceux qui simpliﬁent la vie d’un promoteur de thèse. Toutes ces qualités m’ont permis de mener ce travail à bon port. Les quelques moments passés à enseigner dans les séances de répétitions qu’il m’a conﬁées m’ont également permis de satisfaire ma passion pour l’éducation et la pédagogie. Pour tout cela, je tiens à lui exprimer toute ma gratitude. Je remercie également l’Université de Liège, la faculté des Sciences Appli- quées et le département A&M pour m’avoir permis de mener mes recherches dans un environnement stimulant. À ce titre, je tiens tout spécialement à remercier les collègues du groupe de Mathématiques générales pour toutes les discussions scientiﬁques approfondies mais aussi et surtout pour tous les bons moments pas- sés à discuter de tout et de rien dans une ambiance détendue : merci à Patricia pour l’intérêt porté à mon travail, merci à Christophe pour les séances collectives de débogage. Merci également à Géraldine et Francine. Je voudrais aussi remercier Caroline, Julien et Renaud, de vieux amis tous docteurs aujourd’hui, pour leur soutien moral : leurs encouragements m’ont aidé à garder le cap malgré les embûches. Je réserve les dernières lignes à ceux qui ont vécu cette thèse en en subissant les conséquences les moins agréables. Merci à Delphine pour absolument tout mais encore pour tout le reste. Et merci aux deux petits bonshommes de deux et quatre ans qui m’ont d’ores et déjà appris bien plus que toutes les thèses du monde. 3 4 Table des matières I Introduction 15 1 Position du problème 17 1.1 Formulation mathématique. . . . . . . . . . . . . . . . . . . . . . 18 1.2 Conditions d’optimalité. . . . . . . . . . . . . . . . . . . . . . . 18 1.3 Taux de convergence. . . . . . . . . . . . . . . . . . . . . . . . . 20 1.4 Objet et apport de ce travail. . . . . . . . . . . . . . . . . . . . . 21 2 Méthodes de globalisation en optimisation 25 2.1 Recherche linéaire. . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.1 Méthodes à un point. . . . . . . . . . . . . . . . . . . . . 27 2.1.2 Méthodes à deux points. . . . . . . . . . . . . . . . . . . 28 2.1.3 Méthode à trois points. . . . . . . . . . . . . . . . . . . . 30 2.2 Régions de conﬁance. . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3 Point proximal. . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.4 Méta-heuristiques. . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4.1 Recuit simulé. . . . . . . . . . . . . . . . . . . . . . . . 35 2.4.2 Algorithmes génétiques. . . . . . . . . . . . . . . . . . . 37 2.4.3 Propriétés générales. . . . . . . . . . . . . . . . . . . . . 38 2.5 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3 Approximations locales 39 3.1 Approximations linéaires. . . . . . . . . . . . . . . . . . . . . . . 39 3.1.1 Méthode de la plus grande pente. . . . . . . . . . . . . . 39 3.1.2 Cas non-différentiable. . . . . . . . . . . . . . . . . . . . 40 3.2 Approximations quadratiques. . . . . . . . . . . . . . . . . . . . 42 3.2.1 Méthode de Newton. . . . . . . . . . . . . . . . . . . . . 42 3.2.2 Méthodes de Newton modiﬁées. . . . . . . . . . . . . . . 43 3.2.3 Méthodes de type quasi-Newton. . . . . . . . . . . . . . . 46 3.2.4 Directions conjuguées. . . . . . . . . . . . . . . . . . . . 50 3.2.5 Résolution d’équations non-linéaires. . . . . . . . . . . . 52 3.2.6 Approximations quadratiques séparables. . . . . . . . . . 54 5 6 TABLE DES MATIÈRES 3.3 Autres approximations. . . . . . . . . . . . . . . . . . . . . . . . 55 3.3.1 Approximation conique. . . . . . . . . . . . . . . . . . . 55 3.3.2 Asymptotes mobiles. . . . . . . . . . . . . . . . . . . . . 56 3.4 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4 Convergence des régions de conﬁance 59 4.1 Points critiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Convergence globale du premier ordre. . . . . . . . . . . . . . . . 60 4.2.1 Hypothèses sur le problème. . . . . . . . . . . . . . . . . 60 4.2.2 Hypothèses sur l’algorithme. . . . . . . . . . . . . . . . . 61 4.2.3 Théorème de convergence. . . . . . . . . . . . . . . . . . 66 4.3 Convergence globale du second ordre. . . . . . . . . . . . . . . . 67 4.3.1 Approximations locales asymptotiquement convexes. . . . 67 4.3.2 Approximations locales non-convexes. . . . . . . . . . . . 68 4.3.3 Hypothèses sur l’algorithme. . . . . . . . . . . . . . . . . 70 4.3.4 Théorème de convergence globale. . . . . . . . . . . . . . 72 4.4 Forme des régions de conﬁance. . . . . . . . . . . . . . . . . . . 72 4.5 Problèmes non-différentiables. . . . . . . . . . . . . . . . . . . . 75 4.6 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 II Optimisation non-contrainte 81 5 Identiﬁcation paramétrique 83 5.1 Modélisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.1.1 Modélisation mathématique. . . . . . . . . uploads/Geographie/ these-jw-goooood.pdf