François Glineur Etude des méthodes de point intérieur appliquées à la programm

François Glineur Etude des méthodes de point intérieur appliquées à la programmation linéaire et à la programmation semidéfinie A.1 Introduction - Présentation générale Page 1 FRANÇOIS GLINEUR ETUDE DES METHODES DE POINT INTERIEUR APPLIQUEES A LA PROGRAMMATION LINEAIRE ET A LA PROGRAMMATION SEMIDEFINIE François Glineur Etude des méthodes de point intérieur appliquées à la programmation linéaire et à la programmation semidéfinie A.1 Introduction - Présentation générale Page 2 A. INTRODUCTION A.1 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 efficace de résolution : l'algorithme du simplexe, découvert par Dantzig en 1947. 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 1984 : 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
Efficacité 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)
Efficacité 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 non- liné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 efficace. L’objectif de ce travail de fin 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éfinie, possédant de nombreuses applications. Enfin, nous terminerons en décrivant une implémentation sur ordinateur, réalisée dans le cadre de ce travail de fin d’études, utilisant les méthodes de point intérieur appliquées à la programmation semidéfinie pour résoudre un problème de classification de données (analyse discriminante par ellipsoïdes). A.2 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. La suite sera divisée en deux parties : programmation linéaire et programmation semidéfinie. La première partie débute par un important chapitre consacré aux développements théoriques relatifs aux méthodes de point intérieur pour la programmation linéaire. En particulier, on y trouvera une présentation de la démarche conceptuelle de création de ces méthodes de point intérieur. Le chapitre suivant traitera les aspects relatifs à l’implémentation de ces méthodes sur ordinateur. En effet, l’efficacité d’un logiciel utilisant ces méthodes dépendra fortement du soin que l’on aura François Glineur Etude des méthodes de point intérieur appliquées à la programmation linéaire et à la programmation semidéfinie A.2 Introduction - Structure de ce travail de fin d’études Page 3 apporté à son implémentation. On trouvera ensuite un chapitre renfermant quelques compléments théoriques. Enfin, nous terminerons cette première partie par un chapitre fournissant les résultats de tests numériques ainsi que quelques comparaisons entre différentes méthodes et logiciels. La seconde partie débute par les développements théoriques relatifs à la programmation semidéfinie. Nous y insisterons tout particulièrement sur le parallèle avec la programmation linéaire qui peut être établi pour la plupart des concepts. Le chapitre suivant fournira une série de problèmes d’optimisation modélisables par la programmation semidéfinie. Nous terminerons cette partie par la présentation de l’implémentation que nous avons réalisée pour résoudre un problème de classification par la programmation semidéfinie. Enfin, nous clôturerons ce travail par un chapitre dédié aux conclusions, suivi des références, d’une bibliographie et des annexes. François Glineur Etude des méthodes de point intérieur appliquées à la programmation linéaire et à la programmation semidéfinie A.3 Introduction - Table des matières Page 4 A.3 TABLE DES MATIERES A. INTRODUCTION..................................................................................................................................2 A.1 Présentation générale ....................................................................................................................2 A.2 Structure de ce travail de fin d’études............................................................................................2 A.3 Table des matières..........................................................................................................................4 A.4 Table des illustrations ....................................................................................................................5 B. GENERALITES....................................................................................................................................6 B.1 Recherche opérationnelle et programmation mathématique .........................................................6 B.2 Programmation linéaire.................................................................................................................7 B.3 Méthode du simplexe......................................................................................................................8 B.4 Première présentation des méthodes de point intérieur.................................................................9 B.5 Historique du domaine.................................................................................................................11 PREMIERE PARTIE LES METHODES DE POINT INTERIEUR POUR LA PROGRAMMATION LINEAIRE..... 13 C. DEVELOPPEMENTS THEORIQUES....................................................................................................14 C.1 Dualité..........................................................................................................................................14 C.2 Démarche de conception des méthodes de point intérieur...........................................................16 C.3 Classification des méthodes de point intérieur.............................................................................24 C.4 Description détaillée de quatre méthodes ....................................................................................27 C.5 Se passer d’un point de départ admissible...................................................................................32 C.6 Complexité....................................................................................................................................33 C.7 Généralisation par Nesterov et Nemirovsky.................................................................................35 D. ASPECTS RELATIFS A L’IMPLEMENTATION ....................................................................................37 D.1 Résolution du système d’équations linéaires................................................................................37 D.2 Formulation du modèle................................................................................................................41 D.3 Choix des paramètres...................................................................................................................43 D.4 Technique de prédiction-correction de Mehrotra ........................................................................44 E. COMPLEMENTS................................................................................................................................47 E.1 Théorème de Goldman-Tucker et la partition optimale ...............................................................47 E.2 Forme du chemin central et nombre de condition........................................................................48 E.3 Convergence superlinéaire...........................................................................................................48 E.4 Terminaison finie..........................................................................................................................49 E.5 Technique du problème homogène auto-dual ..............................................................................49 F. RESULTATS NUMERIQUES ET PERSPECTIVES .................................................................................51 F.1 Comparaisons...............................................................................................................................51 F.2 Tests numériques..........................................................................................................................52 F.3 Directions actuelles de recherche ................................................................................................54 DEUXIEME PARTIE LES METHODES DE POINT INTERIEUR POUR LA PROGRAMMATION SEMIDEFINIE55 G. DEVELOPPEMENTS THEORIQUES....................................................................................................56 G.1 Introduction..................................................................................................................................56 G.2 Parallèle avec le cas linéaire .......................................................................................................57 G.3 Méthodes de point intérieur .........................................................................................................60 H. APPLICATIONS.................................................................................................................................62 H.1 Modélisation exacte......................................................................................................................62 H.2 Relaxations...................................................................................................................................64 I. CONCLUSIONS......................................................................................................................................66 I.1 Programmation linéaire...............................................................................................................66 I.2 Programmation non-linéaire et programmation semidéfinie.......................................................66 I.3 Remarque finale ...........................................................................................................................67 J. REFERENCES ET BIBLIOGRAPHIE.......................................................................................................68 J.1 Références ....................................................................................................................................68 François Glineur Etude des méthodes de point intérieur appliquées à la programmation linéaire et à la programmation semidéfinie A.4 Introduction - Table des illustrations Page 5 J.2 Bibliographie................................................................................................................................70 A.4 TABLE DES ILLUSTRATIONS FIGURE B-1 - EXEMPLE DE POLYEDRE ADMISSIBLE (CAS A DEUX DIMENSIONS) ..................................................8 FIGURE B-2 - CONVERGENCE DES ITERES D'UNE METHODE DE POINT INTERIEUR ..............................................10 FIGURE C-1 - PROGRESSION POTENTIELLE D'UN ITERE CENTRAL ET D'UN ITERE PEU CENTRAL..........................17 FIGURE C-2 - UN CAS SIMPLE D'OPTIMISATION..................................................................................................17 FIGURE C-3 - PROGRESSION AVEC MISE A L'ECHELLE AFFINE............................................................................18 FIGURE C-4 - UNE ITERATION DE LA METHODE DE NEWTON POUR UNE FONCTION SCALAIRE ...........................19 FIGURE C-5 - EXEMPLE DE CHEMIN CENTRAL A DEUX DIMENSIONS ..................................................................21 FIGURE C-6 - DEUX PAS DE NEWTON VERS DEUX CIBLES DU CHEMIN CENTRAL................................................23 FIGURE C-7 - UN PAS VISANT L'OPTIMUM ET UN PAS VISANT UNE CIBLE SUR LE CHEMIN CENTRAL ...................23 FIGURE C-8 - QUELQUES ITERES D'UNE METHODE DE SUIVI DE CHEMIN............................................................26 FIGURE C-9 - METHODE DE SUIVI DE CHEMIN A PAS COURT EN AXES XS...........................................................28 FIGURE C-10 - METHODE DE SUIVI DE CHEMIN A PREDICTION-CORRECTION EN AXES XS ..................................29 FIGURE C-11 - METHODE DE SUIVI DE CHEMIN A PAS LONG EN AXES XS...........................................................30 FIGURE D-1 - DENSITE D'UNE MATRICE TYPIQUE D'UN PROBLEME REEL............................................................37 FIGURE D-2 - DENSITE DE M ET DE SON FACTEUR DE CHOLEVSKY...................................................................39 FIGURE D-3 - FACTORISATIONS MINIMUM ORDERING ET MINIMUM LOCAL FILL IN..............................................40 FIGURE E-1 - EXEMPLE DE CHEMIN CENTRAL COMPRENANT UN TOURNANT BRUSQUE.....................................48 FIGURE G-1 - EXEMPLE D'OPTIMISATION SUR UN SPECTRAEDRE A DEUX DIMENSIONS ......................................57 François Glineur Etude des méthodes de point intérieur appliquées à la programmation linéaire et à la programmation semidéfinie B.1 Généralités - Recherche opérationnelle et programmation mathématique Page 6 B. GENERALITES B.1 RECHERCHE OPERATIONNELLE ET PROGRAMMATION MATHEMATIQUE B.1.1 Présentation et définitions Les définitions de la recherche opérationnelle que l’on rencontre couramment ressemblent généralement à
    
 

  
 



 


  
  
  
  

 



  


  

 

 
  



 
!"
Cette discipline trouve ses origines durant la seconde guerre mondiale, où elle servit entre autres à élaborer des stratégies de défense aérienne et à résoudre des problèmes logistiques. Elle est à présent un outil de gestion couramment employé, et s’applique à des domaines aussi variés que l’ordonnancement de production, les systèmes de transport, la gestion des stocks, les télécommunications, etc. En tant que branche des mathématiques appliquées, elle recherche principalement des procédures de calcul efficaces et a de ce fait connu de formidables progrès suite au développement des ordinateurs modernes. Le but de la recherche opérationnelle est de modéliser une situation afin de déduire de cette représentation idéalisée la ou les meilleures décisions à prendre. La notion de « meilleure décision » correspond dans le modèle à celle qui maximise un ou plusieurs critères déterminés. C’est pourquoi le domaine mathématique de l’optimisation est étroitement lié à la recherche opérationnelle, puisqu’il s’occupe du problème de la maximisation (ou uploads/Management/ reference-i-pm.pdf

Documents similaires

Méthodes de prévision Pr Lotfi Bouzaïane Pr Rim Mouelhi Projet de M2PA Universi 0 0

Support de cours de Analyse Des Données 1 Année académique 2021 – 2022 MASTER 1 0 0

See discussions, stats, and author profiles for this publication at: https://ww 0 0

Faculté d’Ingénierie SYLLABUS DU COURS GELE4311 Microprocesseurs Préalable : GE 0 0

1. Quelques problèmes d’optimisation en ingénierie 2. Méthodes sans gradient dé 0 0

__________________________________________________________________________ Reco 0 0

Coordinateurs Christophe Hermon - chermon@ctcpa.org Graziella Midelet - graziel 0 0

Abstrait: Les fuites de gaz peuvent provoquer des incidents majeurs entraînant 0 0

2 Auteurs : Marie-Hélène Lemieux et le comité Pédagogie, tâche et règles départ 0 0

09/11/2022 15:54 Extreme programming — Wikipédia https://fr.wikipedia.org/wiki/ 0 0

• Détails
• Publié le Mar 28, 2022
• Catégorie Management
• Langue French
• Taille du fichier 0.8020MB