Development Of A Corrector-Predictor Algorithm For Convex Quadratic Optimization / Mohamed Benguellil  

Public ISBD Titre : Development Of A Corrector-Predictor Algorithm For Convex Quadratic Optimization Type de document : document électronique Auteurs : Mohamed Benguellil, Auteur ; Loukmene Selama, Auteur ; Billel Zaoui, Directeur de thèse Editeur : Sétif:UFS Année de publication : 2025 Importance : 1 vol (46 f.) Format : 29 cm Langues : Anglais (eng) Mots-clés : Convex quadratic optimization Interior-point methods Corrector-predictor algorithm Algebraic equivalent transformation Search direction Résumé : This manuscript introduces a new corrector-predictor interior-point algorithm for solving convex quadratic optimization problems. Inspired by the algebraic equivalent transformation technique, we define a modified transformed central path utilizing the specific function φ(t) = t - √t. This approach allows us to derive efficient Newton-type search directions for both the predictor and corrector steps. To demonstrate the practical efficiency and robustness of our proposed algorithm, a comprehensive numerical comparison is conducted against the standard primal-dual interior-point method and the recent weighted primal-dual interior-point algorithm (2024). The numerical results validate the computational superior performance of the proposed method. Note de contenu : Contents Glossary of abbreviations 1 Glossary of notations 2 Introduction 3 1 Fundamental notions 6 1.1 Convex analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Inner product and norm . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Elements of convex analysis . . . . . . . . . . . . . . . . . . . . . 7 1.1.3 Convex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.4 Characterization of a differentiable convex function . . . . . . . . 9 1.1.5 Newton’s method for a non-linear system . . . . . . . . . . . . . . 10 1.2 Mathematical programming . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Problem definition and classification . . . . . . . . . . . . . . . . . 11 1.2.2 Existence and uniqueness results . . . . . . . . . . . . . . . . . . . 12 1.2.3 Constraint qualification . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Convex quadratic programming . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 Primal convex quadratic problem . . . . . . . . . . . . . . . . . . . 13 1.3.2 Dual convex quadratic problem . . . . . . . . . . . . . . . . . . . . 14 1.3.3 Duality in quadratic programming . . . . . . . . . . . . . . . . . . 14 1.3.4 Resolution methods . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 Recent primal-dual algorithms for CQO 17 2.1 Primal-dual convex quadratic optimization . . . . . . . . . . . . . . . . . 17 2.2 Classical central path method . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Central path method using the Algebraic Equivalent Transformation . . 19 2.4 The algorithm prototype . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 An efficient corrector predictor interior-point algorithm for CQO 24 3.1 Corrector-predictor algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.1 Algorithm description . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Algorithm analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.1 The corrector step . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2.2 The predictor step . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2.3 Complexity analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4 Numerical tests 36 4.1 Examples with fixed size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Examples with variable size . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2.1 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 Algorithm Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3.1 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Conclusion 44 Bibliography 46 Côte titre : MAM/0847 En ligne : https://repository.univ-setif.dz/server/api/core/bitstreams/d779cea3-b80d-4069-b [...] Development Of A Corrector-Predictor Algorithm For Convex Quadratic Optimization [document électronique] / Mohamed Benguellil, Auteur ; Loukmene Selama, Auteur ; Billel Zaoui, Directeur de thèse . - [S.l.] : Sétif:UFS, 2025 . - 1 vol (46 f.) ; 29 cm. Langues : Anglais (eng) Mots-clés : Convex quadratic optimization Interior-point methods Corrector-predictor algorithm Algebraic equivalent transformation Search direction Résumé : This manuscript introduces a new corrector-predictor interior-point algorithm for solving convex quadratic optimization problems. Inspired by the algebraic equivalent transformation technique, we define a modified transformed central path utilizing the specific function φ(t) = t - √t. This approach allows us to derive efficient Newton-type search directions for both the predictor and corrector steps. To demonstrate the practical efficiency and robustness of our proposed algorithm, a comprehensive numerical comparison is conducted against the standard primal-dual interior-point method and the recent weighted primal-dual interior-point algorithm (2024). The numerical results validate the computational superior performance of the proposed method. Note de contenu : Contents Glossary of abbreviations 1 Glossary of notations 2 Introduction 3 1 Fundamental notions 6 1.1 Convex analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Inner product and norm . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Elements of convex analysis . . . . . . . . . . . . . . . . . . . . . 7 1.1.3 Convex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.4 Characterization of a differentiable convex function . . . . . . . . 9 1.1.5 Newton’s method for a non-linear system . . . . . . . . . . . . . . 10 1.2 Mathematical programming . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Problem definition and classification . . . . . . . . . . . . . . . . . 11 1.2.2 Existence and uniqueness results . . . . . . . . . . . . . . . . . . . 12 1.2.3 Constraint qualification . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Convex quadratic programming . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1 Primal convex quadratic problem . . . . . . . . . . . . . . . . . . . 13 1.3.2 Dual convex quadratic problem . . . . . . . . . . . . . . . . . . . . 14 1.3.3 Duality in quadratic programming . . . . . . . . . . . . . . . . . . 14 1.3.4 Resolution methods . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 Recent primal-dual algorithms for CQO 17 2.1 Primal-dual convex quadratic optimization . . . . . . . . . . . . . . . . . 17 2.2 Classical central path method . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Central path method using the Algebraic Equivalent Transformation . . 19 2.4 The algorithm prototype . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 An efficient corrector predictor interior-point algorithm for CQO 24 3.1 Corrector-predictor algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.1 Algorithm description . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Algorithm analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.1 The corrector step . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2.2 The predictor step . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2.3 Complexity analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4 Numerical tests 36 4.1 Examples with fixed size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2 Examples with variable size . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2.1 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 Algorithm Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.3.1 Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Conclusion 44 Bibliography 46 Côte titre : MAM/0847 En ligne : https://repository.univ-setif.dz/server/api/core/bitstreams/d779cea3-b80d-4069-b [...]

Exemplaires (1)

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

---

1 (1 - 1 / 1)