Remerciez-le!

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

Programmation non linéaire Jean-Pierre Dussault1 4 janvier 2011 1. Professeur t

Programmation non linéaire Jean-Pierre Dussault1 4 janvier 2011 1. Professeur titulaire, département d’Informatique, Université de Sherbrooke, Sherbrooke, Ca- nada J1K 2R1 2 Table des matières Préface xi Notation 1 Introduction 3 1 Préliminaires 9 1.1 Optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Types d’optima . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Optima locaux et globaux . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Optima stricts . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.3 Optima isolés . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.4 Remarques . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.1 Conditions pour un point stationnaire. . . . . . . . . . . . . . . 14 1.3.2 Conditions pour un optimum . . . . . . . . . . . . . . . . . . 16 1.4 Algorithmes de descente . . . . . . . . . . . . . . . . . . . . . . . 20 1.4.1 Réduction d’intervalle avec f ′ . . . . . . . . . . . . . . . . . . 21 1.4.2 Réduction d’intervalles sans utiliser la dérivée . . . . . . . . . . . 25 1.5 Algorithmes d’approximation polynomiale . . . . . . . . . . . . . . . . 29 1.5.1 Approximation quadratique de la fonction f . . . . . . . . . . . . 30 1.5.2 Approximation linéaire de la fonction f ′ . . . . . . . . . . . . . . 31 1.5.3 Approximation cubique de la fonction f . . . . . . . . . . . . . . 34 *1.5.4 Utilisation de l’approximation cubique de f . . . . . . . . . . . . 35 1.6 Analyse asymptotique . . . . . . . . . . . . . . . . . . . . . . . . 36 1.6.1 Notation “grand O” et “petit o” . . . . . . . . . . . . . . . . . 36 1.6.2 Vitesse de convergence d’algorithmes itératifs . . . . . . . . . . . 38 1.7 Convergence locale quadratique de l’itération de Newton. . . . . . . . . . 40 1.7.1 Analyse de l’itération de Newton . . . . . . . . . . . . . . . . . 40 1.7.2 Preuve concise de la convergence quadratique . . . . . . . . . . . 41 1.7.3 Preuve détaillée de la convergence quadratique . . . . . . . . . . . 41 i ii TABLE DES MATIÈRES *1.8 Analyse des approximations polynômiales . . . . . . . . . . . . . . . . 43 1.8.1 Ordre de convergence de la méthode de la sécante . . . . . . . . . 43 1.8.2 Ordre de convergence de l’approximation cubique de f . . . . . . . 44 1.9 Algorithme combiné . . . . . . . . . . . . . . . . . . . . . . . . . 44 1.9.1 Algorithme de Newton modiﬁé . . . . . . . . . . . . . . . . . . 45 1.10 Région de conﬁance . . . . . . . . . . . . . . . . . . . . . . . . . 47 2 Optimisation locale de fonctions diﬀérentiables sans contrainte 51 2.1 Formulation du problème . . . . . . . . . . . . . . . . . . . . . . . 52 2.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2.1 Analyse du problème à une seule variable . . . . . . . . . . . . . 53 2.2.2 Conditions d’optimalité pour un problème à n variables . . . . . . . 55 2.3 Déduction d’une classe d’algorithmes itératifs . . . . . . . . . . . . . . 63 2.3.1 Recherche de points stationnaires. . . . . . . . . . . . . . . . . 63 2.3.2 Conditions pour la convergence . . . . . . . . . . . . . . . . . 66 2.3.3 Recherche de minima locaux faibles. . . . . . . . . . . . . . . . 76 2.4 Itération de Newton modiﬁée pour l’optimisation . . . . . . . . . . . . . 81 2.4.1 Modiﬁcation de la direction de Newton . . . . . . . . . . . . . . 82 2.4.2 Analyse du pas θ pour la direction de Newton . . . . . . . . . . . 82 2.4.3 Convergence de la méthode de Newton modiﬁée . . . . . . . . . . 84 2.4.4 Convergence de la méthode de Newton — régions de conﬁance . . . . 85 2.5 Méthodes quasi-Newton. . . . . . . . . . . . . . . . . . . . . . . . 86 2.5.1 Convergence globale . . . . . . . . . . . . . . . . . . . . . . 87 2.5.2 Vitesse de convergence . . . . . . . . . . . . . . . . . . . . . 88 2.6 Fonctions objectif quadratiques . . . . . . . . . . . . . . . . . . . . 88 2.6.1 Décomposition de Cholesky . . . . . . . . . . . . . . . . . . . 88 2.6.2 Algorithme du gradient conjugué . . . . . . . . . . . . . . . . . 90 2.7 Problèmes de moindres carrés . . . . . . . . . . . . . . . . . . . . . 93 2.7.1 Méthodes de descente pour les systèmes d’équations. . . . . . . . . 94 2.7.2 Méthodes spécialisées aux mointres carrés . . . . . . . . . . . . . 94 2.8 Mises en œuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 2.8.1 Mise en œuvre de la direction de Newton modiﬁée . . . . . . . . . 95 2.8.2 Mise en œuvre d’algorithmes de régions de conﬁance . . . . . . . . 99 2.8.3 Mise en œuvre d’un pas admissible . . . . . . . . . . . . . . . . 101 2.9 Traitement de problèmes de très grande taille . . . . . . . . . . . . . . 102 2.9.1 Gradient conjugué non-linéaire. . . . . . . . . . . . . . . . . . 103 2.9.2 Newton tronqué . . . . . . . . . . . . . . . . . . . . . . . . 105 2.10 Résumé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 2.11 Extensions et références. . . . . . . . . . . . . . . . . . . . . . . . 106 TABLE DES MATIÈRES iii 3 Programmation linéaire uploads/Management/ programmation-non-lineaire.pdf