A Numerical Comparison of Two Methodes for Solving a Linear Optimization. / Fatima Arif

Public ISBD Titre : A Numerical Comparison of Two Methodes for Solving a Linear Optimization. Type de document : document électronique Auteurs : Fatima Arif, Auteur ; Amina Toulmit, Auteur ; Sekhri ,Hakima, Directeur de thèse Editeur : Sétif:UFS Année de publication : 2025 Importance : 1 vol (92 f.) Format : 29 cm Langues : Anglais (eng) Mots-clés : Linear Programming Interior Point Methods Logarithmic Barrier Method Minorant and Majorant Functions Résumé : Abstract: This work presents a numerical and algorithmic comparative study of the logarithmic barrier method for solving linear programming (LP) problems. The focus is placed on computing the search direction using Newton’s method and determining the step size through the use of minorant and majorant functions to minimize computational cost. The proposed approach is validated through numerical experiments that highlight the comparative performance of the resulting algorithm. Note de contenu : Contents I Introduction vii x III Chapter 1 xi IV Preliminary concepts xii 0.1 1.1 Convex Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . xiv 0.1.1 1.1.1 A¢ ne sets and applications . . . . . . . . . . . . . . . xiv 0.1.2 1.1.2 Convex sets . . . . . . . . . . . . . . . . . . . . . . . . xv 0.1.3 1.1.3 Convex cones . . . . . . . . . . . . . . . . . . . . . . . xvi 0.1.4 1.1.4 Convex functions . . . . . . . . . . . . . . . . . . . . . xviii 0.1.5 1.1.5 Semi-continuity . . . . . . . . . . . . . . . . . . . . . . xx V Chapter 2 xxi VI Linear programming xxii 0.2 2.1 Notion of mathematical programming . . . . . . . . . . . . . . xxiv 0.3 2.1.1 QualiÂ…cation of constraints . . . . . . . . . . . . . . . . . . . . xxvii 0.4 2.1.2 Optimality conditions . . . . . . . . . . . . . . . . . . . . . . . xxviii 0.4.1 First-order necessary condition . . . . . . . . . . . . . . . . xxviii 0.4.2 Second-order necessary condition . . . . . . . . . . . . . . . xxix 0.5 2.1.3 Main results of existence and uniqueness of (MP) . . . . . . . xxx 0.6 2.1.4 Lagrangiene Duality . . . . . . . . . . . . . . . . . . . . . . . xxxii 0.7 2.1.5 General theory of linear programming . . . . . . . . . . . . . . xxxiii 0.8 2.1.6 Usual forms of a linear programming . . . . . . . . . . . . . . xxxvii 0.8.1 Canonical form . . . . . . . . . . . . . . . . . . . . . . . . . xxxvii 0.8.2 Standard form . . . . . . . . . . . . . . . . . . . . . . . . . . xxxvii 0.8.3 Mixed form (general form) . . . . . . . . . . . . . . . . . . . xxxix 0.9 2.1.7 Duality in Linear Programming . . . . . . . . . . . . . . . . . xl 0.10 2.1.8 Fields of application of the linear programming . . . . . . . . xliii 0.11 2.2 Methods for solving Linear Programming . . . . . . . . . . . . . xliv 0.12 2.2.1 Simplex Method . . . . . . . . . . . . . . . . . . . . . . . . . . xliv 0.13 2.2.2 Gradient methods . . . . . . . . . . . . . . . . . . . . . . . . . xliv 0.13.1 Conjugate gradient methods . . . . . . . . . . . . . . . . . . xliv 0.13.2 Projected gradient . . . . . . . . . . . . . . . . . . . . . . . xlv 0.14 2.2.3 Interior points method . . . . . . . . . . . . . . . . . . . . . . xlvi 0.14.1 1. Potential Reduction method . . . . . . . . . . . . . . . . xlvi 0.14.2 2. Trajectory centering method . . . . . . . . . . . . . . . . xlviii 0.14.3 3. A¢ ne method . . . . . . . . . . . . . . . . . . . . . . . . xlviii 0.14.4 4. Barrier method . . . . . . . . . . . . . . . . . . . . . . . . xlviii VII Chapter 3 liii Line Search method and Logarithmic Penality method for linear pro- gramming liv 0.15 3.1 Line Search method . . . . . . . . . . . . . . . . . . . . . . . . . lv 0.15.1 3.1.1 Principle of Linear Search . . . . . . . . . . . . . . . . lv 0.15.2 3.1.2 Rate of decrease . . . . . . . . . . . . . . . . . . . . . . lvi 0.15.3 3.1.3 Objectives to achieve . . . . . . . . . . . . . . . . . . lvii 0.15.4 3.1.4 Types of Line Search . . . . . . . . . . . . . . . . . . lvii 0.15.5 3.1.5 Safety interval . . . . . . . . . . . . . . . . . . . . . . lviii 0.16 3.2 Wolfe Line Search . . . . . . . . . . . . . . . . . . . . . . . . . . lviii 0.16.1 3.2.1 Insertion interval . . . . . . . . . . . . . . . . . . . . . lix 0.16.2 3.2.2 Conditions of computing rk . . . . . . . . . . . . . . . lix 0.16.3 3.2.3 Shema Linear Resarch . . . . . . . . . . . . . . . . . . lix 0.16.4 3.2.4 Inexacte Line Search with Strong Wolfe Conditions . . lxi 0.16.5 3.2.5 WolfeÂ’s Algorithm . . . . . . . . . . . . . . . . . . . . lxii 0.16.6 3.2.6 WolfeÂ’s Conditions Relaxed . . . . . . . . . . . . . . . lxiii 0.16.7 3.2.7 Existence of WolfeÂ’s step . . . . . . . . . . . . . . . . . lxiv 0.17 3.3 Logarithmic Barrier Method . . . . . . . . . . . . . . . . . . . . lxv 0.17.1 3.3.1 Theoretical Aspect of the Problem (P) . . . . . . . . . lxvii 0.17.2 3.3.2 Numerical Aspect of the Problem (P) . . . . . . . . . lxix 0.18 3.3.3 Minorant Functions of  . . . . . . . . . . . . . . . . . . . . . lxxvi 0.19 3.3.4 Majorant fuction of  . . . . . . . . . . . . . . . . . . . . . . . lxxxix 0.20 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xci 0.21 3.4 Comparative numericaly study between line search method and approximative function . . . . . . . . . . . . . . . . . . . . . . . . . xcii 0.21.1 3.4.1 Numerical Tests . . . . . . . . . . . . . . . . . . . . . xcii 0.21.2 3.4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . xciii 0.21.3 3.4.3 Comments . . . . . . . . . . . . . . . . . . . . . . . xcv Conclusion xcvi Côte titre : MAM/0810 A Numerical Comparison of Two Methodes for Solving a Linear Optimization. [document électronique] / Fatima Arif, Auteur ; Amina Toulmit, Auteur ; Sekhri ,Hakima, Directeur de thèse . - [S.l.] : Sétif:UFS, 2025 . - 1 vol (92 f.) ; 29 cm. Langues : Anglais (eng) Mots-clés : Linear Programming Interior Point Methods Logarithmic Barrier Method Minorant and Majorant Functions Résumé : Abstract: This work presents a numerical and algorithmic comparative study of the logarithmic barrier method for solving linear programming (LP) problems. The focus is placed on computing the search direction using Newton’s method and determining the step size through the use of minorant and majorant functions to minimize computational cost. The proposed approach is validated through numerical experiments that highlight the comparative performance of the resulting algorithm. Note de contenu : Contents I Introduction vii x III Chapter 1 xi IV Preliminary concepts xii 0.1 1.1 Convex Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . xiv 0.1.1 1.1.1 A¢ ne sets and applications . . . . . . . . . . . . . . . xiv 0.1.2 1.1.2 Convex sets . . . . . . . . . . . . . . . . . . . . . . . . xv 0.1.3 1.1.3 Convex cones . . . . . . . . . . . . . . . . . . . . . . . xvi 0.1.4 1.1.4 Convex functions . . . . . . . . . . . . . . . . . . . . . xviii 0.1.5 1.1.5 Semi-continuity . . . . . . . . . . . . . . . . . . . . . . xx V Chapter 2 xxi VI Linear programming xxii 0.2 2.1 Notion of mathematical programming . . . . . . . . . . . . . . xxiv 0.3 2.1.1 QualiÂ…cation of constraints . . . . . . . . . . . . . . . . . . . . xxvii 0.4 2.1.2 Optimality conditions . . . . . . . . . . . . . . . . . . . . . . . xxviii 0.4.1 First-order necessary condition . . . . . . . . . . . . . . . . xxviii 0.4.2 Second-order necessary condition . . . . . . . . . . . . . . . xxix 0.5 2.1.3 Main results of existence and uniqueness of (MP) . . . . . . . xxx 0.6 2.1.4 Lagrangiene Duality . . . . . . . . . . . . . . . . . . . . . . . xxxii 0.7 2.1.5 General theory of linear programming . . . . . . . . . . . . . . xxxiii 0.8 2.1.6 Usual forms of a linear programming . . . . . . . . . . . . . . xxxvii 0.8.1 Canonical form . . . . . . . . . . . . . . . . . . . . . . . . . xxxvii 0.8.2 Standard form . . . . . . . . . . . . . . . . . . . . . . . . . . xxxvii 0.8.3 Mixed form (general form) . . . . . . . . . . . . . . . . . . . xxxix 0.9 2.1.7 Duality in Linear Programming . . . . . . . . . . . . . . . . . xl 0.10 2.1.8 Fields of application of the linear programming . . . . . . . . xliii 0.11 2.2 Methods for solving Linear Programming . . . . . . . . . . . . . xliv 0.12 2.2.1 Simplex Method . . . . . . . . . . . . . . . . . . . . . . . . . . xliv 0.13 2.2.2 Gradient methods . . . . . . . . . . . . . . . . . . . . . . . . . xliv 0.13.1 Conjugate gradient methods . . . . . . . . . . . . . . . . . . xliv 0.13.2 Projected gradient . . . . . . . . . . . . . . . . . . . . . . . xlv 0.14 2.2.3 Interior points method . . . . . . . . . . . . . . . . . . . . . . xlvi 0.14.1 1. Potential Reduction method . . . . . . . . . . . . . . . . xlvi 0.14.2 2. Trajectory centering method . . . . . . . . . . . . . . . . xlviii 0.14.3 3. A¢ ne method . . . . . . . . . . . . . . . . . . . . . . . . xlviii 0.14.4 4. Barrier method . . . . . . . . . . . . . . . . . . . . . . . . xlviii VII Chapter 3 liii Line Search method and Logarithmic Penality method for linear pro- gramming liv 0.15 3.1 Line Search method . . . . . . . . . . . . . . . . . . . . . . . . . lv 0.15.1 3.1.1 Principle of Linear Search . . . . . . . . . . . . . . . . lv 0.15.2 3.1.2 Rate of decrease . . . . . . . . . . . . . . . . . . . . . . lvi 0.15.3 3.1.3 Objectives to achieve . . . . . . . . . . . . . . . . . . lvii 0.15.4 3.1.4 Types of Line Search . . . . . . . . . . . . . . . . . . lvii 0.15.5 3.1.5 Safety interval . . . . . . . . . . . . . . . . . . . . . . lviii 0.16 3.2 Wolfe Line Search . . . . . . . . . . . . . . . . . . . . . . . . . . lviii 0.16.1 3.2.1 Insertion interval . . . . . . . . . . . . . . . . . . . . . lix 0.16.2 3.2.2 Conditions of computing rk . . . . . . . . . . . . . . . lix 0.16.3 3.2.3 Shema Linear Resarch . . . . . . . . . . . . . . . . . . lix 0.16.4 3.2.4 Inexacte Line Search with Strong Wolfe Conditions . . lxi 0.16.5 3.2.5 WolfeÂ’s Algorithm . . . . . . . . . . . . . . . . . . . . lxii 0.16.6 3.2.6 WolfeÂ’s Conditions Relaxed . . . . . . . . . . . . . . . lxiii 0.16.7 3.2.7 Existence of WolfeÂ’s step . . . . . . . . . . . . . . . . . lxiv 0.17 3.3 Logarithmic Barrier Method . . . . . . . . . . . . . . . . . . . . lxv 0.17.1 3.3.1 Theoretical Aspect of the Problem (P) . . . . . . . . . lxvii 0.17.2 3.3.2 Numerical Aspect of the Problem (P) . . . . . . . . . lxix 0.18 3.3.3 Minorant Functions of  . . . . . . . . . . . . . . . . . . . . . lxxvi 0.19 3.3.4 Majorant fuction of  . . . . . . . . . . . . . . . . . . . . . . . lxxxix 0.20 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xci 0.21 3.4 Comparative numericaly study between line search method and approximative function . . . . . . . . . . . . . . . . . . . . . . . . . xcii 0.21.1 3.4.1 Numerical Tests . . . . . . . . . . . . . . . . . . . . . xcii 0.21.2 3.4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . xciii 0.21.3 3.4.3 Comments . . . . . . . . . . . . . . . . . . . . . . . xcv Conclusion xcvi Côte titre : MAM/0810

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
MAM/0810	MAM/0810	Mémoire	Bibliothèque des sciences	Anglais	Disponible Disponible

---

1 (1 - 1 / 1)