University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Benterki,DJ |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Etude asymptotique des méthodes de points intérieurs pour la programmation linéaire / Bouafia,Mousaab
Titre : Etude asymptotique des méthodes de points intérieurs pour la programmation linéaire Type de document : texte imprimé Auteurs : Bouafia,Mousaab, Auteur ; Benterki,DJ, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (135 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation Linéaire
Méthode de Karmarkar
Méthode de Points IntérieursIndex. décimale : 510 Mathématique Résumé : Dans cette recherche, on s’intéresse à l’étude asymptotique des méthodes de points
intérieurs pour la programmation linéaire. En se basant sur les travaux de Schrijver et Padberg, nous
proposons deux nouveaux pas de déplacement pour accélérer la convergence de l'algorithme de
Karmarkar et réduire sa complexité algorithmique. Le premier pas est une amélioration modérée du
comportement de l'algorithme, le deuxième représente le meilleur pas de déplacement fixe obtenu
jusqu'à présent.
Ensuite nous proposons deux approches paramétrées de la l'algorithme de trajectoire centrale basé
sur les fonctions noyau. La première fonction généralise la fonction noyau proposé par Y. Q. Bai et
al., la deuxième est la première fonction noyau trigonométrique qui donne la meilleure complexité
algorithmique, obtenue jusqu'à présent.
Ces propositions ont apporté des nouvelles contributions d'ordre algorithmique, théorique et
numérique.Côte titre : DM/0127 En ligne : https://drive.google.com/file/d/1qbfHP9rkSVdxlhDfGRo8ShqV8pHui5WU/view?usp=shari [...] Format de la ressource électronique : Etude asymptotique des méthodes de points intérieurs pour la programmation linéaire [texte imprimé] / Bouafia,Mousaab, Auteur ; Benterki,DJ, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (135 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation Linéaire
Méthode de Karmarkar
Méthode de Points IntérieursIndex. décimale : 510 Mathématique Résumé : Dans cette recherche, on s’intéresse à l’étude asymptotique des méthodes de points
intérieurs pour la programmation linéaire. En se basant sur les travaux de Schrijver et Padberg, nous
proposons deux nouveaux pas de déplacement pour accélérer la convergence de l'algorithme de
Karmarkar et réduire sa complexité algorithmique. Le premier pas est une amélioration modérée du
comportement de l'algorithme, le deuxième représente le meilleur pas de déplacement fixe obtenu
jusqu'à présent.
Ensuite nous proposons deux approches paramétrées de la l'algorithme de trajectoire centrale basé
sur les fonctions noyau. La première fonction généralise la fonction noyau proposé par Y. Q. Bai et
al., la deuxième est la première fonction noyau trigonométrique qui donne la meilleure complexité
algorithmique, obtenue jusqu'à présent.
Ces propositions ont apporté des nouvelles contributions d'ordre algorithmique, théorique et
numérique.Côte titre : DM/0127 En ligne : https://drive.google.com/file/d/1qbfHP9rkSVdxlhDfGRo8ShqV8pHui5WU/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0127 DM/0127 Thèse Bibliothéque des sciences Français Disponible
DisponibleEtude numérique des méthodes de points intérieurs pour une classe de problèmes de de complémentarité linéaire basées sur une fonction noyau / Benchetta,Imene
Titre : Etude numérique des méthodes de points intérieurs pour une classe de problèmes de de complémentarité linéaire basées sur une fonction noyau Type de document : texte imprimé Auteurs : Benchetta,Imene, Auteur ; Benterki,DJ, Directeur de thèse Editeur : Setif:UFA Année de publication : 2019 Importance : 1 vol (60 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Méthodes de points intérieure
Problème de complémentarité linéaireIndex. décimale : 510 Mathématique Note de contenu : Sommaire
Introduction 1
1 Calcul matriciel et analyse convexe 5
1.1 Calcul matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Rappels et dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Produit scalaire et normes . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Eléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Opérations préservant la convexité . . . . . . . . . . . . . . . . . 8
1.2.3 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.4 Caractérisation d’une fonction convexe di¤érentiable . . . . . . . 11
2 Problème de complémentarité linéaire (PCL) 13
2.1 Position du PCL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Relation entre le PCL et d’autres problèmes d’optimisation . . . . . . . 14
2.2.1 Conditions d’optimalité d’un problème d’optimisation quadratique 14
2.2.2 Programme quadratique associé à un PCL . . . . . . . . . . . . . 16
2.3 L’existence et l’unicité de la solution d’un PCL . . . . . . . . . . . . . . 17
2.3.1 Galerie de matrices adaptées . . . . . . . . . . . . . . . . . . . . . 17
1
2.3.2 Classe des QCôte titre : MAM/0305 En ligne : https://drive.google.com/file/d/1VIfGWt7dLWP07PJ03Cbg6yFbAhF3JeJH/view?usp=shari [...] Format de la ressource électronique : Etude numérique des méthodes de points intérieurs pour une classe de problèmes de de complémentarité linéaire basées sur une fonction noyau [texte imprimé] / Benchetta,Imene, Auteur ; Benterki,DJ, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (60 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Méthodes de points intérieure
Problème de complémentarité linéaireIndex. décimale : 510 Mathématique Note de contenu : Sommaire
Introduction 1
1 Calcul matriciel et analyse convexe 5
1.1 Calcul matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Rappels et dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Produit scalaire et normes . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Eléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 Opérations préservant la convexité . . . . . . . . . . . . . . . . . 8
1.2.3 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.4 Caractérisation d’une fonction convexe di¤érentiable . . . . . . . 11
2 Problème de complémentarité linéaire (PCL) 13
2.1 Position du PCL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Relation entre le PCL et d’autres problèmes d’optimisation . . . . . . . 14
2.2.1 Conditions d’optimalité d’un problème d’optimisation quadratique 14
2.2.2 Programme quadratique associé à un PCL . . . . . . . . . . . . . 16
2.3 L’existence et l’unicité de la solution d’un PCL . . . . . . . . . . . . . . 17
2.3.1 Galerie de matrices adaptées . . . . . . . . . . . . . . . . . . . . . 17
1
2.3.2 Classe des QCôte titre : MAM/0305 En ligne : https://drive.google.com/file/d/1VIfGWt7dLWP07PJ03Cbg6yFbAhF3JeJH/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0305 MAM/0305 Mémoire Bibliothéque des sciences Français Disponible
DisponibleEtude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire / Menniche, Linda
Titre : Etude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire Type de document : texte imprimé Auteurs : Menniche, Linda, Auteur ; Benterki,DJ, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (78 f.) Format : 29cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation linéaire
Méthode de Points Intérieurs
Méthodebarrière logarithmique
Fonction majoranteIndex. décimale : 519 Mathématiques appliquées, probabilités (statistiques mathématiques) Résumé :
Ce travail concerne l'étude théorique, algorithmique et numérique d'une
méthode barrière logarithmique pour résoudre un problème de
programmation linéaire (PL). Nous mettons l'accent sur le calcul de la direction
moyennant l'approche de Newton, et le calcul du pas de déplacement en
utilisant de nouvelles fonctions majorantes dans le but de réduire le coût de
calcul. Des résultats théoriques sont présentés donnant lieu à l'existence et
l'unicité de la solution optimale du problème approché de (PL) ainsi que sa
convergence vers celle de (PL). Ce travail est consolidé par des tests
numériques réalisés sur l'algorithme obtenu.Note de contenu :
Sommaire
Introduction
1 Préliminaires et notions fondamentales 7
1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Ensembles et fonctions affnes . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Notions de convexité. . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Convexite et dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Fonction barriére . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.5 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . 13
1.2 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Formes usuelles d'un programme linéaire . . . . . . . . . . . . . . . . . . . 19
1.3.1 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.2 Forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 Dualité en programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 20
2 Méthodes de resolution d'un programme linéaire 24
2.1 Domaines d'applications de la programmation linéaire . . . . . . . . . . . . 24
2.1.1 Exemples concrets de problemes de programmation linéaire . . . . . 26
2.2 Méthode de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.1 Caractéristiques de l'algorithme du simplexe . . . . . . . . . . . . . 34
2.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1 Méthodes affnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Algorithme de la méthode affne primale . . . . . . . . . . . . . . . 39
2.3.3 Méthode de réduction du potentiel . . . . . . . . . . . . . . . . . . 42
2.3.4 Méthodes de trajectoire centrale . . . . . . . . . . . . . . . . . . . . 43
2.3.5 Méthodes de trajectoire centrale primales-duales . . . . . . . . . . . 45
2.4 Résultats de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Méthode barriére logarithmique via les fonctions majorantes 52
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2 Aspect theorique du probléme (DLr) . . . . . . . . . . . . . . . . . . . . . 54
3.2.1 Existence de la solution du probléme (DLr) . . . . . . . . . . . . . 54
3.2.2 Unicite de la solution du probléme (DLr) . . . . . . . . . . . . . . . 55
3.2.3 Convergence de (DLr) vers (DL) lorsque r tend vers zéro . . . . . . 56
3.3 Aspect numérique du probléme (DLr) . . . . . . . . . . . . . . . . . . . . 57
3.3.1 Calcul du pas de déplacement tk . . . . . . . . . . . . . . . . . . . . 59
3.3.2 Calcul des différentes valeurs debt
. . . . . . . . . . . . . . . . . . . 61
3.4 Fonctions majorantes de t . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.4.1 Premiére fonction majorante . . . . . . . . . . . . . . . . . . . . . . 63
3.4.2 Seconde fonction majorante . . . . . . . . . . . . . . . . . . . . . . 64
3.4.3 Troisiéme fonction majorante . . . . . . . . . . . . . . . . . . . . . 65
3.5 Tests numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.1 Exemples a dimension xe . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Exemple a dimension variable . . . . . . . . . . . . . . . . . . . . . 72
Conclusion 73
Bibliographie
Côte titre : MD/122 Etude théorique et numérique d’une classe de méthodes de points intérieurs pour la programmation linéaire [texte imprimé] / Menniche, Linda, Auteur ; Benterki,DJ, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (78 f.) ; 29cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation linéaire
Méthode de Points Intérieurs
Méthodebarrière logarithmique
Fonction majoranteIndex. décimale : 519 Mathématiques appliquées, probabilités (statistiques mathématiques) Résumé :
Ce travail concerne l'étude théorique, algorithmique et numérique d'une
méthode barrière logarithmique pour résoudre un problème de
programmation linéaire (PL). Nous mettons l'accent sur le calcul de la direction
moyennant l'approche de Newton, et le calcul du pas de déplacement en
utilisant de nouvelles fonctions majorantes dans le but de réduire le coût de
calcul. Des résultats théoriques sont présentés donnant lieu à l'existence et
l'unicité de la solution optimale du problème approché de (PL) ainsi que sa
convergence vers celle de (PL). Ce travail est consolidé par des tests
numériques réalisés sur l'algorithme obtenu.Note de contenu :
Sommaire
Introduction
1 Préliminaires et notions fondamentales 7
1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Ensembles et fonctions affnes . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Notions de convexité. . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Convexite et dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.4 Fonction barriére . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.5 Programmation mathématique . . . . . . . . . . . . . . . . . . . . . 13
1.2 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Formes usuelles d'un programme linéaire . . . . . . . . . . . . . . . . . . . 19
1.3.1 Forme standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.2 Forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 Dualité en programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 20
2 Méthodes de resolution d'un programme linéaire 24
2.1 Domaines d'applications de la programmation linéaire . . . . . . . . . . . . 24
2.1.1 Exemples concrets de problemes de programmation linéaire . . . . . 26
2.2 Méthode de simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.1 Caractéristiques de l'algorithme du simplexe . . . . . . . . . . . . . 34
2.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1 Méthodes affnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Algorithme de la méthode affne primale . . . . . . . . . . . . . . . 39
2.3.3 Méthode de réduction du potentiel . . . . . . . . . . . . . . . . . . 42
2.3.4 Méthodes de trajectoire centrale . . . . . . . . . . . . . . . . . . . . 43
2.3.5 Méthodes de trajectoire centrale primales-duales . . . . . . . . . . . 45
2.4 Résultats de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3 Méthode barriére logarithmique via les fonctions majorantes 52
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2 Aspect theorique du probléme (DLr) . . . . . . . . . . . . . . . . . . . . . 54
3.2.1 Existence de la solution du probléme (DLr) . . . . . . . . . . . . . 54
3.2.2 Unicite de la solution du probléme (DLr) . . . . . . . . . . . . . . . 55
3.2.3 Convergence de (DLr) vers (DL) lorsque r tend vers zéro . . . . . . 56
3.3 Aspect numérique du probléme (DLr) . . . . . . . . . . . . . . . . . . . . 57
3.3.1 Calcul du pas de déplacement tk . . . . . . . . . . . . . . . . . . . . 59
3.3.2 Calcul des différentes valeurs debt
. . . . . . . . . . . . . . . . . . . 61
3.4 Fonctions majorantes de t . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.4.1 Premiére fonction majorante . . . . . . . . . . . . . . . . . . . . . . 63
3.4.2 Seconde fonction majorante . . . . . . . . . . . . . . . . . . . . . . 64
3.4.3 Troisiéme fonction majorante . . . . . . . . . . . . . . . . . . . . . 65
3.5 Tests numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.5.1 Exemples a dimension xe . . . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Exemple a dimension variable . . . . . . . . . . . . . . . . . . . . . 72
Conclusion 73
Bibliographie
Côte titre : MD/122 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MD/122 MD/122 Mémoire Bibliothéque des sciences Français Disponible
DisponibleLaméthod de newton régularisée avec correction pour l'optimisation convexe sans contraintes / Larabi,Yasmina
Titre : Laméthod de newton régularisée avec correction pour l'optimisation convexe sans contraintes Type de document : texte imprimé Auteurs : Larabi,Yasmina, Auteur ; Benterki,DJ, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (49 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Méthode de newton Régularisée
Technique de correction
Optimisation sans contraintesIndex. décimale : 510 Mathématique Note de contenu : Sommaire
Introduction 2
1 Rappel sur lÂ’analyse convexe 6
1.1 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Convexité et la dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Caractérisation de la convexité en termes du Hessien . . . . . . . . . . . 9
1.5 Caractérisation de la convexité en termes du gradient . . . . . . . . . . . 10
1.6 Résultats d’existence et d’unicité d’un problème d’optimisation sans contraintes 11
1.6.1 Conditions nécessaires . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6.2 Conditions nécessaires et su¢ santes . . . . . . . . . . . . . . . . . 11
2 Méthodes de résolution d’un problème d’optimisation sans contraintes 13
2.1 Méthodes de descente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Principe et algorithme des méthodes de descente . . . . . . . . . . 13
2.2 Méthode de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Principe et algorithme des méthodes de gradient . . . . . . . . . . 15
2.3 Méthode du gradient conjuguée . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Principe et algorithme des méthodes du gradient conjuguée . . . . 16
2.3.2 Convergence de la méthode du gradient conjuguée . . . . . . . . . 18
1
2.4 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.1 Principe et algorithme de la méthode de Newton . . . . . . . . . . 18
2.4.2 Convergence de la méthode de Newton . . . . . . . . . . . . . . . 20
2.4.3 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.4 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Méthode Quasi-Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5.2 Méthode de correction de rang un . . . . . . . . . . . . . . . . . . 24
2.5.3 Méthode de Davidon-Fletcher-Powell (DFP) . . . . . . . . . . . . 27
2.5.4 Méthode de Broyden-Fletcher-Goldfarb-Shanno (BFGS) . . . . . 30
3 Méthode de Newton régularisée avec correction pour l’optimisation
convexe sans contraintes 33
3.1 Principe de la méthode de Newton régularisée avec correction . . . . . . 33
3.2 LÂ’algorithme et sa convergence globale . . . . . . . . . . . . . . . . . . . 35
3.2.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.2 Convergence de la méthode de Newton régularisée avec correction 40
3.3 Implémentation numérique . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Conclusion 46
BibliographieCôte titre : MAM/0296 En ligne : https://drive.google.com/file/d/1_wEs-ZOtZQLaJesyZumw1i7uSkO2ajkW/view?usp=shari [...] Format de la ressource électronique : Laméthod de newton régularisée avec correction pour l'optimisation convexe sans contraintes [texte imprimé] / Larabi,Yasmina, Auteur ; Benterki,DJ, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (49 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Méthode de newton Régularisée
Technique de correction
Optimisation sans contraintesIndex. décimale : 510 Mathématique Note de contenu : Sommaire
Introduction 2
1 Rappel sur lÂ’analyse convexe 6
1.1 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Convexité et la dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Caractérisation de la convexité en termes du Hessien . . . . . . . . . . . 9
1.5 Caractérisation de la convexité en termes du gradient . . . . . . . . . . . 10
1.6 Résultats d’existence et d’unicité d’un problème d’optimisation sans contraintes 11
1.6.1 Conditions nécessaires . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6.2 Conditions nécessaires et su¢ santes . . . . . . . . . . . . . . . . . 11
2 Méthodes de résolution d’un problème d’optimisation sans contraintes 13
2.1 Méthodes de descente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Principe et algorithme des méthodes de descente . . . . . . . . . . 13
2.2 Méthode de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Principe et algorithme des méthodes de gradient . . . . . . . . . . 15
2.3 Méthode du gradient conjuguée . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Principe et algorithme des méthodes du gradient conjuguée . . . . 16
2.3.2 Convergence de la méthode du gradient conjuguée . . . . . . . . . 18
1
2.4 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.1 Principe et algorithme de la méthode de Newton . . . . . . . . . . 18
2.4.2 Convergence de la méthode de Newton . . . . . . . . . . . . . . . 20
2.4.3 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.4 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Méthode Quasi-Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5.2 Méthode de correction de rang un . . . . . . . . . . . . . . . . . . 24
2.5.3 Méthode de Davidon-Fletcher-Powell (DFP) . . . . . . . . . . . . 27
2.5.4 Méthode de Broyden-Fletcher-Goldfarb-Shanno (BFGS) . . . . . 30
3 Méthode de Newton régularisée avec correction pour l’optimisation
convexe sans contraintes 33
3.1 Principe de la méthode de Newton régularisée avec correction . . . . . . 33
3.2 LÂ’algorithme et sa convergence globale . . . . . . . . . . . . . . . . . . . 35
3.2.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.2 Convergence de la méthode de Newton régularisée avec correction 40
3.3 Implémentation numérique . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Conclusion 46
BibliographieCôte titre : MAM/0296 En ligne : https://drive.google.com/file/d/1_wEs-ZOtZQLaJesyZumw1i7uSkO2ajkW/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0296 MAM/0296 Mémoire Bibliothéque des sciences Français Disponible
Disponible