University Sétif 1 FERHAT ABBAS Faculty of Sciences
Résultat de la recherche
1 résultat(s) recherche sur le mot-clé 'Programmation convexe acontraintes linéaires Complexité des Agorithmes'
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
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