University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur D BENTERKI |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheEtude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire / Linda Menniche
Titre : Etude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire Type de document : texte imprimé Auteurs : Linda Menniche, Auteur ; D BENTERKI, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (78 f.) Format : 29 cm Catégories : Mathématique Mots-clés : Programmation linéaire,
Méthode de Points Intérieurs,
Méthode
barrière logarithmique,
Fonction majorante.Index. décimale : 510 Mathématique Résumé : Résumé :
Ce travail concerne l'étude théorique, algorithmique et numérique d'une
méthode barrière logarithmique pour résoudre un problème de
programmation linéaire (PL). Nous mettons l'accent sur le calcul de la direction
moyennant l'approche de Newton, et le calcul du pas de déplacement en
utilisant de nouvelles fonctions majorantes dans le but de réduire le coût de
calcul. Des résultats théoriques sont présentés donnant lieu à l'existence et
l'unicité de la solution optimale du problème approché de (PL) ainsi que sa
convergence vers celle de (PL). Ce travail est consolidé par des tests
numériques réalisés sur l'algorithme obtenu.
Note de contenu : Table des matières
Introduction 3
1 Préliminaires et notions fondamentales 7
1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Ensembles et fonctions affines . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Notions de convexité . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Convexité et dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Fonction barri`ere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.5 Programmation math´ematique . . . . . . . . . . . . . . . . . . . . . 13
1.2 Programmation lin´eaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Formes usuelles d’un programme linéaire . . . . . . . . . . . . . . . . . . . 19
1.3.1 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.2 Forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 Dualité en programmation lin´eaire . . . . . . . . . . . . . . . . . . . . . . . 20
2 M´ethodes de résolution d’un programme linéaire 24
2.1 Domaines d’applications de la programmation linéaire . . . . . . . . . . . . 24
2.1.1 Exemples concrets de problèmes de programmation linéaire . . . . . 26
2.2 Méthode de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.1 Caract´eristiques de l’algorithme du simplexe . . . . . . . . . . . . . 34
2.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1 M´ethodes affines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Algorithme de la méthode affine primale . . . . . . . . . . . . . . . 39
2.3.3 Méthode de réduction du potentiel . . . . . . . . . . . . . . . . . . 42
2.3.4 Méthodes de trajectoire centrale . . . . . . . . . . . . . . . . . . . . 43
2.3.5 Méthodes de trajectoire centrale primales-duales . . . . . . . . . . . 45
2.4 R´esultats de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Méthode barri`ere logarithmique via les fonctions majorantes 52
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2 Aspect théorique du problème (DLr) . . . . . . . . . . . . . . . . . . . . . 54
3.2.1 Existence de la solution du probl`eme (DLr) . . . . . . . . . . . . . 54
3.2.2 Unicité de la solution du problème (DLr) . . . . . . . . . . . . . . . 55
3.2.3 Convergence de (DLr) vers (DL) lorsque r tend vers zéro . . . . . . 56
3.3 Aspect numérique du probl`eme (DLr) . . . . . . . . . . . . . . . . . . . . 57
3.3.1 Calcul du pas de d´eplacement tk . . . . . . . . . . . . . . . . . . . . 59
3.3.2 Calcul des différentes valeurs de bt . . . . . . . . . . . . . . . . . . . 61
3.4 Fonctions majorantes de θ . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.4.1 Première fonction majorante . . . . . . . . . . . . . . . . . . . . . . 63
3.4.2 Seconde fonction majorante . . . . . . . . . . . . . . . . . . . . . . 64
3.4.3 Troisiéme fonction majorante . . . . . . . . . . . . . . . . . . . . . 65
3.5 Tests num´eriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.1 Exemples `a dimension fixe . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Exemple `a dimension variable . . . . . . . . . . . . . . . . . . . . . 72
Conclusion 73
Bibliographie 75Côte titre : DM/0122 En ligne : https://drive.google.com/file/d/11YNbdvBMZXfjDwFmTZBiBGCOU5vlXVmh/view?usp=shari [...] Format de la ressource électronique : Etude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire [texte imprimé] / Linda Menniche, Auteur ; D BENTERKI, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (78 f.) ; 29 cm.
Catégories : Mathématique Mots-clés : Programmation linéaire,
Méthode de Points Intérieurs,
Méthode
barrière logarithmique,
Fonction majorante.Index. décimale : 510 Mathématique Résumé : Résumé :
Ce travail concerne l'étude théorique, algorithmique et numérique d'une
méthode barrière logarithmique pour résoudre un problème de
programmation linéaire (PL). Nous mettons l'accent sur le calcul de la direction
moyennant l'approche de Newton, et le calcul du pas de déplacement en
utilisant de nouvelles fonctions majorantes dans le but de réduire le coût de
calcul. Des résultats théoriques sont présentés donnant lieu à l'existence et
l'unicité de la solution optimale du problème approché de (PL) ainsi que sa
convergence vers celle de (PL). Ce travail est consolidé par des tests
numériques réalisés sur l'algorithme obtenu.
Note de contenu : Table des matières
Introduction 3
1 Préliminaires et notions fondamentales 7
1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Ensembles et fonctions affines . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Notions de convexité . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Convexité et dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Fonction barri`ere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.5 Programmation math´ematique . . . . . . . . . . . . . . . . . . . . . 13
1.2 Programmation lin´eaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Formes usuelles d’un programme linéaire . . . . . . . . . . . . . . . . . . . 19
1.3.1 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.2 Forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 Dualité en programmation lin´eaire . . . . . . . . . . . . . . . . . . . . . . . 20
2 M´ethodes de résolution d’un programme linéaire 24
2.1 Domaines d’applications de la programmation linéaire . . . . . . . . . . . . 24
2.1.1 Exemples concrets de problèmes de programmation linéaire . . . . . 26
2.2 Méthode de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.1 Caract´eristiques de l’algorithme du simplexe . . . . . . . . . . . . . 34
2.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1 M´ethodes affines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Algorithme de la méthode affine primale . . . . . . . . . . . . . . . 39
2.3.3 Méthode de réduction du potentiel . . . . . . . . . . . . . . . . . . 42
2.3.4 Méthodes de trajectoire centrale . . . . . . . . . . . . . . . . . . . . 43
2.3.5 Méthodes de trajectoire centrale primales-duales . . . . . . . . . . . 45
2.4 R´esultats de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Méthode barri`ere logarithmique via les fonctions majorantes 52
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2 Aspect théorique du problème (DLr) . . . . . . . . . . . . . . . . . . . . . 54
3.2.1 Existence de la solution du probl`eme (DLr) . . . . . . . . . . . . . 54
3.2.2 Unicité de la solution du problème (DLr) . . . . . . . . . . . . . . . 55
3.2.3 Convergence de (DLr) vers (DL) lorsque r tend vers zéro . . . . . . 56
3.3 Aspect numérique du probl`eme (DLr) . . . . . . . . . . . . . . . . . . . . 57
3.3.1 Calcul du pas de d´eplacement tk . . . . . . . . . . . . . . . . . . . . 59
3.3.2 Calcul des différentes valeurs de bt . . . . . . . . . . . . . . . . . . . 61
3.4 Fonctions majorantes de θ . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.4.1 Première fonction majorante . . . . . . . . . . . . . . . . . . . . . . 63
3.4.2 Seconde fonction majorante . . . . . . . . . . . . . . . . . . . . . . 64
3.4.3 Troisiéme fonction majorante . . . . . . . . . . . . . . . . . . . . . 65
3.5 Tests num´eriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.1 Exemples `a dimension fixe . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Exemple `a dimension variable . . . . . . . . . . . . . . . . . . . . . 72
Conclusion 73
Bibliographie 75Côte titre : DM/0122 En ligne : https://drive.google.com/file/d/11YNbdvBMZXfjDwFmTZBiBGCOU5vlXVmh/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0122 DM/0122 Mémoire Bibliothéque des sciences Français Disponible
Disponible
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
