Remerciez-le!

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

Université de Sherbrooke Optimisation mathématique avec applications en imageri

Université de Sherbrooke Optimisation mathématique avec applications en imagerie Jean-Pierre Dussault 18 décembre 2015 2 Optimisation mathématique avec applications en imagerie1 Jean-Pierre Dussault2 18 décembre 2015 1. c ⃝Jean-Pierre Dussault 2015. Ce manuscrit est mis à disposition selon les termes de la Li- cence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International. 2. Professeur titulaire, département d’Informatique, Université de Sherbrooke, Sherbrooke, Ca- nada J1K 2R1 2 Table des matières Préface ix Notation 1 Introduction 3 I Motivation 5 1 Modélisation 9 1.1 Premier modèle simple . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.1 Modéliser avec AMPL . . . . . . . . . . . . . . . . . . . . . 11 1.1.2 Modélisation dans Scilab . . . . . . . . . . . . . . . . . . . . 13 1.2 Normes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.1 Diﬀérentes normes . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Convexité et diﬀérentiabilité. . . . . . . . . . . . . . . . . . . . . . 19 1.3.1 Notions de convexité . . . . . . . . . . . . . . . . . . . . . . 19 1.3.2 Types des modèles . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.3 Types de minima . . . . . . . . . . . . . . . . . . . . . . . 21 1.4 Distances minimales . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.4.1 Droites . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.4.2 Paraboles . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.4.3 Exercices géométriques . . . . . . . . . . . . . . . . . . . . . 24 1.5 Sommes de distances minimales . . . . . . . . . . . . . . . . . . . . 25 1.5.1 Droite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.5.2 Parabole . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 i ii TABLE DES MATIÈRES 1.6 Ajustements de modèles aux données . . . . . . . . . . . . . . . . . . 28 1.7 Problèmes inverses . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.7.1 Problèmes inverses en traitement d’images . . . . . . . . . . . . . 30 1.7.2 Problèmes inverses en contrôle . . . . . . . . . . . . . . . . . . 38 1.8 Problèmes issus de la physique. . . . . . . . . . . . . . . . . . . . . 40 1.9 Tous les exercices du chapitres . . . . . . . . . . . . . . . . . . . . . 42 II Optimisation diﬀérentiable sans contrainte 45 2 Préliminaires 49 2.1 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.2 Types d’optima . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.2.1 Optima locaux et globaux . . . . . . . . . . . . . . . . . . . . 51 2.2.2 Optima stricts . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2.3 Optima isolés . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2.4 Remarques . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.3 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 54 2.3.1 Conditions pour un point stationnaire. . . . . . . . . . . . . . . 54 2.3.2 Conditions pour un optimum . . . . . . . . . . . . . . . . . . 56 2.4 Algorithmes de descente . . . . . . . . . . . . . . . . . . . . . . . 59 2.4.1 Réduction d’intervalle avec f 1 . . . . . . . . . . . . . . . . . . 61 2.4.2 Réduction d’intervalles sans utiliser la dérivée . . . . . . . . . . . 64 2.5 Algorithmes d’approximation polynomiale . . . . . . . . . . . . . . . . 69 2.5.1 Approximation quadratique de la fonction f . . . . . . . . . . . . 69 2.5.2 Approximation linéaire de la fonction f 1 . . . . . . . . . . . . . . 70 2.5.3 Approximation cubique de la fonction f . . . . . . . . . . . . . . 73 *2.5.4 Utilisation de l’approximation cubique de f . . . . . . . . . . . . 74 2.6 Analyse asymptotique . . . . . . . . . . . . . . . . . . . . . . . . 75 2.6.1 Notation “grand O” et “petit o” . . . . . . . . . . . . . . . . . 76 2.6.2 Vitesse de convergence d’algorithmes itératifs . . . . . . . . . . . 77 2.7 Convergence locale quadratique de l’itération de Newton. . . . . . . . . . 79 2.7.1 Analyse de l’itération de Newton . . . . . . . . . . . . . . . . . 79 2.7.2 Preuve concise de la convergence quadratique . . . . . . . . . . . 80 2.7.3 Preuve détaillée de la convergence quadratique . . . . . . . . . . . 81 *2.8 Analyse des approximations polynômiales . . . . . . . . . . . . . . . . 83 2.8.1 Ordre de convergence de la méthode de la sécante . . . . . . . . . 83 2.8.2 Ordre de convergence de l’approximation cubique de f . . . . . . . 83 2.9 Algorithme combiné . . . . . . . . . . . . . . . . . . . . . . . . . 84 2.9.1 Algorithme de Newton modiﬁé . . . . . . . . . . . . . . . . . . 84 TABLE DES MATIÈRES iii 2.10 Région de conﬁance . . . . . . . . . . . . . . . . . . . . . . . . . 87 2.11 Organisation des chapitres . . . . . . . . . . . . . . . . . . . . . . 91 2.12 Tous les exercices du chapitres . . . . . . . . . . . . . . . . . . . . . 91 3 Optimisation locale de fonctions diﬀérentiables sans contrainte 99 3.1 Formulation du problème . . uploads/Geographie/ opt-pdf.pdf