University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Imene Touil |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheEtude 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
Disponible
