University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Goutali, Moufida |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Complexité et implémentation numérique d’une méthode de points intérieurs pour la programmation convexe / Goutali, Moufida
Titre : Complexité et implémentation numérique d’une méthode de points intérieurs pour la programmation convexe Type de document : texte imprimé Auteurs : Goutali, Moufida, Auteur ; Achache, M, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (92 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation convexe acontraintes linéaires
Complexité des AgorithmesIndex. décimale : 510 Mathématique Résumé : Résumé
Dans cette thèse, on s’intéresse à l’étude théorique (notamment la complexité polynomi-
ale) et à l’implémentation numérique d’une méthode de points intérieurs de trajectoire
centrale de type primal-dual pour résoudre les problèmes de la programmation convexe Ã
contraintes linéaires (PCCL). Dans notre étude, nous proposons de nouveaux paramètres
qui décrivent le paramètre barrière et le seuil qui mesure la taille du voisinage de la
trajectoire centrale. À travers ces derniers, un algorithme primal-dual à pas court et
d’itération de Newton complet bien dé…ni est présenté et de plus sa complexité est cal-
culée. L’e¢ cacité numérique de cet algorithme est con…rmée par des tests numériques.
Note de contenu : Sommaire
Analyse convexe et programmation mathématique 14
1.1 Éléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.1 Dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.2 Ensemble a¢ ne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.3 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.4 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.5 Cônes Convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 Programmation Mathématique . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1 Solutions optimales locales et globales . . . . . . . . . . . . . . . 18
1.2.2 Classi…cation d’un programme mathématique . . . . . . . . . . . 19
1.2.3 QualiÂ…cation des contraintes . . . . . . . . . . . . . . . . . . . . . 19
1.2.4 Résolution d’un programme mathématique . . . . . . . . . . . . . 20
1.3 Programmation convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.1 Existence (unicité) d’une solution optimale . . . . . . . . . . . . . 22
1.3.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.3 Le dual dÂ’un programme convexe . . . . . . . . . . . . . . . . . . 23
1.4 Algorithme dÂ’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5 Méthode de Newton-Raphson pour un système non linéaire . . . . . . . . 27
1.6 Méthodes de résolution d’un programme mathématique . . . . . . . . . . 28
1.6.1 Méthodes de type gradient . . . . . . . . . . . . . . . . . . . . . . 28
1.6.2 Méthodes simpliciales . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . 29
2 Méthodes de points intérieurs de type de TC pour (PCCL) 32
2.1 Existence et unicité de la trajectoire centrale (suivi de chemin) pour PCCL 32
2.1.1 Le problème perturbé . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.2 Les conditions d’optimalité de (K.K.T) . . . . . . . . . . . . . . 34
2.1.3 Le chemin central est bien dé…ni . . . . . . . . . . . . . . . . . . . 36
2.1.4 Le Théorème principal de la trajectoire centrale . . . . . . . . . . 37
2.2 Principe des méthodes de trajectoire centrale . . . . . . . . . . . . . . . . 40
2.2.1 Concept de proximité ou de centralisation . . . . . . . . . . . . . 41
2.2.2 Mise à jour du paramètre barrière . . . . . . . . . . . . . . . . . 42
2.2.3 Itération de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.4 Pas de déplacement . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3 Algorithme générale primal-dual de suivi de trajectoire . . . . . . . . . . 44
3 Méthodes primal-dual pour (PCCL) 45
3.1 Directions de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.1 Description algorithmique . . . . . . . . . . . . . . . . . . . . . . 48
3.1.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Convergence de l’algorithme et analyse de la complexité . . . . . . . . . . 49
3.2.1 Résultats préliminaires . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.2 Analyse de la faisabilité . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.3 Analyse de la complexité . . . . . . . . . . . . . . . . . . . . . . . 56
4 Simulation numérique 58
4.1 Mise en Âœuvre de cet algorithme . . . . . . . . . . . . . . . . . . . . . . 58
4.1.1 Paramètre barrière . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.1.2 Directions de déplacement . . . . . . . . . . . . . . . . . . . . . . 59
4.1.3 Point dÂ’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.1 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.2 Programmation quadratique . . . . . . . . . . . . . . . . . . . . . 66
4.2.3 Cas dÂ’une fonction convexe . . . . . . . . . . . . . . . . . . . . . 72
4.2.4 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4 Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Côte titre : DM/0140 En ligne : https://drive.google.com/file/d/1N-LtJ9dgX_smqAuQLpOV4bz1Rg28767N/view?usp=shari [...] Format de la ressource électronique : Complexité et implémentation numérique d’une méthode de points intérieurs pour la programmation convexe [texte imprimé] / Goutali, Moufida, Auteur ; Achache, M, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (92 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation convexe acontraintes linéaires
Complexité des AgorithmesIndex. décimale : 510 Mathématique Résumé : Résumé
Dans cette thèse, on s’intéresse à l’étude théorique (notamment la complexité polynomi-
ale) et à l’implémentation numérique d’une méthode de points intérieurs de trajectoire
centrale de type primal-dual pour résoudre les problèmes de la programmation convexe Ã
contraintes linéaires (PCCL). Dans notre étude, nous proposons de nouveaux paramètres
qui décrivent le paramètre barrière et le seuil qui mesure la taille du voisinage de la
trajectoire centrale. À travers ces derniers, un algorithme primal-dual à pas court et
d’itération de Newton complet bien dé…ni est présenté et de plus sa complexité est cal-
culée. L’e¢ cacité numérique de cet algorithme est con…rmée par des tests numériques.
Note de contenu : Sommaire
Analyse convexe et programmation mathématique 14
1.1 Éléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.1 Dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.2 Ensemble a¢ ne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.3 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.4 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.5 Cônes Convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 Programmation Mathématique . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1 Solutions optimales locales et globales . . . . . . . . . . . . . . . 18
1.2.2 Classi…cation d’un programme mathématique . . . . . . . . . . . 19
1.2.3 QualiÂ…cation des contraintes . . . . . . . . . . . . . . . . . . . . . 19
1.2.4 Résolution d’un programme mathématique . . . . . . . . . . . . . 20
1.3 Programmation convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.1 Existence (unicité) d’une solution optimale . . . . . . . . . . . . . 22
1.3.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.3 Le dual dÂ’un programme convexe . . . . . . . . . . . . . . . . . . 23
1.4 Algorithme dÂ’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5 Méthode de Newton-Raphson pour un système non linéaire . . . . . . . . 27
1.6 Méthodes de résolution d’un programme mathématique . . . . . . . . . . 28
1.6.1 Méthodes de type gradient . . . . . . . . . . . . . . . . . . . . . . 28
1.6.2 Méthodes simpliciales . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . 29
2 Méthodes de points intérieurs de type de TC pour (PCCL) 32
2.1 Existence et unicité de la trajectoire centrale (suivi de chemin) pour PCCL 32
2.1.1 Le problème perturbé . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.2 Les conditions d’optimalité de (K.K.T) . . . . . . . . . . . . . . 34
2.1.3 Le chemin central est bien dé…ni . . . . . . . . . . . . . . . . . . . 36
2.1.4 Le Théorème principal de la trajectoire centrale . . . . . . . . . . 37
2.2 Principe des méthodes de trajectoire centrale . . . . . . . . . . . . . . . . 40
2.2.1 Concept de proximité ou de centralisation . . . . . . . . . . . . . 41
2.2.2 Mise à jour du paramètre barrière . . . . . . . . . . . . . . . . . 42
2.2.3 Itération de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.4 Pas de déplacement . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3 Algorithme générale primal-dual de suivi de trajectoire . . . . . . . . . . 44
3 Méthodes primal-dual pour (PCCL) 45
3.1 Directions de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.1 Description algorithmique . . . . . . . . . . . . . . . . . . . . . . 48
3.1.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Convergence de l’algorithme et analyse de la complexité . . . . . . . . . . 49
3.2.1 Résultats préliminaires . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.2 Analyse de la faisabilité . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.3 Analyse de la complexité . . . . . . . . . . . . . . . . . . . . . . . 56
4 Simulation numérique 58
4.1 Mise en Âœuvre de cet algorithme . . . . . . . . . . . . . . . . . . . . . . 58
4.1.1 Paramètre barrière . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.1.2 Directions de déplacement . . . . . . . . . . . . . . . . . . . . . . 59
4.1.3 Point dÂ’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.1 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.2 Programmation quadratique . . . . . . . . . . . . . . . . . . . . . 66
4.2.3 Cas dÂ’une fonction convexe . . . . . . . . . . . . . . . . . . . . . 72
4.2.4 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4 Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Côte titre : DM/0140 En ligne : https://drive.google.com/file/d/1N-LtJ9dgX_smqAuQLpOV4bz1Rg28767N/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0140 DM/0140 Thèse Bibliothéque des sciences Français Disponible
Disponible