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 complexity
Ré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 43
Cô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 complexity
Ré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 43
Côte titre :	MAM/0848
En ligne :	https://repository.univ-setif.dz/server/api/core/bitstreams/91a357e0-32d7-490c-a [...]