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é algorithmique
Index. 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 104
Côte titre :	DM/0139
En ligne :	https://drive.google.com/file/d/1IU6_DgY25fd8MuriaUa5e7zIxOJKyjCu/view?usp=shari [...]
Format de la ressource électronique :	pdf

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é algorithmique
Index. 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 104
Côte titre :	DM/0139
En ligne :	https://drive.google.com/file/d/1IU6_DgY25fd8MuriaUa5e7zIxOJKyjCu/view?usp=shari [...]
Format de la ressource électronique :	pdf