University Sétif 1 FERHAT ABBAS Faculty of Sciences
Résultat de la recherche
1 résultat(s) recherche sur le mot-clé 'Programmation linéaire Programmatio semi-Définie linéaire Méthode de trajectoire centrale'
Ajouter le résultat dans votre panier Affiner la recherche Générer le flux rss de la recherche
Partager le résultat de cette recherche
Généralisation d'une méthode de trajectoire centrale de points intérieurs pour la programmation semi- définie / Kettab.Samia
Titre : Généralisation d'une méthode de trajectoire centrale de points intérieurs pour la programmation semi- définie Type de document : texte imprimé Auteurs : Kettab.Samia, Auteur ; D BENTERKI, Directeur de thèse Editeur : Setif:UFA Année de publication : 2015 Importance : 1 vol (81 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation linéaire
Programmatio semi-Définie linéaire
Méthode de trajectoire centraleIndex. décimale : 519 Mathématiques appliquées, probabilités (statistiques mathématiques) Résumé : Les méthodes primales- duales de points intérieurs ont été bien connues les plus efficaces pour résoudre les classes de large taille de problèmes d' optimisation tel que problème optimalisation linéaire problème d'optimisation quadratique problème d'optimisation semi- définie et problème d'optimisation convexe ces méthodes possèdent une convergence polynomiale et sont crédités d'un bon comportement numérique dans notre étude nous proposons une nouvelle méthode de trajectoire centrale primale- duale pour la programmation semi- définie linéaire ou on introduit une relaxation du paramétre barriére afin de donner plus de flexibilité aux aspects théoriques et numériques des problémes perturbés et d'accélérer la converqence de l'algorithmece propos sont confirmés pardes tests numériques montrant le bon comportemment de l'algorithme proposé Note de contenu :
Sommaire
Introduction 4
1 Analyse convexe et programmation mathématique 8
1.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Produit scalaire et normes . . . . . . . . . . . . . . . . . . . . . . 9
1.1.2 Matrices (semi-) dé…nies positives . . . . . . . . . . . . . . . . . . 9
1.2 Analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Ensembles a¢ nes . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3 Cônes convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.4 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.1 Dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.2 ClassiÂ…cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.3 Principaux résultas d’existence et d’unicité . . . . . . . . . . . . . 20
1.3.4 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4.1 Méthodes de résolution d’un programme linéaire . . . . . . . . . . 23
2 Programmation semi-dé…nie 34
2.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.1 Problème primal . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.2 Problème dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2 Domaines dÂ’applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.1 Problèmes de min-max des valeurs propres . . . . . . . . . . . . . 38
2.2.2 Norme spectrale dÂ’une matrice . . . . . . . . . . . . . . . . . . . . 39
2.2.3 Programmation quadratique avec des contraintes quadratiques . . 39
2.2.4 Problème de programmation non linéaire . . . . . . . . . . . . . . 41
2.3 Dualité en programmation semi-dé…nie . . . . . . . . . . . . . . . . . . . 42
2.3.1 Dualité faible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.2 Dualité forte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4 Complémentarité en SDP . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.5 Méthodes de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.5.1 Méthodes de réduction du potentiel . . . . . . . . . . . . . . . . . 47
2.5.2 Méthodes de trajectoire centrale de type primal-dual . . . . . . . 49
3 Méthode de trajectoire centrale pour la programmation semi-dé…nie 52
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2 Pénalisation logarithmique . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2.1 Etude du problème perturbé (SDP) . . . . . . . . . . . . . . . . 54
3.2.2 Conditions d’optimalité pour (SDP) . . . . . . . . . . . . . . . . 56
3.3 Méthode de trajectoire centrale . . . . . . . . . . . . . . . . . . . . . . . 57
3.3.1 Principe de la méthode de trajectoire centrale . . . . . . . . . . . 57
3.3.2 Algorithme de trajectoire centrale T . . . . . . . . . . . . . . . . 59
3.4 Relaxation du paramètre . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.1 Calcul de la direction . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.4.2 Calcul du pas de déplacement . . . . . . . . . . . . . . . . . . . . 65
3.4.3 Algorithme de trajectoire centrale TW . . . . . . . . . . . . . . . . 67
3.4.4 Convergence de lÂ’algorithme . . . . . . . . . . . . . . . . . . . . . 68
3.5 Tests Numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.5.1 Exemples à taille …xe . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.5.2 Exemples à taille variable . . . . . . . . . . . . . . . . . . . . . . 74
3.5.3 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Conclusion 76
Bibliographie 77
Côte titre : DM/0134 En ligne : https://drive.google.com/file/d/11JDp1b0DJZVWc1p53ROS-ZzphBbn4MLq/view?usp=shari [...] Format de la ressource électronique : Généralisation d'une méthode de trajectoire centrale de points intérieurs pour la programmation semi- définie [texte imprimé] / Kettab.Samia, Auteur ; D BENTERKI, Directeur de thèse . - [S.l.] : Setif:UFA, 2015 . - 1 vol (81 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation linéaire
Programmatio semi-Définie linéaire
Méthode de trajectoire centraleIndex. décimale : 519 Mathématiques appliquées, probabilités (statistiques mathématiques) Résumé : Les méthodes primales- duales de points intérieurs ont été bien connues les plus efficaces pour résoudre les classes de large taille de problèmes d' optimisation tel que problème optimalisation linéaire problème d'optimisation quadratique problème d'optimisation semi- définie et problème d'optimisation convexe ces méthodes possèdent une convergence polynomiale et sont crédités d'un bon comportement numérique dans notre étude nous proposons une nouvelle méthode de trajectoire centrale primale- duale pour la programmation semi- définie linéaire ou on introduit une relaxation du paramétre barriére afin de donner plus de flexibilité aux aspects théoriques et numériques des problémes perturbés et d'accélérer la converqence de l'algorithmece propos sont confirmés pardes tests numériques montrant le bon comportemment de l'algorithme proposé Note de contenu :
Sommaire
Introduction 4
1 Analyse convexe et programmation mathématique 8
1.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Produit scalaire et normes . . . . . . . . . . . . . . . . . . . . . . 9
1.1.2 Matrices (semi-) dé…nies positives . . . . . . . . . . . . . . . . . . 9
1.2 Analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Ensembles a¢ nes . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3 Cônes convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.4 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.1 Dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3.2 ClassiÂ…cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.3 Principaux résultas d’existence et d’unicité . . . . . . . . . . . . . 20
1.3.4 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4.1 Méthodes de résolution d’un programme linéaire . . . . . . . . . . 23
2 Programmation semi-dé…nie 34
2.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.1 Problème primal . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.2 Problème dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2 Domaines dÂ’applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2.1 Problèmes de min-max des valeurs propres . . . . . . . . . . . . . 38
2.2.2 Norme spectrale dÂ’une matrice . . . . . . . . . . . . . . . . . . . . 39
2.2.3 Programmation quadratique avec des contraintes quadratiques . . 39
2.2.4 Problème de programmation non linéaire . . . . . . . . . . . . . . 41
2.3 Dualité en programmation semi-dé…nie . . . . . . . . . . . . . . . . . . . 42
2.3.1 Dualité faible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.2 Dualité forte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4 Complémentarité en SDP . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.5 Méthodes de résolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.5.1 Méthodes de réduction du potentiel . . . . . . . . . . . . . . . . . 47
2.5.2 Méthodes de trajectoire centrale de type primal-dual . . . . . . . 49
3 Méthode de trajectoire centrale pour la programmation semi-dé…nie 52
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2 Pénalisation logarithmique . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2.1 Etude du problème perturbé (SDP) . . . . . . . . . . . . . . . . 54
3.2.2 Conditions d’optimalité pour (SDP) . . . . . . . . . . . . . . . . 56
3.3 Méthode de trajectoire centrale . . . . . . . . . . . . . . . . . . . . . . . 57
3.3.1 Principe de la méthode de trajectoire centrale . . . . . . . . . . . 57
3.3.2 Algorithme de trajectoire centrale T . . . . . . . . . . . . . . . . 59
3.4 Relaxation du paramètre . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4.1 Calcul de la direction . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.4.2 Calcul du pas de déplacement . . . . . . . . . . . . . . . . . . . . 65
3.4.3 Algorithme de trajectoire centrale TW . . . . . . . . . . . . . . . . 67
3.4.4 Convergence de lÂ’algorithme . . . . . . . . . . . . . . . . . . . . . 68
3.5 Tests Numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.5.1 Exemples à taille …xe . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.5.2 Exemples à taille variable . . . . . . . . . . . . . . . . . . . . . . 74
3.5.3 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Conclusion 76
Bibliographie 77
Côte titre : DM/0134 En ligne : https://drive.google.com/file/d/11JDp1b0DJZVWc1p53ROS-ZzphBbn4MLq/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0134 DM/0134 Thèse Bibliothéque des sciences Français Disponible
Disponible