University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Boubakeur Seddik Hamani |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheUne méthode de point intérieur correcteur-prédicteur avec une nouvelle direction de recherche pour l'optimisation linéaire / Boubakeur Seddik Hamani
Titre : Une méthode de point intérieur correcteur-prédicteur avec une nouvelle direction de recherche pour l'optimisation linéaire Type de document : texte imprimé Auteurs : Boubakeur Seddik Hamani, Auteur ; Abderrahim Gana, Auteur ; Louiza Derbal, Directeur de thèse Editeur : Sétif:UFS Année de publication : 2024 Importance : 1 vol (f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation linéaire
Méthodes des points intérieurs primal-dual
Transformation algébrique équivalente
Algorithme correcteur-prédicteur.Index. décimale : 510-Mathématique Résumé : Dans ce mémoire, nous avons présenté une étude théorique et numérique comparative de
l'algorithme de point intérieur primal-dual de type correcteur-prédicteur. Cette technique, définie
par Darvay (2020), repose sur de nouvelles directions de recherche en introduisant une
transformation algébrique équivalente sur l'équation du chemin central.
L'algorithme étudié a une complexité polynomiale, et les résultats numériques obtenus en
introduisant de nouvelles transformations sont encourageants et d'une grande importanceNote de contenu :
Sommaire
Table des matières vi
Liste des abbreviations et notations 1
Introduction 3
1 Rappels sur l’analyse convexe et la programmation linéaire 6
1.1 Produit scalaire et norme . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Eléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Caractérisation d’une fonction convexe différentiable . . . . . . 9
1.3 Optimisation linéaire ( Programation linéaire) . . . . . . . . . . . . . . 10
1.3.1 Forme usuelle d’un programme linéaire . . . . . . . . . . . . . 10
1.3.2 Condition d’optimalité pour un (PL) . . . . . . . . . . . . . . . 11
1.3.3 Dualité en programmation linéaire . . . . . . . . . . . . . . . . 12
1.3.4 Méthodes de résolution d’un (PL) . . . . . . . . . . . . . . . . . 13
1.4 Méthode de Newton pour un système non linéaire . . . . . . . . . . . . 14
2 Algorithme de point intérieur de type correcteur-prédicteur pour la
programmation linéaire 16
2.1 Programmation linéaire primale-duale . . . . . . . . . . . . . . . . . . 16
2.2 Méthode de trajectoire centrale . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Nouvelle classe de directions de Newton . . . . . . . . . . . . . . . . . 18
2.3.1 La mesure de proximité . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Algorithme correcteur-prédicteur . . . . . . . . . . . . . . . . . . . . . 20
2.4.1 Description de l’algorithme . . . . . . . . . . . . . . . . . . . . . 20
2.5 Analyse de l’algorithmeé . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5.1 L’étape du correcteur . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5.2 L’étape du prédicteur . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Expérimentations numériques et commentaires 35
3.1 Etude numérique comparative . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 Exemples à taille fixe . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.2 Exemples à taille variable . . . . . . . . . . . . . . . . . . . . . 42
3.2 Amélioration de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Côte titre : MAM/0757 Une méthode de point intérieur correcteur-prédicteur avec une nouvelle direction de recherche pour l'optimisation linéaire [texte imprimé] / Boubakeur Seddik Hamani, Auteur ; Abderrahim Gana, Auteur ; Louiza Derbal, Directeur de thèse . - [S.l.] : Sétif:UFS, 2024 . - 1 vol (f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation linéaire
Méthodes des points intérieurs primal-dual
Transformation algébrique équivalente
Algorithme correcteur-prédicteur.Index. décimale : 510-Mathématique Résumé : Dans ce mémoire, nous avons présenté une étude théorique et numérique comparative de
l'algorithme de point intérieur primal-dual de type correcteur-prédicteur. Cette technique, définie
par Darvay (2020), repose sur de nouvelles directions de recherche en introduisant une
transformation algébrique équivalente sur l'équation du chemin central.
L'algorithme étudié a une complexité polynomiale, et les résultats numériques obtenus en
introduisant de nouvelles transformations sont encourageants et d'une grande importanceNote de contenu :
Sommaire
Table des matières vi
Liste des abbreviations et notations 1
Introduction 3
1 Rappels sur l’analyse convexe et la programmation linéaire 6
1.1 Produit scalaire et norme . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Eléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Ensembles convexes . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Caractérisation d’une fonction convexe différentiable . . . . . . 9
1.3 Optimisation linéaire ( Programation linéaire) . . . . . . . . . . . . . . 10
1.3.1 Forme usuelle d’un programme linéaire . . . . . . . . . . . . . 10
1.3.2 Condition d’optimalité pour un (PL) . . . . . . . . . . . . . . . 11
1.3.3 Dualité en programmation linéaire . . . . . . . . . . . . . . . . 12
1.3.4 Méthodes de résolution d’un (PL) . . . . . . . . . . . . . . . . . 13
1.4 Méthode de Newton pour un système non linéaire . . . . . . . . . . . . 14
2 Algorithme de point intérieur de type correcteur-prédicteur pour la
programmation linéaire 16
2.1 Programmation linéaire primale-duale . . . . . . . . . . . . . . . . . . 16
2.2 Méthode de trajectoire centrale . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Nouvelle classe de directions de Newton . . . . . . . . . . . . . . . . . 18
2.3.1 La mesure de proximité . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Algorithme correcteur-prédicteur . . . . . . . . . . . . . . . . . . . . . 20
2.4.1 Description de l’algorithme . . . . . . . . . . . . . . . . . . . . . 20
2.5 Analyse de l’algorithmeé . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5.1 L’étape du correcteur . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5.2 L’étape du prédicteur . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Expérimentations numériques et commentaires 35
3.1 Etude numérique comparative . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 Exemples à taille fixe . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1.2 Exemples à taille variable . . . . . . . . . . . . . . . . . . . . . 42
3.2 Amélioration de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Côte titre : MAM/0757 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0757 MAM/0757 Mémoire Bibliothéque des sciences Français Disponible
Disponible
