University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'éditeur
Setif:UFA |
Documents disponibles chez cet éditeur
Ajouter le résultat dans votre panier Affiner la recherche
Etude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire / Menniche, Linda
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 : Menniche, Linda, Auteur Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (77 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
Méthode de Points Intérieurs
Méthode
barrière logarithmique
Fonction majoranteIndex. décimale : 519 Mathématiques appliquées, probabilités (statistiques mathématiques) 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 : Sommaire
Introduction 3
1 Préliminaires et notions fondamentales 7
1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Ensembles et fonctions affnes . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Notions de convexité . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Convexité et dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Fonction barriére . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.5 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . 13
1.2 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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éaire . . . . . . . . . . . . . . . . . . . . . . . 20
2 Méthodes 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 problemes de programmation lineaire . . . . . 26
2.2 Methode de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.1 Caractéristiques de l'algorithme du simplexe . . . . . . . . . . . . . 34
2.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1 Méthodes affnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Algorithme de la méthode affne 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ésultats de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Méthode barriére 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éme (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éme (DLr) . . . . . . . . . . . . . . . . . . . . 57
3.3.1 Calcul du pas de déplacement tk . . . . . . . . . . . . . . . . . . . . 59
3.3.2 Calcul des différentes valeurs debt
. . . . . . . . . . . . . . . . . . . 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ériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.1 Exemples a dimension xe . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Exemple a dimension variable . . . . . . . . . . . . . . . . . . . . . 72
Conclusion 73
Bibliographie 75Côte titre : DM/0122 Etude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire [texte imprimé] / Menniche, Linda, Auteur . - [S.l.] : Setif:UFA, 2017 . - 1 vol (77 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
Méthode de Points Intérieurs
Méthode
barrière logarithmique
Fonction majoranteIndex. décimale : 519 Mathématiques appliquées, probabilités (statistiques mathématiques) 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 : Sommaire
Introduction 3
1 Préliminaires et notions fondamentales 7
1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Ensembles et fonctions affnes . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Notions de convexité . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Convexité et dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Fonction barriére . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.5 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . 13
1.2 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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éaire . . . . . . . . . . . . . . . . . . . . . . . 20
2 Méthodes 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 problemes de programmation lineaire . . . . . 26
2.2 Methode de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.1 Caractéristiques de l'algorithme du simplexe . . . . . . . . . . . . . 34
2.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1 Méthodes affnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Algorithme de la méthode affne 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ésultats de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Méthode barriére 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éme (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éme (DLr) . . . . . . . . . . . . . . . . . . . . 57
3.3.1 Calcul du pas de déplacement tk . . . . . . . . . . . . . . . . . . . . 59
3.3.2 Calcul des différentes valeurs debt
. . . . . . . . . . . . . . . . . . . 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ériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.1 Exemples a dimension xe . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Exemple a dimension variable . . . . . . . . . . . . . . . . . . . . . 72
Conclusion 73
Bibliographie 75Côte titre : DM/0122 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MD/0122 MD/0122 Mémoire Bibliothéque des sciences Français Disponible
DisponibleEtude théorique et numérique d'une méthode non réalisable de points intérieurs pour l'optimisation linéaire / Boussoualim ,Amel
Titre : Etude théorique et numérique d'une méthode non réalisable de points intérieurs pour l'optimisation linéaire Type de document : texte imprimé Auteurs : Boussoualim ,Amel, Auteur ; Kettab.Samia, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (60 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
Méthode de points intérieurs
Fonction noyauIndex. décimale : 510 Mathématique Résumé : Dans ce travail, on s'intéresse à l'étude d'une méthode de points intérieurs non
réalisable proposée par A.Asadi et C.Roos pour résoudre les problèmes de la
programmation linéaire. Cette méthode basée sur une nouvelle classe de direction de
Newton et d'une nouvelle mesure de proximité introduite par une fonction Noyau. Dans
une première étape, une formulation du problème initial à un problème perturbé tout en
évitant le problème d'initialisation. D'autre part, On a établi avec succès l'implémentation
numérique de cette méthode et on a effectué une étude comparative avec d'autre
algorithme de trajectoire centrale pour trouver une solution optimale.Note de contenu :
Sommaire
Introduction 3
1 Notion d’analyse convexe et programmation mathématique 6
1.1 Notions élémentaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Ensembles et fonctions convexes . . . . . . . . . . . . . . . . . . . 6
1.2.2 Caractérisation d’une fonction convexe di¤érentiable . . . . . . . 9
1.3 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Classi…cation d’un programme mathématique . . . . . . . . . . . 11
1.3.2 QualiÂ…cation des contraintes . . . . . . . . . . . . . . . . . . . . . 11
1.3.3 Principaux résultats d’existence et d’unicité . . . . . . . . . . . . 12
1.3.4 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Programmation Linéaire 13
2.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Formes usuelles d’un programme linéaire . . . . . . . . . . . . . . 14
2.1.2 Dual d’un programme linéaire . . . . . . . . . . . . . . . . . . . . 15
2.2 Résolution d’un programme linéaire . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 Méthode de point intérieurs . . . . . . . . . . . . . . . . . . . . . 18
2.2.3 Etude la convergence . . . . . . . . . . . . . . . . . . . . . . . . . 26
1
3 Méthode de point intérieur non réalisable pour (PL) 27
3.1 Méthode de trajectoire centrale via une fonction noyau . . . . . . . . . . 27
3.1.1 Fonction noyau et sa qualiÂ…cation . . . . . . . . . . . . . . . . . . 27
3.1.2 Présentation de la méthode . . . . . . . . . . . . . . . . . . . . . 28
3.1.3 Analyse de la complexité de l’algorithme . . . . . . . . . . . . . . 36
3.2 Méthode de points intérieurs non réalisable pour (PL) . . . . . . . . . . . 38
3.2.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.2 La trajectoire central des problèmes perturbés. . . . . . . . . . . . 39
3.2.3 Analyse de Complexité . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3 Expérimentation numérique . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3.1 Exemple traités . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3.2 Méthode de trajectoire centrale TC . . . . . . . . . . . . . . . . . 52
3.3.3 Méthode de trajectoire centrale via une fonction noyau FIPMs . 54
3.3.4 Méthode de trajectoire centrale non réalisable IIPMs . . . . . . 55
3.3.5 Commentaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Conclusion 57
Côte titre : MAM/0289 En ligne : https://drive.google.com/file/d/1hZAuEQuVYaZjWeryZ-kdhad_hbtk_Eg1/view?usp=shari [...] Format de la ressource électronique : Etude théorique et numérique d'une méthode non réalisable de points intérieurs pour l'optimisation linéaire [texte imprimé] / Boussoualim ,Amel, Auteur ; Kettab.Samia, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (60 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
Méthode de points intérieurs
Fonction noyauIndex. décimale : 510 Mathématique Résumé : Dans ce travail, on s'intéresse à l'étude d'une méthode de points intérieurs non
réalisable proposée par A.Asadi et C.Roos pour résoudre les problèmes de la
programmation linéaire. Cette méthode basée sur une nouvelle classe de direction de
Newton et d'une nouvelle mesure de proximité introduite par une fonction Noyau. Dans
une première étape, une formulation du problème initial à un problème perturbé tout en
évitant le problème d'initialisation. D'autre part, On a établi avec succès l'implémentation
numérique de cette méthode et on a effectué une étude comparative avec d'autre
algorithme de trajectoire centrale pour trouver une solution optimale.Note de contenu :
Sommaire
Introduction 3
1 Notion d’analyse convexe et programmation mathématique 6
1.1 Notions élémentaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Ensembles et fonctions convexes . . . . . . . . . . . . . . . . . . . 6
1.2.2 Caractérisation d’une fonction convexe di¤érentiable . . . . . . . 9
1.3 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Classi…cation d’un programme mathématique . . . . . . . . . . . 11
1.3.2 QualiÂ…cation des contraintes . . . . . . . . . . . . . . . . . . . . . 11
1.3.3 Principaux résultats d’existence et d’unicité . . . . . . . . . . . . 12
1.3.4 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Programmation Linéaire 13
2.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Formes usuelles d’un programme linéaire . . . . . . . . . . . . . . 14
2.1.2 Dual d’un programme linéaire . . . . . . . . . . . . . . . . . . . . 15
2.2 Résolution d’un programme linéaire . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 Méthode de point intérieurs . . . . . . . . . . . . . . . . . . . . . 18
2.2.3 Etude la convergence . . . . . . . . . . . . . . . . . . . . . . . . . 26
1
3 Méthode de point intérieur non réalisable pour (PL) 27
3.1 Méthode de trajectoire centrale via une fonction noyau . . . . . . . . . . 27
3.1.1 Fonction noyau et sa qualiÂ…cation . . . . . . . . . . . . . . . . . . 27
3.1.2 Présentation de la méthode . . . . . . . . . . . . . . . . . . . . . 28
3.1.3 Analyse de la complexité de l’algorithme . . . . . . . . . . . . . . 36
3.2 Méthode de points intérieurs non réalisable pour (PL) . . . . . . . . . . . 38
3.2.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.2 La trajectoire central des problèmes perturbés. . . . . . . . . . . . 39
3.2.3 Analyse de Complexité . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3 Expérimentation numérique . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3.1 Exemple traités . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3.2 Méthode de trajectoire centrale TC . . . . . . . . . . . . . . . . . 52
3.3.3 Méthode de trajectoire centrale via une fonction noyau FIPMs . 54
3.3.4 Méthode de trajectoire centrale non réalisable IIPMs . . . . . . 55
3.3.5 Commentaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Conclusion 57
Côte titre : MAM/0289 En ligne : https://drive.google.com/file/d/1hZAuEQuVYaZjWeryZ-kdhad_hbtk_Eg1/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0289 MAM/0289 Mémoire Bibliothéque des sciences Français Disponible
DisponibleEtude théorique et numérique des méthodes de points intérieurs de type trajectoire centrale pour la programmation semi-définie linéaire / Imene Touil
Titre : Etude théorique et numérique des méthodes de points intérieurs de type trajectoire centrale pour la programmation semi-définie linéaire Type de document : texte imprimé Auteurs : Imene Touil ; D. Benterki, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (89 f.) Format : 29 cm Catégories : Mathématique Mots-clés : Programmation semi-définie linéaire,
Méthode de trajectoire centrale,
Méthode de points intérieurs primale–duale,
Analyse de la complexitéIndex. décimale : 510 Mathématique Résumé :
Résumé
Dans cette thèse, on s’est intéressé à la résolution du problème de programmation semi-définie
(PSD) par la méthode de trajectoire centrale. On a associé à (PSD) un problème perturbé, noté
(PSD)µ. En premier lieu, on a montré l'existence et l'unicité de la solution optimale du problème
(PSD)µ , ensuite on a montré que cette solution converge vers la solution optimale du problème
originel (PSD) quand µ tend vers zéro.
Puis, on a proposé quatre nouvelles alternatives pour calculer le pas de déplacement par une
technique simple, facile et moins couteuse. Enfin, pour valoriser notre contribution, on a présenté
des simulations numériques pour illustrer l’efficacité et la convergence des quatre alternatives vers
la solution optimale du problème considéré (PSD).
Note de contenu :
Table des matières
Introduction 4
1 Préliminaires et notions fondamentales 8
1.1 Analyse matricielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Determinant, spectre et norme spectrale . . . . . . . . . . . . . . . ´ 8
1.1.2 Trace d’une matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.3 Produit scalaire et norme de Frobenius . . . . . . . . . . . . . . . 11
1.1.4 Matrices (semi-) definies positives . . . . . . . . . . . . . . . . . . ´ 11
1.2 Analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.1 Ensembles et fonctions affines . . . . . . . . . . . . . . . . . . . . 16
1.2.2 Ensembles et fonctions convexes . . . . . . . . . . . . . . . . . . . 17
1.2.3 Le cone des matrices sym ˆ etriques semi-d ´ efinies positives . . . . . ´ 21
1.3 Programmation mathematique . . . . . . . . . . . . . . . . . . . . . . . . ´ 22
1.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 22
1.3.2 Principaux resultats d’existence et d’unicit ´ e . . . . . . . . . . . . . ´ 24
1.3.3 Conditions d’optimalite . . . . . . . . . . . . . . . . . . . . . . . . ´ 25
1.3.4 Programme lineaire . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 26
2 La programmation semi-d´efinie : Th´eorie, Applications et R´esolution 27
2.1 Les programmes semi-definis . . . . . . . . . . . . . . . . . . . . . . . . . ´ 27
2.1.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 Theorie de la dualit ´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 30`
2.2.1 Exemples pathologiques . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.2 Relations primales-duales pour la programmation semi-definie . ´ 35
2.3 Domaines d’applications en PSD . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.1 Optimisation des valeurs propres . . . . . . . . . . . . . . . . . . 37
2.3.2 Programmation quadratique avec contraintes quadratiques . . . 39
2.3.3 Approximation logarithmique de Tchebychev . . . . . . . . . . . 40
2.3.4 Problemes g ` eom´ etriques en formes quadratiques . . . . . . . . . ´ 42
2.3.5 Optimisation quadratique non convexe . . . . . . . . . . . . . . . 43
2.4 Methode de points int ´ erieurs pour r ´ esoudre ( ´ PSD) . . . . . . . . . . . . . 46
2.4.1 Methodes a ´ ffines . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4.2 Methodes de r ´ eduction du potentiel . . . . . . . . . . . . . . . . . ´ 47
2.4.3 Methodes de trajectoire centrale . . . . . . . . . . . . . . . . . . . ´ 49
3 M´ethode r ´ealisable de trajectoire centrale pour la programmation semi-d´efinie 52
3.1 Position du probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ` 53
3.2 Existence et unicite de la solution optimale du probl ´ eme ` (PSD)µ et sa convergence vers une solution du (PSD) . ... . 54
3.2.1 Existence et unicite de la solution optimale de ´ (PSD)µ. . . . . 54
3.2.2 Convergence de la solution optimale de (PSD)µ vers la solution optimale de (PSD) . . . . . . . . . 56
3.3 Methode de trajectoire centrale primale-duale . . . . . . . . . . . . . . . ´ 57
3.3.1 Calcul du pas de deplacement . . . . . . . . . . . . . . . . . . . . ´ 60
3.4 L’algorithme prototype et l’analyse de sa complexite . . . . . . . . . . . . ´ 66
3.4.1 Algorithme de la methode de trajectoire centrale . . . . . . . . . . ´ 66
3.4.2 Resultats de convergence . . . . . . . . . . . . . . . . . . . . . . . ´ 67
3.4.3 Analyse de la complexite . . . . . . . . . . . . . . . . . . . . . . . ´ 69
3.5 Mise en oeuvre de la methode de trajectoire centrale pour ( ´ PSD) . . . . . 76
3.5.1 Exemples a taille fixe . . . . . . . . . . . . . . . . . . . . . . . . . . ` 76
3.5.2 Exemple a taille variable . . . . . . . . . . . . . . . . . . . . . . . . ` 80
3.5.3 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Conclusion 82Côte titre : DM/0124 En ligne : https://drive.google.com/file/d/1bqglv3NYoW88vlcsZ8rr_YOzcQzp-nMr/view?usp=shari [...] Format de la ressource électronique : Etude théorique et numérique des méthodes de points intérieurs de type trajectoire centrale pour la programmation semi-définie linéaire [texte imprimé] / Imene Touil ; D. Benterki, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (89 f.) ; 29 cm.
Catégories : Mathématique Mots-clés : Programmation semi-définie linéaire,
Méthode de trajectoire centrale,
Méthode de points intérieurs primale–duale,
Analyse de la complexitéIndex. décimale : 510 Mathématique Résumé :
Résumé
Dans cette thèse, on s’est intéressé à la résolution du problème de programmation semi-définie
(PSD) par la méthode de trajectoire centrale. On a associé à (PSD) un problème perturbé, noté
(PSD)µ. En premier lieu, on a montré l'existence et l'unicité de la solution optimale du problème
(PSD)µ , ensuite on a montré que cette solution converge vers la solution optimale du problème
originel (PSD) quand µ tend vers zéro.
Puis, on a proposé quatre nouvelles alternatives pour calculer le pas de déplacement par une
technique simple, facile et moins couteuse. Enfin, pour valoriser notre contribution, on a présenté
des simulations numériques pour illustrer l’efficacité et la convergence des quatre alternatives vers
la solution optimale du problème considéré (PSD).
Note de contenu :
Table des matières
Introduction 4
1 Préliminaires et notions fondamentales 8
1.1 Analyse matricielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Determinant, spectre et norme spectrale . . . . . . . . . . . . . . . ´ 8
1.1.2 Trace d’une matrice . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.3 Produit scalaire et norme de Frobenius . . . . . . . . . . . . . . . 11
1.1.4 Matrices (semi-) definies positives . . . . . . . . . . . . . . . . . . ´ 11
1.2 Analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.1 Ensembles et fonctions affines . . . . . . . . . . . . . . . . . . . . 16
1.2.2 Ensembles et fonctions convexes . . . . . . . . . . . . . . . . . . . 17
1.2.3 Le cone des matrices sym ˆ etriques semi-d ´ efinies positives . . . . . ´ 21
1.3 Programmation mathematique . . . . . . . . . . . . . . . . . . . . . . . . ´ 22
1.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 22
1.3.2 Principaux resultats d’existence et d’unicit ´ e . . . . . . . . . . . . . ´ 24
1.3.3 Conditions d’optimalite . . . . . . . . . . . . . . . . . . . . . . . . ´ 25
1.3.4 Programme lineaire . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 26
2 La programmation semi-d´efinie : Th´eorie, Applications et R´esolution 27
2.1 Les programmes semi-definis . . . . . . . . . . . . . . . . . . . . . . . . . ´ 27
2.1.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2 Theorie de la dualit ´ e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 30`
2.2.1 Exemples pathologiques . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2.2 Relations primales-duales pour la programmation semi-definie . ´ 35
2.3 Domaines d’applications en PSD . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.1 Optimisation des valeurs propres . . . . . . . . . . . . . . . . . . 37
2.3.2 Programmation quadratique avec contraintes quadratiques . . . 39
2.3.3 Approximation logarithmique de Tchebychev . . . . . . . . . . . 40
2.3.4 Problemes g ` eom´ etriques en formes quadratiques . . . . . . . . . ´ 42
2.3.5 Optimisation quadratique non convexe . . . . . . . . . . . . . . . 43
2.4 Methode de points int ´ erieurs pour r ´ esoudre ( ´ PSD) . . . . . . . . . . . . . 46
2.4.1 Methodes a ´ ffines . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4.2 Methodes de r ´ eduction du potentiel . . . . . . . . . . . . . . . . . ´ 47
2.4.3 Methodes de trajectoire centrale . . . . . . . . . . . . . . . . . . . ´ 49
3 M´ethode r ´ealisable de trajectoire centrale pour la programmation semi-d´efinie 52
3.1 Position du probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ` 53
3.2 Existence et unicite de la solution optimale du probl ´ eme ` (PSD)µ et sa convergence vers une solution du (PSD) . ... . 54
3.2.1 Existence et unicite de la solution optimale de ´ (PSD)µ. . . . . 54
3.2.2 Convergence de la solution optimale de (PSD)µ vers la solution optimale de (PSD) . . . . . . . . . 56
3.3 Methode de trajectoire centrale primale-duale . . . . . . . . . . . . . . . ´ 57
3.3.1 Calcul du pas de deplacement . . . . . . . . . . . . . . . . . . . . ´ 60
3.4 L’algorithme prototype et l’analyse de sa complexite . . . . . . . . . . . . ´ 66
3.4.1 Algorithme de la methode de trajectoire centrale . . . . . . . . . . ´ 66
3.4.2 Resultats de convergence . . . . . . . . . . . . . . . . . . . . . . . ´ 67
3.4.3 Analyse de la complexite . . . . . . . . . . . . . . . . . . . . . . . ´ 69
3.5 Mise en oeuvre de la methode de trajectoire centrale pour ( ´ PSD) . . . . . 76
3.5.1 Exemples a taille fixe . . . . . . . . . . . . . . . . . . . . . . . . . . ` 76
3.5.2 Exemple a taille variable . . . . . . . . . . . . . . . . . . . . . . . . ` 80
3.5.3 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
Conclusion 82Côte titre : DM/0124 En ligne : https://drive.google.com/file/d/1bqglv3NYoW88vlcsZ8rr_YOzcQzp-nMr/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0124 DM/0124 Thèse Bibliothéque des sciences Français Disponible
DisponibleEtude théorique et numérique d’un problème aux limites non linéaire dans un domaine non borné / Djamila Chergui
Titre : Etude théorique et numérique d’un problème aux limites non linéaire dans un domaine non borné Type de document : texte imprimé Auteurs : Djamila Chergui ; M. Kolli, Directeur de thèse Editeur : Setif:UFA Année de publication : 2007 Format : 29 cm Catégories : Thèses & Mémoires:Mathématique Mots-clés : Théorique
Numérique
Limites non linéaire
Domaine non bornéIndex. décimale : 510 Mathématique Côte titre : DM/0070 Etude théorique et numérique d’un problème aux limites non linéaire dans un domaine non borné [texte imprimé] / Djamila Chergui ; M. Kolli, Directeur de thèse . - [S.l.] : Setif:UFA, 2007 . - ; 29 cm.
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Théorique
Numérique
Limites non linéaire
Domaine non bornéIndex. décimale : 510 Mathématique Côte titre : DM/0070 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0070 DM/0070 Thèse Bibliothéque des sciences Français Disponible
DisponibleEtude théorique par la méthode DFT des composés α-aminophosphonates synthétisés à partir de para phénylenediamine / Anis Bouchama
Titre : Etude théorique par la méthode DFT des composés α-aminophosphonates synthétisés à partir de para phénylenediamine Type de document : texte imprimé Auteurs : Anis Bouchama ; Abdelkader Hellal Editeur : Setif:UFA Année de publication : 2020 Importance : 1 vol (85 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Chimie Mots-clés : Ester α-aminophosphonate
Acide α-aminophosphonique
Microonde
DFT
Descripteurs de réactivitéIndex. décimale : 540 Chimie et sciences connexes Résumé : Dans cette étude, deux composés, ester et acide aminophosphonique, ont été synthétisées, à reflux et sous microonde, par des réactions à partir de para phénylenediamine. Les produits, obtenus avec de bons rendements sous MO, sont ensuite caractérisés par différentes méthodes physico-chimiques (CCM, l’IR et l’UV). Ensuite, ces molécules ont été étudiées d'un point de vue théorique afin de connaître leurs propriétés structurales et électroniques, grâce aux calculs par la méthode (DFT) et à l'aide du logiciel Gaussian09. Les structures stables ont été optimisées en utilisant la méthode hybride B3LYP/6-31G. Afin de faire une étude comparative entre les molécules obtenues (AP) et (EP), différentes propriétés de ces produits ont été analysées au moyen des propriétés HOMO-LUMO. Les descripteurs de réactivité globale, les charges de Mulliken et les moments dipolaires deux molécules ont également calculés et discutés.
Côte titre : MACH/0185 En ligne : https://drive.google.com/file/d/15UioIOu0jCy12eJJaMugZDgP7n6vQxDu/view?usp=shari [...] Format de la ressource électronique : Etude théorique par la méthode DFT des composés α-aminophosphonates synthétisés à partir de para phénylenediamine [texte imprimé] / Anis Bouchama ; Abdelkader Hellal . - [S.l.] : Setif:UFA, 2020 . - 1 vol (85 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Chimie Mots-clés : Ester α-aminophosphonate
Acide α-aminophosphonique
Microonde
DFT
Descripteurs de réactivitéIndex. décimale : 540 Chimie et sciences connexes Résumé : Dans cette étude, deux composés, ester et acide aminophosphonique, ont été synthétisées, à reflux et sous microonde, par des réactions à partir de para phénylenediamine. Les produits, obtenus avec de bons rendements sous MO, sont ensuite caractérisés par différentes méthodes physico-chimiques (CCM, l’IR et l’UV). Ensuite, ces molécules ont été étudiées d'un point de vue théorique afin de connaître leurs propriétés structurales et électroniques, grâce aux calculs par la méthode (DFT) et à l'aide du logiciel Gaussian09. Les structures stables ont été optimisées en utilisant la méthode hybride B3LYP/6-31G. Afin de faire une étude comparative entre les molécules obtenues (AP) et (EP), différentes propriétés de ces produits ont été analysées au moyen des propriétés HOMO-LUMO. Les descripteurs de réactivité globale, les charges de Mulliken et les moments dipolaires deux molécules ont également calculés et discutés.
Côte titre : MACH/0185 En ligne : https://drive.google.com/file/d/15UioIOu0jCy12eJJaMugZDgP7n6vQxDu/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MACH/0185 MACH/0185 Mémoire Bibliothéque des sciences Français Disponible
DisponibleEtude théorique par la méthode de DFT des constituants principales de la plante médicinale « Genévrier Phoenicea » / Amira Kadri
PermalinkEtude théorique d’un problème électro-viscoélastique avec mémoire longue et usure / Sabrina Aliane
PermalinkEtude théorique des propriétés catalytique d’une surface bimétallique CuW (100) / Chouayb Guerra
PermalinkPermalinkEtude théorique des propriétés catalytiques des surfaces d’alliage à base de métaux de transition / Khettal, Habib
PermalinkEtude théorique de propriétés catalytiques des surfaces bimétalliques à base des métaux de transition : Activation de l’eau sur les surfaces bimétallique Ru-Cu (100) et W-Cu (100). / Amina Bellalem
PermalinkEtude théorique des propriétés structurale, élastique et thermodynamiques des composés T2GaC avec T=Mo, Nb et Ta / Ikhlass Benaissa
PermalinkEtude théorique des propriétés structurales, élastiques et thermodynamiques des composés à base de TiAl / Ines Zerari
PermalinkEtude théorique des propriétés structurales et magnéto-optiques dans le film ultra-mince Fen /Cu (001) / Benchikh, somia
PermalinkEtude théorique des propriétés structurales, de la structure électronique, du magnétisme et de l'effet Kerr dans les films ultraminces ferrimagnétiques / Ouarab, nouredine
Permalink