University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Malek Mihoubi |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : On A Variant Of Primal-Dual Interior Point Method For Linear Optimization Type de document : document électronique Auteurs : Malek Mihoubi, Auteur ; Oumaima Boucekkine, Auteur ; Djamel Benterki, Directeur de thèse Editeur : Sétif:UFS Année de publication : 2025 Importance : 1 vol (43 f.) Format : 29 cm Langues : Anglais (eng) Mots-clés : Linear programming
Interior point method
Descent direction
Algorithmic complexityRésumé : In this manuscript, we are interested in solving a linear programming
problem using a primal-dual interior point method. Inspired by the work
of Zhang and Xu (2011), we propose a new descent direction through a
modified transformation of the complementarity condition in the
system that defines the central path. A comprehensive theoretical and
numerical study has been carried out to achieve our objective.
Note de contenu : Contents
Glossary of abbreviations and notations ii
Introduction iii
1 Concepts of convex analysis and optimization 1
1.1 Convex analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Convex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Characterization of differentiable convex function . . . . . . . . . 2
1.2 Mathematical programming . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Classification of mathematical program . . . . . . . . . . . . . . . 4
1.2.3 Constraints qualification . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 Optimality conditions . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Dual of the primal problem . . . . . . . . . . . . . . . . . . . . . . 6
1.3.3 Duality in linear programming . . . . . . . . . . . . . . . . . . . . 7
2 Interior point algorithm based on Zhang and Xu’s technique 8
2.1 Position of linear programming . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 The classical central path method . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Descent direction based on Zhang and Xu’s technique . . . . . . . . . . . 10
2.4 Generic primal-dual IPA for LP . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5 Convergence and complexity analysis . . . . . . . . . . . . . . . . . . . . 12
3 New descent direction for linear programming 14
3.1 Interior point algorithm for LP . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1.1 Generic primal-dual IPA for LP . . . . . . . . . . . . . . . . . . . . 16
3.2 Convergence and complexity analysis . . . . . . . . . . . . . . . . . . . . 16
3.3 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.1 Fixed-size examples . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.2 Variable-size example . . . . . . . . . . . . . . . . . . . . . . . . . 37
Conclusion 42
Bibliography 43Côte titre : MAM/0848 En ligne : https://repository.univ-setif.dz/server/api/core/bitstreams/91a357e0-32d7-490c-a [...] On A Variant Of Primal-Dual Interior Point Method For Linear Optimization [document électronique] / Malek Mihoubi, Auteur ; Oumaima Boucekkine, Auteur ; Djamel Benterki, Directeur de thèse . - [S.l.] : Sétif:UFS, 2025 . - 1 vol (43 f.) ; 29 cm.
Langues : Anglais (eng)
Mots-clés : Linear programming
Interior point method
Descent direction
Algorithmic complexityRésumé : In this manuscript, we are interested in solving a linear programming
problem using a primal-dual interior point method. Inspired by the work
of Zhang and Xu (2011), we propose a new descent direction through a
modified transformation of the complementarity condition in the
system that defines the central path. A comprehensive theoretical and
numerical study has been carried out to achieve our objective.
Note de contenu : Contents
Glossary of abbreviations and notations ii
Introduction iii
1 Concepts of convex analysis and optimization 1
1.1 Convex analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Convex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Characterization of differentiable convex function . . . . . . . . . 2
1.2 Mathematical programming . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Classification of mathematical program . . . . . . . . . . . . . . . 4
1.2.3 Constraints qualification . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 Optimality conditions . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Linear programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Dual of the primal problem . . . . . . . . . . . . . . . . . . . . . . 6
1.3.3 Duality in linear programming . . . . . . . . . . . . . . . . . . . . 7
2 Interior point algorithm based on Zhang and Xu’s technique 8
2.1 Position of linear programming . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 The classical central path method . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Descent direction based on Zhang and Xu’s technique . . . . . . . . . . . 10
2.4 Generic primal-dual IPA for LP . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5 Convergence and complexity analysis . . . . . . . . . . . . . . . . . . . . 12
3 New descent direction for linear programming 14
3.1 Interior point algorithm for LP . . . . . . . . . . . . . . . . . . . . . . . . 14
3.1.1 Generic primal-dual IPA for LP . . . . . . . . . . . . . . . . . . . . 16
3.2 Convergence and complexity analysis . . . . . . . . . . . . . . . . . . . . 16
3.3 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.1 Fixed-size examples . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.2 Variable-size example . . . . . . . . . . . . . . . . . . . . . . . . . 37
Conclusion 42
Bibliography 43Côte titre : MAM/0848 En ligne : https://repository.univ-setif.dz/server/api/core/bitstreams/91a357e0-32d7-490c-a [...] Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0848 MAM/0848 Mémoire Bibliothèque des sciences Anglais Disponible
Disponible
