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 lineaire

Programmation non linéaire Jean-Pierre Dussault janvier Professeur titulaire département d ? Informatique Université de Sherbrooke Sherbrooke Canada J K R C CTable des matières Préface xi Notation Introduction Préliminaires Optimisation Types d ? optima Optima locaux et globaux Optima stricts Optima isolés Remarques Conditions d ? optimalité Conditions pour un point stationnaire Conditions pour un optimum Algorithmes de descente Réduction d ? intervalle avec f ?? Réduction d ? intervalles sans utiliser la dérivée Algorithmes d ? approximation polynomiale Approximation quadratique de la fonction f Approximation linéaire de la fonction f ?? Approximation cubique de la fonction f Utilisation de l ? approximation cubique de f Analyse asymptotique Notation ??grand O ? et ??petit o ? Vitesse de convergence d ? algorithmes itératifs Convergence locale quadratique de l ? itération de Newton Analyse de l ? itération de Newton Preuve concise de la convergence quadratique Preuve détaillée de la convergence quadratique i Cii TABLE DES MATIÈRES Analyse des approximations polynômiales Ordre de convergence de la méthode de la sécante Ordre de convergence de l ? approximation cubique de f Algorithme combiné Algorithme de Newton modi ?é Région de con ?ance Optimisation locale de fonctions di ?érentiables sans contrainte Formulation du problème Conditions d ? optimalité Analyse du problème à une seule variable Conditions d ? optimalité pour un problème à n variables Déduction d ? une classe d ? algorithmes itératifs Recherche de points stationnaires Conditions pour la convergence Recherche de minima locaux faibles Itération de Newton modi ?ée pour l ? optimisation Modi ?cation de la direction de Newton Analyse du pas pour la direction de Newton Convergence de la méthode de Newton modi ?ée Convergence de la méthode de Newton ?? régions de con ?ance Méthodes quasi-Newton Convergence globale Vitesse de convergence Fonctions objectif quadratiques Décomposition de Cholesky Algorithme du gradient conjugué Problèmes de moindres carrés Méthodes de descente pour les systèmes d ? équations Méthodes spécialisées aux mointres carrés Mises en ?uvre Mise en ?uvre de la direction de Newton modi ?ée Mise en ?uvre d ? algorithmes de régions de con ?ance Mise en ?uvre d ? un pas admissible Traitement de problèmes de très grande taille Gradient conjugué non-linéaire Newton tronqué Résumé Extensions et références CTABLE DES MATIÈRES iii Programmation linéaire Formulation du problème Solutions de base réalisables Condition d ? optimalité Algorithme du simplexe Dualité Dégénérescence Un exemple de cyclage dans l ? algorithme du simplexe Règles d ? anti-cyclage Convergence ?nie de l ? algorithme du simplexe Implantation numérique de l ? algorithme du simplexe Utilisation de la décomposition LU Utilisation de la décomposition QR Dégénérescence numérique Comment obtenir la première solution de base réalisable Résumé Extensions et références Optimisation di ?érentiable avec contraintes linéaires Énoncé du problème Conditions d ? optimalité pour les points stationnaires Formulation inspirée de la programmation linéaire Formulation sous forme de projection Conditions de Karush-Kuhn-Tucker Conditions pour les contraintes d ? égalité Conditions pour les contraintes d ? inégalité Exemples Remarques générales sur les algorithmes Algorithmes de directions