Remerciez-le!

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

Reference i pm François Glineur Etude des méthodes de point intérieur appliquées à la programmation linéaire et à la programmation semidé ?nie FRANÇOIS GLINEUR ETUDE DES METHODES DE POINT INTERIEUR APPLIQUEES A LA PROGRAMMATION LINEAIRE ET A LA PROGRAMMAT

François Glineur Etude des méthodes de point intérieur appliquées à la programmation linéaire et à la programmation semidé ?nie FRANÇOIS GLINEUR ETUDE DES METHODES DE POINT INTERIEUR APPLIQUEES A LA PROGRAMMATION LINEAIRE ET A LA PROGRAMMATION SEMIDEFINIE A Introduction - Présentation générale Page CFrançois Glineur Etude des méthodes de point intérieur appliquées à la programmation linéaire et à la programmation semidé ?nie A INTRODUCTION A PRESENTATION GENERALE La programmation mathématique branche de l ? optimisation s ? occupe de la minimisation sous contraintes d ? une fonction à plusieurs variables schéma très général s ? appliquant à de nombreuses situations pratiques dans beaucoup de domaines minimisation de coûts de durées etc Dans le cas d'une fonction et de contraintes linéaires programmation linéaire on dispose d'une méthode e ?cace de résolution l'algorithme du simplexe découvert par Dantzig en Cet algorithme a connu depuis lors de nombreuses améliorations et est utilisé dans la majorité des logiciels commerciaux Cependant un nouveau type de méthodes de résolution a fait son apparition en les méthodes de point intérieur La plupart des idées sous-jacentes à ces méthodes proviennent du domaine de la programmation non-linéaire Parmi leurs avantages citons E ?cacité théorique il est possible de prouver que ces méthodes s ? exécutent en temps polynomial ce qui n'est pas le cas de l'algorithme du simplexe de nature exponentielle E ?cacité pratique les temps de calcul de ces méthodes sont compétitifs et battent l'algorithme du simplexe dans le cas de problèmes de grande taille Traitement de très grands problèmes ces méthodes permettent de résoudre des problèmes de très grande taille qu ? aucun autre algorithme connu ne pourrait traiter en un temps acceptable Adaptation au cas non-linéaire il est possible d'adapter ces méthodes à la programmation nonlinéaire plus particulièrement à la programmation convexe ce qui permet de traiter de nouveaux types de problèmes pour lesquels on ne connaissait jusqu'à présent aucune méthode de résolution e ?cace L ? objectif de ce travail de ?n d ? études est de donner un aperçu de ce domaine relativement récent en fournissant une description claire et compréhensible de ces méthodes tant du point de vue théorique que de celui de leur implémentation sur ordinateur et de leurs performances pratiques Nous nous attacherons d ? abord à l ? examen du cas linéaire le plus étudié et le plus utilisé avant de nous concentrer sur un cas particulier important de la programmation non-linéaire la programmation semidé ?nie possédant de nombreuses applications En ?n nous terminerons en décrivant une implémentation sur ordinateur réalisée dans le cadre de ce travail de ?n d ? études utilisant les méthodes de point intérieur appliquées à la programmation semidé ?nie pour résoudre un problème de classi ?cation de données analyse discriminante par ellipso? des A STRUCTURE DE CE TRAVAIL DE FIN D ? ETUDES Après cette brève introduction nous consacrerons un premier chapitre à quelques généralités sur le domaine que nous allons étudier ainsi qu ? à quelques rappels au sujet de la méthode du simplexe