Mémoire Online: Etude de quelques algorithmes de points intérieurs pour la programmation convexe

Sommaire: Etude de quelques algorithmes de points intérieurs pour la programmation convexe

LIST OF TABLES
LIST OF FIGURES
Introduction
I PRÉLIMINAIRES ET NOTIONS FONDAMENTALES
1.1 Eléments d’analyse convexe
1.1.1 Notions de convexité
1.1.2 Convexité et Dérivée
1.2 Programmation mathématique
1.2.1 Classi…cation des problemes d’optimisation
1.2.2 Quali…cation des contraintes
1.3 Résolution d’un programme mathématique
1.3.1 Existence & Unicité
1.3.2 Conditions d’’optimalitéé
1.3.3 Méthode de Newton pour résoudre un systeme non linéaire
1.3.4 Les méthodes de directions admissibles
1.3.5 Méthodes de résolution d’un programme mathématique
II MÉTHODES DE POINTS INTÉRIEURS DE TYPE NEWTONIENNE POUR RÉSOUDRE UN PROGRAMME QUADRATIQUE CONVEXE (CQP)
2.1 Méthode de la trajectoire centrale non réalisable pour la (CQP) .
2.1.1 Présentation et principe de la méthode
2.1.2 Algorithme (Méthode de la trajectoire centrale non réalisable)
2.1.3 Convergence de l’algorithme
2.1.4 Tests Numériques
2.2 Méthode de la trajectoire centrale réalisable pour (CQP)
2.2.1 Déscription et principe de la méthode
2.2.2 Algorithme ( Méthode de la trajectoire centrale réalisable )
2.3 Méthode de la trajectoire centrale réalisable améliorée pour (CQP)
2.3.1 Description de la méthode
2.3.2 Algorithme ( Méthode de la trajectoire centrale réalisable améliorée )
2.3.3 Etude de la convergence
2.3.4 Tests Numériques
III ALGORITHMES DE RÉSOLUTION D’UN PROBLEME DE COMPLÉMENTARITÉ LINÉAIRE (LCP)
3.1 Méthode de Karmarkar
3.1.1 Principe de la méthode
3.1.2 Etude de la convergence
3.2 Extension de la méthode de karmarkar
3.2.1 Introduction
3.2.2 Présentation du probleme
3.2.3 Préparation de l’algorithme
3.2.4 Algorithme (Extension d’une méthode projective pour résoudre (LCP))
3.2.5 Convergence de l’algorithme
3.2.6 Tests Numériques
3.3 Algorithme à petit pas pour (LCP)
3.3.1 Introduction
3.3.2 Présentation du probleme
3.3.3 Direction de descente
3.3.4 Algorithme (Méthode de la trajectoire centrale à petit pas pour résoudre LCP)
3.3.5 Etude de la convergence
3.3.6 Tests numériques
IV ALGORITHME DE POINTS INTÉRIEURS POUR UN PROBLEME D’OPTIMISATION SEMI DÉFINI (SDO) BASÉ SUR UNE NOUVELLE FONCTION NOYAU
4.1 Déscription de l’algorithme
4.1.1 Méthode de la trajectoire centrale
4.1.2 Direction de descente
4.1.3 Algorithme générique de points intérieurs pour (SDO)
4.2 Fonction noyau et ses propriétés
4.3 Convergence de l’algorithme
4.3.1 Le pas de déplacement
4.3.2 Diminution de la fonction de proximité
4.3.3 Les bornes d’itération
Conclusion
Annexe
Bibliographie

♣ Extrait du mémoire

Introduction
La programmation mathématique, branche de l’’optimisation, s’’occupe de la minimisation (maximisation) 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 effcace 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 points intérieurs. La plupart des idées sous-jacentes à ces méthodes proviennent du domaine de la programmation non linéaire. Parmi leurs avantages, citons 1. Effcacité 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).
2. Effcacité pratique : les temps de calcul et de réponse de ces méthodes sont compétitifs (et battent l’algorithme du simplexe dans le cas de problemes de grande taille).
3. Traitement de tress grands problemes : ces méthodes permettent de résoudre des problemes de trŁs grande taille qu’aucun autre algorithme connu ne pourrait traiter en un temps acceptable.
4. Adaptation au cas non linéaire : il est possible d’adapter ces méthodes à la programmation non linéaire, plus particulierement à la programmation convexe, ce qui permet de traiter de nouveaux types de problemes pour lesquels on ne connaissait jusqu’à présent aucune méthode de résolution efficace.
Nous allons à présent donner un bref aperçu historique du domaine de la programmation mathématique, a…n de situer la découverte des méthodes de points intérieurs dans son contexte.
………..