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 importance
Note 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Cô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 importance
Note 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Côte titre :	MAM/0757