University Sétif 1 FERHAT ABBAS Faculty of Sciences
Catégories
Ajouter le résultat dans votre panier Affiner la recherche
Mé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
DisponibleMéthodes de points intérieurs et leurs applications sur des problèmes d'optimisation semi-définis / Zerari ,Amina
Titre : Méthodes de points intérieurs et leurs applications sur des problèmes d'optimisation semi-définis Type de document : texte imprimé Auteurs : Zerari ,Amina, Auteur ; Djamel Benterki, Directeur de thèse Editeur : Setif:UFA Année de publication : 2020 Importance : 1 vol (93 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation semi-définie
Méthode de points intérieurs
Méthode projectiveIndex. décimale : 510 - Mathématique Résumé : Les méthodes de points intérieurs sont bien connues comme les plus efficaces pour résoudre les problèmes d’optimisation. Ces méthodes possèdent une convergence polynômiale et un bon comportement numérique. Dans cette recherche, nous nous sommes intéressés à une étude théorique, algorithmique et numérique des méthodes de points intérieurs pour la programmation semi-définie.
En effet, on présente dans une première partie un algorithme réalisable projectif primal-dual de points intérieurs de type polynômial à deux phases, où on a introduit trois nouvelles alternatives efficaces pour calculer le pas de déplacement.
Ensuite, dans la deuxième partie, on s’intéresse aux méthodes de type trajectoire centrale primale-duale via une fonction noyau, nous proposons deux nouvelles fonctions noyaux à terme logarithmique qui donnent la meilleure complexité algorithmique, obtenue jusqu’à présent.Côte titre : DM/0160 En ligne : https://drive.google.com/file/d/1rFNeEG1GpEdyy-kEw-4m_S1tpr2D36Ou/view?usp=shari [...] Format de la ressource électronique : Méthodes de points intérieurs et leurs applications sur des problèmes d'optimisation semi-définis [texte imprimé] / Zerari ,Amina, Auteur ; Djamel Benterki, Directeur de thèse . - [S.l.] : Setif:UFA, 2020 . - 1 vol (93 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation semi-définie
Méthode de points intérieurs
Méthode projectiveIndex. décimale : 510 - Mathématique Résumé : Les méthodes de points intérieurs sont bien connues comme les plus efficaces pour résoudre les problèmes d’optimisation. Ces méthodes possèdent une convergence polynômiale et un bon comportement numérique. Dans cette recherche, nous nous sommes intéressés à une étude théorique, algorithmique et numérique des méthodes de points intérieurs pour la programmation semi-définie.
En effet, on présente dans une première partie un algorithme réalisable projectif primal-dual de points intérieurs de type polynômial à deux phases, où on a introduit trois nouvelles alternatives efficaces pour calculer le pas de déplacement.
Ensuite, dans la deuxième partie, on s’intéresse aux méthodes de type trajectoire centrale primale-duale via une fonction noyau, nous proposons deux nouvelles fonctions noyaux à terme logarithmique qui donnent la meilleure complexité algorithmique, obtenue jusqu’à présent.Côte titre : DM/0160 En ligne : https://drive.google.com/file/d/1rFNeEG1GpEdyy-kEw-4m_S1tpr2D36Ou/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0160 DM/0160 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : MÉTHODES DE POINTS INTÉRIEURS POUR LLA PROGRAMMATION QUADRATIQUE CONVEXE : THÉORIE, ALGORITHMES ET APPLICATIONS Type de document : texte imprimé Auteurs : Nawel Boudjellal, Auteur ; Hayet Roumili, Directeur de thèse Editeur : Setif:UFA Année de publication : 2020 Importance : 1 vol (97 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Méthodes de points intérieurs primales-duales
Programmation quadratique convexe
Version à grand et petit pas
Fonction noyauIndex. décimale : 510 Mathématique Résumé :
Dans cette thèse, une classe de méthodes de points intérieurs primales-duales (MPIs) pour résoudre des problèmes de programmation quadratique convexe est présentée. C'est une méthode de trajectoire centrale basée sur une fonction noyau qui est proposée dans le but de remédier au problème d'initialisation (le point initial soit au voisinage de la trajectoire centrale) en créant la phase de centralité qui est mesurée par fonction barrière. Nous proposons deux nouvelles fonctions noyaux paramétrées. La première a un terme barrière exponentiel et la seconde a un terme barrière polynomial. Nous analysons les versions à grand et petit pas qui sont basées sur ces nouvelles fonctions noyaux. Nous obtenons les meilleures bornes d'itérations connues concernant la petite version pour les deux fonctions noyaux et la grande version de mise à jour pour la deuxième fonction noyau. Enfin, quelques résultats numériques sont présentés pour montrer l'efficacité des fonctions noyaux proposées.Côte titre : DM/0162 En ligne : https://drive.google.com/file/d/1eW2UhAc7a-UvyzLiFldKnIf9VUDk2nJQ/view?usp=shari [...] Format de la ressource électronique : MÉTHODES DE POINTS INTÉRIEURS POUR LLA PROGRAMMATION QUADRATIQUE CONVEXE : THÉORIE, ALGORITHMES ET APPLICATIONS [texte imprimé] / Nawel Boudjellal, Auteur ; Hayet Roumili, Directeur de thèse . - [S.l.] : Setif:UFA, 2020 . - 1 vol (97 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Méthodes de points intérieurs primales-duales
Programmation quadratique convexe
Version à grand et petit pas
Fonction noyauIndex. décimale : 510 Mathématique Résumé :
Dans cette thèse, une classe de méthodes de points intérieurs primales-duales (MPIs) pour résoudre des problèmes de programmation quadratique convexe est présentée. C'est une méthode de trajectoire centrale basée sur une fonction noyau qui est proposée dans le but de remédier au problème d'initialisation (le point initial soit au voisinage de la trajectoire centrale) en créant la phase de centralité qui est mesurée par fonction barrière. Nous proposons deux nouvelles fonctions noyaux paramétrées. La première a un terme barrière exponentiel et la seconde a un terme barrière polynomial. Nous analysons les versions à grand et petit pas qui sont basées sur ces nouvelles fonctions noyaux. Nous obtenons les meilleures bornes d'itérations connues concernant la petite version pour les deux fonctions noyaux et la grande version de mise à jour pour la deuxième fonction noyau. Enfin, quelques résultats numériques sont présentés pour montrer l'efficacité des fonctions noyaux proposées.Côte titre : DM/0162 En ligne : https://drive.google.com/file/d/1eW2UhAc7a-UvyzLiFldKnIf9VUDk2nJQ/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0162 DM/0162 Mémoire Bibliothéque des sciences Français Disponible
DisponibleMéthodes de points intérieurs de type primal-dual pour la programmation linéaire basées sur des nouvelles directions. Etude numérique et comparative / Sebaoune ,Basma
Titre : Méthodes de points intérieurs de type primal-dual pour la programmation linéaire basées sur des nouvelles directions. Etude numérique et comparative Type de document : texte imprimé Auteurs : Sebaoune ,Basma, Auteur ; Mohamed Achache, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (49 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation linéaire
Méthode de point intérieur
Algorithme primal- dual de type trajectoire centraleIndex. décimale : 510 Mathématique Résumé : Dans ce mémoire, nous présentons une méthode de point intérieur de type primal-dual
de trajectoire centrale avec un pas de Newton complet pour résoudre les problèmes de la
programmation linéaire. La spéci…cité de notre méthode est de calculer le pas de Newton
en utilisant un système modi…é qui contient l’équation de centralité. Pour ce but, nous
considérons trois fonctions connues dans la littérature appliquées à l’équation de centra-
lité et donc de nouvelles directions de Newton sont déterminées. La convergence de ces
algorithmes est achevée. Finalement, des expériences numériques de ces trois algorithmes
à pas court sur des programmes linéaires connus dans la littérature sont présentées suivi
par une étude comparative entre les résultats numériques obtenus a travers ces trois
fonctions. Finalement, on terminera le mémoire par une conclusion et des perspectives.Note de contenu :
Sommaire
Programmation linéaire et méthodes de résolution 11
1.1 Théorie générale de la programmation linéaire . . . . . . . . . . . . . . . 11
1.2 Dualité en programmation linéaire . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Méthodes de résolution d’un programme linéaire . . . . . . . . . . . . . . 14
1.3.1 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.2 Méthodes modernes de points intérieures . . . . . . . . . . . . . . 15
1.3.3 Algorithme dÂ’optimisation . . . . . . . . . . . . . . . . . . . . . . 16
2 Méthodes primales duales pour la programmation linéaire 21
2.1 Méthodes de trajectoire centrale classiques basées sur l’approche barrière
logarithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1 Méthodes barrières logarithmiques de type primal dual de TC pour
PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.2 Le problème perturbé . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.3 Concept de proximité ou de centralisation . . . . . . . . . . . . . 23
2.1.4 Directions de Newton classiques . . . . . . . . . . . . . . . . . . . 24
3 Méthodes nouvelles primales-duales pour la programmation linéaire 25
3.1 Principe de ces méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Nouvelle classe de directions de Newton . . . . . . . . . . . . . . . . . . . 26
3.3 Directions de Newton pour le choix de '(t) = t: . . . . . . . . . . . . . . 28
2
3.3.1 Description algorithmique . . . . . . . . . . . . . . . . . . . . . . 28
3.3.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4 Directions de Newton pour le choix de '(t) = pt . . . . . . . . . . . . . 29
3.4.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Directions de Newton pour le choix de '(t) =
pt
2(1+pt) . . . . . . . . . . . 31
3.5.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6 Complexité polynomiale de ces trois algorithmes . . . . . . . . . . . . . . 33
4 Expérimentation numérique et comparaison 35
4.0.1 Paramètre barrière . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.0.2 Directions de déplacement . . . . . . . . . . . . . . . . . . . . . . 36
4.0.3 Point dÂ’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Comparaison numérique entre les trois algorithmes . . . . . . . . . . . . 44
4.3 Conclusion et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . 45Côte titre : MAM/0290 En ligne : https://drive.google.com/file/d/1ajKp3JhKjRkiTsuVvDcAyfkEMbV27t5Y/view?usp=share [...] Format de la ressource électronique : Méthodes de points intérieurs de type primal-dual pour la programmation linéaire basées sur des nouvelles directions. Etude numérique et comparative [texte imprimé] / Sebaoune ,Basma, Auteur ; Mohamed Achache, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (49 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation linéaire
Méthode de point intérieur
Algorithme primal- dual de type trajectoire centraleIndex. décimale : 510 Mathématique Résumé : Dans ce mémoire, nous présentons une méthode de point intérieur de type primal-dual
de trajectoire centrale avec un pas de Newton complet pour résoudre les problèmes de la
programmation linéaire. La spéci…cité de notre méthode est de calculer le pas de Newton
en utilisant un système modi…é qui contient l’équation de centralité. Pour ce but, nous
considérons trois fonctions connues dans la littérature appliquées à l’équation de centra-
lité et donc de nouvelles directions de Newton sont déterminées. La convergence de ces
algorithmes est achevée. Finalement, des expériences numériques de ces trois algorithmes
à pas court sur des programmes linéaires connus dans la littérature sont présentées suivi
par une étude comparative entre les résultats numériques obtenus a travers ces trois
fonctions. Finalement, on terminera le mémoire par une conclusion et des perspectives.Note de contenu :
Sommaire
Programmation linéaire et méthodes de résolution 11
1.1 Théorie générale de la programmation linéaire . . . . . . . . . . . . . . . 11
1.2 Dualité en programmation linéaire . . . . . . . . . . . . . . . . . . . . . . 12
1.3 Méthodes de résolution d’un programme linéaire . . . . . . . . . . . . . . 14
1.3.1 Méthode du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.2 Méthodes modernes de points intérieures . . . . . . . . . . . . . . 15
1.3.3 Algorithme dÂ’optimisation . . . . . . . . . . . . . . . . . . . . . . 16
2 Méthodes primales duales pour la programmation linéaire 21
2.1 Méthodes de trajectoire centrale classiques basées sur l’approche barrière
logarithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1 Méthodes barrières logarithmiques de type primal dual de TC pour
PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.2 Le problème perturbé . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.3 Concept de proximité ou de centralisation . . . . . . . . . . . . . 23
2.1.4 Directions de Newton classiques . . . . . . . . . . . . . . . . . . . 24
3 Méthodes nouvelles primales-duales pour la programmation linéaire 25
3.1 Principe de ces méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Nouvelle classe de directions de Newton . . . . . . . . . . . . . . . . . . . 26
3.3 Directions de Newton pour le choix de '(t) = t: . . . . . . . . . . . . . . 28
2
3.3.1 Description algorithmique . . . . . . . . . . . . . . . . . . . . . . 28
3.3.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4 Directions de Newton pour le choix de '(t) = pt . . . . . . . . . . . . . 29
3.4.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Directions de Newton pour le choix de '(t) =
pt
2(1+pt) . . . . . . . . . . . 31
3.5.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6 Complexité polynomiale de ces trois algorithmes . . . . . . . . . . . . . . 33
4 Expérimentation numérique et comparaison 35
4.0.1 Paramètre barrière . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.0.2 Directions de déplacement . . . . . . . . . . . . . . . . . . . . . . 36
4.0.3 Point dÂ’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Comparaison numérique entre les trois algorithmes . . . . . . . . . . . . 44
4.3 Conclusion et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . 45Côte titre : MAM/0290 En ligne : https://drive.google.com/file/d/1ajKp3JhKjRkiTsuVvDcAyfkEMbV27t5Y/view?usp=share [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0290 MAM/0290 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Méthodes de la recherche linéaire avec rebroussement Type de document : texte imprimé Auteurs : Abed ,Ahlem, Auteur ; Merikhi,B, Directeur de thèse Editeur : Setif:UFA Année de publication : 2019 Importance : 1 vol (43 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Recherche linéaire
Recherche linéaire avec rebroussement
Fonction potentiel logarithmique
Fonction de recherche linéaireIndex. décimale : 510 Mathématique Résumé : Ce mémoire présente une étude comparative entre les différentes variantes de la recherche linéaire pour le calcul du pas de déplacement utilisé dans l’algorithme de Karmarkar en programmation linéaire.
A ce propos, on a utilisé la recherche linéaire avec rebroussement (quadratique et cubique) comme élément de comparaison avec les recherches linéaires d’Armijo et Armijo Goldstein.
Les simulations numériques effectuées sont en faveur de la variante de la recherche linéaire avec rebroussement et ce s’explique par le fait que le rebroussement évite les petits et grands pas.
Note de contenu : Sommaire
Introduction 1
1 UNE SYNTHÈSE SUR LA RECHERCHE LINÉAIRE 5
1.1 LA RECHERCHE LINÉAIRE . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Où on utilise la recherche linéaire ? . . . . . . . . . . . . . . . . 5
1.2 RECHERCHES LINÉAIRES EXACTES ET INEXACTES . . . . . . . 7
1.2.1 Recherche linéaire exacte . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Recherche linéaire inexate . . . . . . . . . . . . . . . . . . . . . 15
1.3 RECHERCHE LINÉAIRE AVEC REBROUSSEMENT . . . . . . . . . 21
2 R.L DÂ’ARMIJO AVEC REBROUSSEMENT ET SON APPLICA-
TION DANS LÂ’ALGORITHME DE KARMARKAR 25
2.1 RAPPEL SUR LA MÉTHODE DE KARMARKAR DANS LE CAS
GÉNÉRAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Algorithme de Karmarkar . . . . . . . . . . . . . . . . . . . . . 25
2.2 R.L APPLIQUÉE À L’ALGORITHME DE Karmarkar . . . . . . . . . 31
2.2.1 Calcul du pas de déplacement . . . . . . . . . . . . . . . . . . . 31
2.2.2 Procédure d’Armijo sans et avec rebroussement appliqueé dans
lÂ’algorithme de Karamarkar ( cas Rn
+ ! Sn+1 ) . . . . . . . . . . 32
3 SIMULATIONS NUMÉRIQUES 35
Conclusion et perspectives 40
Bibliographie 41Côte titre : MAM/0335 En ligne : https://drive.google.com/file/d/1kokj0Cgua8l5ynX93OVCWylezP-ZDmkc/view?usp=shari [...] Format de la ressource électronique : Méthodes de la recherche linéaire avec rebroussement [texte imprimé] / Abed ,Ahlem, Auteur ; Merikhi,B, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (43 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Recherche linéaire
Recherche linéaire avec rebroussement
Fonction potentiel logarithmique
Fonction de recherche linéaireIndex. décimale : 510 Mathématique Résumé : Ce mémoire présente une étude comparative entre les différentes variantes de la recherche linéaire pour le calcul du pas de déplacement utilisé dans l’algorithme de Karmarkar en programmation linéaire.
A ce propos, on a utilisé la recherche linéaire avec rebroussement (quadratique et cubique) comme élément de comparaison avec les recherches linéaires d’Armijo et Armijo Goldstein.
Les simulations numériques effectuées sont en faveur de la variante de la recherche linéaire avec rebroussement et ce s’explique par le fait que le rebroussement évite les petits et grands pas.
Note de contenu : Sommaire
Introduction 1
1 UNE SYNTHÈSE SUR LA RECHERCHE LINÉAIRE 5
1.1 LA RECHERCHE LINÉAIRE . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Où on utilise la recherche linéaire ? . . . . . . . . . . . . . . . . 5
1.2 RECHERCHES LINÉAIRES EXACTES ET INEXACTES . . . . . . . 7
1.2.1 Recherche linéaire exacte . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2 Recherche linéaire inexate . . . . . . . . . . . . . . . . . . . . . 15
1.3 RECHERCHE LINÉAIRE AVEC REBROUSSEMENT . . . . . . . . . 21
2 R.L DÂ’ARMIJO AVEC REBROUSSEMENT ET SON APPLICA-
TION DANS LÂ’ALGORITHME DE KARMARKAR 25
2.1 RAPPEL SUR LA MÉTHODE DE KARMARKAR DANS LE CAS
GÉNÉRAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Algorithme de Karmarkar . . . . . . . . . . . . . . . . . . . . . 25
2.2 R.L APPLIQUÉE À L’ALGORITHME DE Karmarkar . . . . . . . . . 31
2.2.1 Calcul du pas de déplacement . . . . . . . . . . . . . . . . . . . 31
2.2.2 Procédure d’Armijo sans et avec rebroussement appliqueé dans
lÂ’algorithme de Karamarkar ( cas Rn
+ ! Sn+1 ) . . . . . . . . . . 32
3 SIMULATIONS NUMÉRIQUES 35
Conclusion et perspectives 40
Bibliographie 41Côte titre : MAM/0335 En ligne : https://drive.google.com/file/d/1kokj0Cgua8l5ynX93OVCWylezP-ZDmkc/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0335 MAM/0335 Mémoire Bibliothéque des sciences Français Disponible
DisponiblePermalinkPermalinkModèle stochastique : Black et Scholes modélisation et estimation de la volatilité / Ahlem Merabtine
PermalinkPermalinkModeling and mathematical analysis of some reaction-diffusion systems driven from biology and medicine / Khaoula Imane Saffidine
PermalinkPermalinkModélisation et résolution de certains problèmes réels d’optimisation globale avec des algorithmes métaheuristiques / Douaa Karkache
PermalinkPermalinkPermalinkPermalink