University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Guerra ,Loubna |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheMéthodes de points intérieurs et fonctions noyaux pour l’optimisation quadratique semi-définie convexe / Guerra ,Loubna
Titre : Méthodes de points intérieurs et fonctions noyaux pour l’optimisation quadratique semi-définie convexe Type de document : texte imprimé Auteurs : Guerra ,Loubna, Auteur ; Achache, M, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (111 p.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Méthodes de points intérieurs
programmation quadratique convexe semi-définie
Fonction noyau
Algorithme primal-dual
complexité algorithmiqueIndex. décimale : 510 Mathématique Résumé : Résumé
Dans cette thèse, on a proposé deux algorithmes primal-dual de points intérieurs pour la programmation quadratique convexe semi-définie (CQSDP). Le premier est de trajectoire centrale tel que à chaque itération on utilise le pas de Newton complet et une mesure de proximité pour obtenir une solution approximative du (CQSDP). Le deuxième algorithme est basé sur une nouvelle fonction noyau telle que cette fonction est la version paramétrée de celle qui est introduite par de M. W. Zhang en 2012. L’étude de cette fonction nous conduit à une meilleure complexité connue jusqu’à maintenant pour ce type d’algorithme à grand et petit pas.
On suit cette étude par des résultats numériques pour montrer l’efficacité de ces deux algorithmes proposés. Ces propositions ont apporté de nouvelles contributions d’ordre algorithmique, théorique et numérique.Note de contenu : Table des matiËres
1 Calcul matriciel, analyse convexe et programmation mathÈmatique 10
1.1 Rappel sur les matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Rappel dÃanalyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Programmation mathÈmatique . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Programmation quadratique convexe semi-dÈÖnie et mÈthodes de points intÈrieurs 20
2.1 Position du problËme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.1 ProblËme primal . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.2 ProblËme dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 LÃimportance de la programmation quadratique semi-dÈÖnie . . . . . . . 22
2.2.1 ModÈlisation de quelques problËmes dÃoptimisations convexe en un problËme CQSDP . . .. . . . . . . . . 23
2.3 DualitÈ en CQSDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1 DualitÈ faible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.2 Conditions dÃoptimalitÈ nÈcessaires et su¢ santes de la solution optimale . . . . . . . . . . . . 26
2.3.3 ComplÈmentaritÈ en CQSDP . . . . . . . . . . . . . . . . . . . . . 27
2.4 MÈthodes de points intÈrieurs pour rÈsoudre le problËme CQSDP . . . . 28
2.4.1 MÈthode de la trajectoire centrale de type primal-dual pour CQSDP 28
2.4.2 Les directions classiques . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.3 La mesure de proximitÈ . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.4 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.5 La convergence de lÃalgorithme et lÃanalyse de la complexitÈ . . . 35
3 MÈthodes de points intÈrieurs basÈe sur une nouvelle fonction noyau pour CQSDP 48
3.1 Les fonctions noyaux et leurs propriÈtÈs . . . . . . . . . . . . . . . . . . . 48
3.1.1 Notion dÃune fonction noyau . . . . . . . . . . . . . . . . . . . . . 49
3.1.2 QualiÖcation dÃune fonction noyau . . . . . . . . . . . . . . . . . 50
3.1.3 PropriÈtÈs dÃune fonction noyau Èligible . . . . . . . . . . . . . . . 54
3.2 Nouvelles directions cherchÈes . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.2 Une borne supÈrieure de (V ) aprËs chaque itÈration externe . . 58
3.2.3 La dÈcroissance de la fonction barriËre durant une itÈration interne 59
3.2.4 Borne de (V ) en terme de (V ) . . . . . . . . . . . . . . . . . . 62
3.2.5 Borne dÃitÈrations . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.3 La convergence de lÃalgorithme et lÃanalyse de la complexitÈ . . . . . . . 64
3.3.1 SchÈma pour analyser un algorithme basÈ sur une fonction noyau Èligible . . . . . . . . . . . 64
3.3.2 Analyse de la complexitÈ . . . . . . . . . . . . . . . . . . . . . . . 66
4 Tests numÈriques 72
4.1 Calcul de la matrice V . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2 Calcul du pas de dÈplacement . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3 ProblËmes ‡ tester . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.1 ProblËmes ‡ taille variable . . . . . . . . . . . . . . . . . . . . . . 75
4.3.2 ProblËmes ‡ taille Öxe . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.3 ProblËme de (N CM) . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.4 RÈsultats numÈriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4.1 RÈsultats numÈriques pour lÃAlgorithme 2.4.4 ‡ petit pas . . . . . 84
4.4.2 RÈsultats comparatifs pour lÃAlgorithme 3.2.1 ‡ grand pas . . . . 85
Conclusion gÈnÈrale et perspectives 98
Bibliographie 100
Annexe 104Côte titre : DM/0139 En ligne : https://drive.google.com/file/d/1IU6_DgY25fd8MuriaUa5e7zIxOJKyjCu/view?usp=shari [...] Format de la ressource électronique : Méthodes de points intérieurs et fonctions noyaux pour l’optimisation quadratique semi-définie convexe [texte imprimé] / Guerra ,Loubna, Auteur ; Achache, M, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (111 p.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Méthodes de points intérieurs
programmation quadratique convexe semi-définie
Fonction noyau
Algorithme primal-dual
complexité algorithmiqueIndex. décimale : 510 Mathématique Résumé : Résumé
Dans cette thèse, on a proposé deux algorithmes primal-dual de points intérieurs pour la programmation quadratique convexe semi-définie (CQSDP). Le premier est de trajectoire centrale tel que à chaque itération on utilise le pas de Newton complet et une mesure de proximité pour obtenir une solution approximative du (CQSDP). Le deuxième algorithme est basé sur une nouvelle fonction noyau telle que cette fonction est la version paramétrée de celle qui est introduite par de M. W. Zhang en 2012. L’étude de cette fonction nous conduit à une meilleure complexité connue jusqu’à maintenant pour ce type d’algorithme à grand et petit pas.
On suit cette étude par des résultats numériques pour montrer l’efficacité de ces deux algorithmes proposés. Ces propositions ont apporté de nouvelles contributions d’ordre algorithmique, théorique et numérique.Note de contenu : Table des matiËres
1 Calcul matriciel, analyse convexe et programmation mathÈmatique 10
1.1 Rappel sur les matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Rappel dÃanalyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Programmation mathÈmatique . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Programmation quadratique convexe semi-dÈÖnie et mÈthodes de points intÈrieurs 20
2.1 Position du problËme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.1 ProblËme primal . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.2 ProblËme dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 LÃimportance de la programmation quadratique semi-dÈÖnie . . . . . . . 22
2.2.1 ModÈlisation de quelques problËmes dÃoptimisations convexe en un problËme CQSDP . . .. . . . . . . . . 23
2.3 DualitÈ en CQSDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1 DualitÈ faible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.2 Conditions dÃoptimalitÈ nÈcessaires et su¢ santes de la solution optimale . . . . . . . . . . . . 26
2.3.3 ComplÈmentaritÈ en CQSDP . . . . . . . . . . . . . . . . . . . . . 27
2.4 MÈthodes de points intÈrieurs pour rÈsoudre le problËme CQSDP . . . . 28
2.4.1 MÈthode de la trajectoire centrale de type primal-dual pour CQSDP 28
2.4.2 Les directions classiques . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.3 La mesure de proximitÈ . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.4 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.5 La convergence de lÃalgorithme et lÃanalyse de la complexitÈ . . . 35
3 MÈthodes de points intÈrieurs basÈe sur une nouvelle fonction noyau pour CQSDP 48
3.1 Les fonctions noyaux et leurs propriÈtÈs . . . . . . . . . . . . . . . . . . . 48
3.1.1 Notion dÃune fonction noyau . . . . . . . . . . . . . . . . . . . . . 49
3.1.2 QualiÖcation dÃune fonction noyau . . . . . . . . . . . . . . . . . 50
3.1.3 PropriÈtÈs dÃune fonction noyau Èligible . . . . . . . . . . . . . . . 54
3.2 Nouvelles directions cherchÈes . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.2 Une borne supÈrieure de (V ) aprËs chaque itÈration externe . . 58
3.2.3 La dÈcroissance de la fonction barriËre durant une itÈration interne 59
3.2.4 Borne de (V ) en terme de (V ) . . . . . . . . . . . . . . . . . . 62
3.2.5 Borne dÃitÈrations . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.3 La convergence de lÃalgorithme et lÃanalyse de la complexitÈ . . . . . . . 64
3.3.1 SchÈma pour analyser un algorithme basÈ sur une fonction noyau Èligible . . . . . . . . . . . 64
3.3.2 Analyse de la complexitÈ . . . . . . . . . . . . . . . . . . . . . . . 66
4 Tests numÈriques 72
4.1 Calcul de la matrice V . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2 Calcul du pas de dÈplacement . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3 ProblËmes ‡ tester . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.1 ProblËmes ‡ taille variable . . . . . . . . . . . . . . . . . . . . . . 75
4.3.2 ProblËmes ‡ taille Öxe . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.3 ProblËme de (N CM) . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.4 RÈsultats numÈriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4.1 RÈsultats numÈriques pour lÃAlgorithme 2.4.4 ‡ petit pas . . . . . 84
4.4.2 RÈsultats comparatifs pour lÃAlgorithme 3.2.1 ‡ grand pas . . . . 85
Conclusion gÈnÈrale et perspectives 98
Bibliographie 100
Annexe 104Côte titre : DM/0139 En ligne : https://drive.google.com/file/d/1IU6_DgY25fd8MuriaUa5e7zIxOJKyjCu/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0139 DM/0139 Thèse Bibliothéque des sciences Français Disponible
Disponible
