University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Goutali, Moufida |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la rechercheComplexité et implémentation numérique d’une méthode de points intérieurs pour la programmation convexe / Goutali, Moufida
Titre : Complexité et implémentation numérique d’une méthode de points intérieurs pour la programmation convexe Type de document : texte imprimé Auteurs : Goutali, Moufida, Auteur ; Achache, M, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (92 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation convexe acontraintes linéaires
Complexité des AgorithmesIndex. décimale : 510 Mathématique Résumé : Résumé
Dans cette thèse, on s’intéresse à l’étude théorique (notamment la complexité polynomi-
ale) et à l’implémentation numérique d’une méthode de points intérieurs de trajectoire
centrale de type primal-dual pour résoudre les problèmes de la programmation convexe Ã
contraintes linéaires (PCCL). Dans notre étude, nous proposons de nouveaux paramètres
qui décrivent le paramètre barrière et le seuil qui mesure la taille du voisinage de la
trajectoire centrale. À travers ces derniers, un algorithme primal-dual à pas court et
d’itération de Newton complet bien dé…ni est présenté et de plus sa complexité est cal-
culée. L’e¢ cacité numérique de cet algorithme est con…rmée par des tests numériques.
Note de contenu : Sommaire
Analyse convexe et programmation mathématique 14
1.1 Éléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.1 Dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.2 Ensemble a¢ ne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.3 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.4 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.5 Cônes Convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 Programmation Mathématique . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1 Solutions optimales locales et globales . . . . . . . . . . . . . . . 18
1.2.2 Classi…cation d’un programme mathématique . . . . . . . . . . . 19
1.2.3 QualiÂ…cation des contraintes . . . . . . . . . . . . . . . . . . . . . 19
1.2.4 Résolution d’un programme mathématique . . . . . . . . . . . . . 20
1.3 Programmation convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.1 Existence (unicité) d’une solution optimale . . . . . . . . . . . . . 22
1.3.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.3 Le dual dÂ’un programme convexe . . . . . . . . . . . . . . . . . . 23
1.4 Algorithme dÂ’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5 Méthode de Newton-Raphson pour un système non linéaire . . . . . . . . 27
1.6 Méthodes de résolution d’un programme mathématique . . . . . . . . . . 28
1.6.1 Méthodes de type gradient . . . . . . . . . . . . . . . . . . . . . . 28
1.6.2 Méthodes simpliciales . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . 29
2 Méthodes de points intérieurs de type de TC pour (PCCL) 32
2.1 Existence et unicité de la trajectoire centrale (suivi de chemin) pour PCCL 32
2.1.1 Le problème perturbé . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.2 Les conditions d’optimalité de (K.K.T) . . . . . . . . . . . . . . 34
2.1.3 Le chemin central est bien dé…ni . . . . . . . . . . . . . . . . . . . 36
2.1.4 Le Théorème principal de la trajectoire centrale . . . . . . . . . . 37
2.2 Principe des méthodes de trajectoire centrale . . . . . . . . . . . . . . . . 40
2.2.1 Concept de proximité ou de centralisation . . . . . . . . . . . . . 41
2.2.2 Mise à jour du paramètre barrière . . . . . . . . . . . . . . . . . 42
2.2.3 Itération de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.4 Pas de déplacement . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3 Algorithme générale primal-dual de suivi de trajectoire . . . . . . . . . . 44
3 Méthodes primal-dual pour (PCCL) 45
3.1 Directions de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.1 Description algorithmique . . . . . . . . . . . . . . . . . . . . . . 48
3.1.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Convergence de l’algorithme et analyse de la complexité . . . . . . . . . . 49
3.2.1 Résultats préliminaires . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.2 Analyse de la faisabilité . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.3 Analyse de la complexité . . . . . . . . . . . . . . . . . . . . . . . 56
4 Simulation numérique 58
4.1 Mise en Âœuvre de cet algorithme . . . . . . . . . . . . . . . . . . . . . . 58
4.1.1 Paramètre barrière . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.1.2 Directions de déplacement . . . . . . . . . . . . . . . . . . . . . . 59
4.1.3 Point dÂ’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.1 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.2 Programmation quadratique . . . . . . . . . . . . . . . . . . . . . 66
4.2.3 Cas dÂ’une fonction convexe . . . . . . . . . . . . . . . . . . . . . 72
4.2.4 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4 Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Côte titre : DM/0140 En ligne : https://drive.google.com/file/d/1N-LtJ9dgX_smqAuQLpOV4bz1Rg28767N/view?usp=shari [...] Format de la ressource électronique : Complexité et implémentation numérique d’une méthode de points intérieurs pour la programmation convexe [texte imprimé] / Goutali, Moufida, Auteur ; Achache, M, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (92 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation convexe acontraintes linéaires
Complexité des AgorithmesIndex. décimale : 510 Mathématique Résumé : Résumé
Dans cette thèse, on s’intéresse à l’étude théorique (notamment la complexité polynomi-
ale) et à l’implémentation numérique d’une méthode de points intérieurs de trajectoire
centrale de type primal-dual pour résoudre les problèmes de la programmation convexe Ã
contraintes linéaires (PCCL). Dans notre étude, nous proposons de nouveaux paramètres
qui décrivent le paramètre barrière et le seuil qui mesure la taille du voisinage de la
trajectoire centrale. À travers ces derniers, un algorithme primal-dual à pas court et
d’itération de Newton complet bien dé…ni est présenté et de plus sa complexité est cal-
culée. L’e¢ cacité numérique de cet algorithme est con…rmée par des tests numériques.
Note de contenu : Sommaire
Analyse convexe et programmation mathématique 14
1.1 Éléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.1 Dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.2 Ensemble a¢ ne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.3 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.4 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.5 Cônes Convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 Programmation Mathématique . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1 Solutions optimales locales et globales . . . . . . . . . . . . . . . 18
1.2.2 Classi…cation d’un programme mathématique . . . . . . . . . . . 19
1.2.3 QualiÂ…cation des contraintes . . . . . . . . . . . . . . . . . . . . . 19
1.2.4 Résolution d’un programme mathématique . . . . . . . . . . . . . 20
1.3 Programmation convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.1 Existence (unicité) d’une solution optimale . . . . . . . . . . . . . 22
1.3.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.3 Le dual dÂ’un programme convexe . . . . . . . . . . . . . . . . . . 23
1.4 Algorithme dÂ’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5 Méthode de Newton-Raphson pour un système non linéaire . . . . . . . . 27
1.6 Méthodes de résolution d’un programme mathématique . . . . . . . . . . 28
1.6.1 Méthodes de type gradient . . . . . . . . . . . . . . . . . . . . . . 28
1.6.2 Méthodes simpliciales . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . 29
2 Méthodes de points intérieurs de type de TC pour (PCCL) 32
2.1 Existence et unicité de la trajectoire centrale (suivi de chemin) pour PCCL 32
2.1.1 Le problème perturbé . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.2 Les conditions d’optimalité de (K.K.T) . . . . . . . . . . . . . . 34
2.1.3 Le chemin central est bien dé…ni . . . . . . . . . . . . . . . . . . . 36
2.1.4 Le Théorème principal de la trajectoire centrale . . . . . . . . . . 37
2.2 Principe des méthodes de trajectoire centrale . . . . . . . . . . . . . . . . 40
2.2.1 Concept de proximité ou de centralisation . . . . . . . . . . . . . 41
2.2.2 Mise à jour du paramètre barrière . . . . . . . . . . . . . . . . . 42
2.2.3 Itération de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.4 Pas de déplacement . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3 Algorithme générale primal-dual de suivi de trajectoire . . . . . . . . . . 44
3 Méthodes primal-dual pour (PCCL) 45
3.1 Directions de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.1 Description algorithmique . . . . . . . . . . . . . . . . . . . . . . 48
3.1.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Convergence de l’algorithme et analyse de la complexité . . . . . . . . . . 49
3.2.1 Résultats préliminaires . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.2 Analyse de la faisabilité . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.3 Analyse de la complexité . . . . . . . . . . . . . . . . . . . . . . . 56
4 Simulation numérique 58
4.1 Mise en Âœuvre de cet algorithme . . . . . . . . . . . . . . . . . . . . . . 58
4.1.1 Paramètre barrière . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.1.2 Directions de déplacement . . . . . . . . . . . . . . . . . . . . . . 59
4.1.3 Point dÂ’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.1 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.2 Programmation quadratique . . . . . . . . . . . . . . . . . . . . . 66
4.2.3 Cas dÂ’une fonction convexe . . . . . . . . . . . . . . . . . . . . . 72
4.2.4 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4 Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Côte titre : DM/0140 En ligne : https://drive.google.com/file/d/1N-LtJ9dgX_smqAuQLpOV4bz1Rg28767N/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0140 DM/0140 Thèse Bibliothèque des sciences Français Disponible
Disponible
Titre : Developing an Interior Point Method for Convex Quadratic Programming Type de document : document électronique Auteurs : Lina Tesslim Sinacer, Auteur ; Rania Grachi, Auteur ; Goutali, Moufida, Directeur de thèse Editeur : Sétif:UFS Année de publication : 2025 Importance : 1 vol (47 f.) Format : 29 cm Langues : Anglais (eng) Mots-clés : Convex Quadratic Programming
Algebraic Transformation
Centrality Condition
Search Direction
Convergence Analysis
Complexity Analysis
Numerical ExperimentsRésumé : This thesis deal with the development of a primal-dual interior-point method for solving convex
quadratic programming problems. The proposed approach is based on an algebraic transformation
of the centrality condition in order to derive a new search direction that improves the efficiency and
numerical performance of the algorithm. The theoretical properties of the method are investigated
through convergence and computational complexity analyses. In addition, numerical experiments
are conducted on a set of benchmark problems. The obtained results demonstrate that the proposed
method efficiently reaches the optimal solution with a small number of iterations and satisfactory
computational performance, confirming its effectiveness for solving convex quadratic programming
problems.Note de contenu : Contents
Glossary of Notation 8
Introduction 11
1 Convex Analysis and Mathematical Programming 14
1.1 Basic Elements of Convex Analysis . . . . . . . . . . . . . . . . . . . . . . 14
1.2 Mathematical Programming . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.1 Local and Global Optimal Solutions . . . . . . . . . . . . . . . . . 16
1.2.2 Classification of mathematical programs . . . . . . . . . . . . . . 17
1.2.3 Qualification of constraints . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Solving Mathematical Programming Problems . . . . . . . . . . . . . . . 18
1.3.1 Existence and Uniqueness of Optimal Solutions . . . . . . . . . . 18
1.3.2 Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4 Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Convex Quadratic Programming . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.1 Solution Methods for Convex Quadratic Optimization . . . . . . 21
1.5.2 Perturbed Problem (Logarithmic Barrier) . . . . . . . . . . . . . . 21
2 A New Short-Step IPA for Convex Quadratic Optimization 23
2.1 The new search direction for CQO by using AET . . . . . . . . . . . . . . 24
2.1.1 The Proximity Measure . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.2 Primal–Dual IP Algorithm for CQO . . . . . . . . . . . . . . . . . 27
2.2 Convergence Behavior and Computational Complexity of the Proposed Algorithm . . 28
2.2.1 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.2 Feasibility Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.3 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Numerical experimentation 37
3.1 Examples with fixed size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.1 Results of Examples (Table (3.1)) . . . . . . . . . . . . . . . . . . . 41
3.2 Example with variable size . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2.1 Results of Example (Table (3.2)) . . . . . . . . . . . . . . . . . . . . 43
3.3 Discussion of Numerical Results . . . . . . . . . . . . . . . . . . . . . . . 44
Conclusion 45
Bibliography 46Côte titre : MAM/0849 En ligne : https://repository.univ-setif.dz/server/api/core/bitstreams/371bdd13-f54d-4023-b [...] Developing an Interior Point Method for Convex Quadratic Programming [document électronique] / Lina Tesslim Sinacer, Auteur ; Rania Grachi, Auteur ; Goutali, Moufida, Directeur de thèse . - [S.l.] : Sétif:UFS, 2025 . - 1 vol (47 f.) ; 29 cm.
Langues : Anglais (eng)
Mots-clés : Convex Quadratic Programming
Algebraic Transformation
Centrality Condition
Search Direction
Convergence Analysis
Complexity Analysis
Numerical ExperimentsRésumé : This thesis deal with the development of a primal-dual interior-point method for solving convex
quadratic programming problems. The proposed approach is based on an algebraic transformation
of the centrality condition in order to derive a new search direction that improves the efficiency and
numerical performance of the algorithm. The theoretical properties of the method are investigated
through convergence and computational complexity analyses. In addition, numerical experiments
are conducted on a set of benchmark problems. The obtained results demonstrate that the proposed
method efficiently reaches the optimal solution with a small number of iterations and satisfactory
computational performance, confirming its effectiveness for solving convex quadratic programming
problems.Note de contenu : Contents
Glossary of Notation 8
Introduction 11
1 Convex Analysis and Mathematical Programming 14
1.1 Basic Elements of Convex Analysis . . . . . . . . . . . . . . . . . . . . . . 14
1.2 Mathematical Programming . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.1 Local and Global Optimal Solutions . . . . . . . . . . . . . . . . . 16
1.2.2 Classification of mathematical programs . . . . . . . . . . . . . . 17
1.2.3 Qualification of constraints . . . . . . . . . . . . . . . . . . . . . . 17
1.3 Solving Mathematical Programming Problems . . . . . . . . . . . . . . . 18
1.3.1 Existence and Uniqueness of Optimal Solutions . . . . . . . . . . 18
1.3.2 Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4 Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Convex Quadratic Programming . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.1 Solution Methods for Convex Quadratic Optimization . . . . . . 21
1.5.2 Perturbed Problem (Logarithmic Barrier) . . . . . . . . . . . . . . 21
2 A New Short-Step IPA for Convex Quadratic Optimization 23
2.1 The new search direction for CQO by using AET . . . . . . . . . . . . . . 24
2.1.1 The Proximity Measure . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.2 Primal–Dual IP Algorithm for CQO . . . . . . . . . . . . . . . . . 27
2.2 Convergence Behavior and Computational Complexity of the Proposed Algorithm . . 28
2.2.1 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.2 Feasibility Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.3 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Numerical experimentation 37
3.1 Examples with fixed size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.1 Results of Examples (Table (3.1)) . . . . . . . . . . . . . . . . . . . 41
3.2 Example with variable size . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.2.1 Results of Example (Table (3.2)) . . . . . . . . . . . . . . . . . . . . 43
3.3 Discussion of Numerical Results . . . . . . . . . . . . . . . . . . . . . . . 44
Conclusion 45
Bibliography 46Côte titre : MAM/0849 En ligne : https://repository.univ-setif.dz/server/api/core/bitstreams/371bdd13-f54d-4023-b [...] Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0849 MAM/0849 Mémoire Bibliothèque des sciences Anglais Disponible
Disponible
