University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Sarra Rebiga |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Interior-Point Method For Weighted Quadratic Programming Type de document : texte imprimé Auteurs : Rahima Abiza, Auteur ; Sarra Rebiga, Auteur ; Louiza Derbal, Directeur de thèse Editeur : Sétif:UFA1 Année de publication : 2025 Importance : 1 vol (38 f.) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Quadratic programming
Interior-point methods
Full-Newton
step
Weight vectorIndex. décimale : 510-Mathématique Résumé : In this study, we present a new algorithm based on the feasible interior-point
method of the primal-dual type, which relies on the weighted central path and
the full Newton step, for solving convex quadratic programming problems. By
applying an algebraic equivalent transformation to the weighted central path
equation, we obtained new Newton directions. To prove that the proposed
algorithm achieves an optimal complexity bound, we established sufficient and
appropriate conditions to guarantee this result. Finally, we presented numerical
results that confirm the effectiveness and efficiency of the developed algorithmNote de contenu : Contents
Introduction iii
1 Fundamental notions of convex analysis and quadratic program-
ming 2
1.1 Notions of convexity . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 A¢ ne sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Convex functions . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.4 Characterization of a di¤erentiable convex function . . . . 4
1.1.5 Asymptotic notations . . . . . . . . . . . . . . . . . . . . . 5
1.1.6 Speed of convergence . . . . . . . . . . . . . . . . . . . . . 5
1.2 Mathematical programming . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 ClassiÂ…cation of a mathematical problem . . . . . . . . . . 7
1.2.2 Existence and uniqueness of an optimal solution . . . . . . 7
1.2.3 Constraints qualiÂ…cation . . . . . . . . . . . . . . . . . . . 7
1.2.4 Optimality conditions . . . . . . . . . . . . . . . . . . . . 8
1.2.5 Lagrangian duality . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Convex quadratic programming . . . . . . . . . . . . . . . . . . . 9
1.3.1 Primal convex quadratic problem . . . . . . . . . . . . . . 10
1.3.2 Dual convex quadratic problem . . . . . . . . . . . . . . . 10
1.3.3 Existence and uniqueness of a solution . . . . . . . . . . . 11
1.3.4 Optimality conditions . . . . . . . . . . . . . . . . . . . . 11
1.3.5 Properties of duality . . . . . . . . . . . . . . . . . . . . . 11
1.3.6 Methods for solving a CQP . . . . . . . . . . . . . . . . . 12
1.4 NewtonÂ’s method for solving nonlinear systems . . . . . . . . . . 13
2 A weighted central path method for CQP 14
2.1 Method description . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Weighted direction . . . . . . . . . . . . . . . . . . . . . . 15
2.2 The proximity measure . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Generic Weighted Interior-Point Algorithm . . . . . . . . . . . . . 17
2.4 Analysis of the algorithm . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 Iteration bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 Numerical results 26
3.1 Examples with Â…xed size . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Example with variable size . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Ameliorated of algorithm . . . . . . . . . . . . . . . . . . . . . . . 32
Conclusion 35
References 36Côte titre : MAM/0772 Interior-Point Method For Weighted Quadratic Programming [texte imprimé] / Rahima Abiza, Auteur ; Sarra Rebiga, Auteur ; Louiza Derbal, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2025 . - 1 vol (38 f.) ; 29 cm.
Langues : Anglais (eng)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Quadratic programming
Interior-point methods
Full-Newton
step
Weight vectorIndex. décimale : 510-Mathématique Résumé : In this study, we present a new algorithm based on the feasible interior-point
method of the primal-dual type, which relies on the weighted central path and
the full Newton step, for solving convex quadratic programming problems. By
applying an algebraic equivalent transformation to the weighted central path
equation, we obtained new Newton directions. To prove that the proposed
algorithm achieves an optimal complexity bound, we established sufficient and
appropriate conditions to guarantee this result. Finally, we presented numerical
results that confirm the effectiveness and efficiency of the developed algorithmNote de contenu : Contents
Introduction iii
1 Fundamental notions of convex analysis and quadratic program-
ming 2
1.1 Notions of convexity . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 A¢ ne sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Convex functions . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.4 Characterization of a di¤erentiable convex function . . . . 4
1.1.5 Asymptotic notations . . . . . . . . . . . . . . . . . . . . . 5
1.1.6 Speed of convergence . . . . . . . . . . . . . . . . . . . . . 5
1.2 Mathematical programming . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 ClassiÂ…cation of a mathematical problem . . . . . . . . . . 7
1.2.2 Existence and uniqueness of an optimal solution . . . . . . 7
1.2.3 Constraints qualiÂ…cation . . . . . . . . . . . . . . . . . . . 7
1.2.4 Optimality conditions . . . . . . . . . . . . . . . . . . . . 8
1.2.5 Lagrangian duality . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Convex quadratic programming . . . . . . . . . . . . . . . . . . . 9
1.3.1 Primal convex quadratic problem . . . . . . . . . . . . . . 10
1.3.2 Dual convex quadratic problem . . . . . . . . . . . . . . . 10
1.3.3 Existence and uniqueness of a solution . . . . . . . . . . . 11
1.3.4 Optimality conditions . . . . . . . . . . . . . . . . . . . . 11
1.3.5 Properties of duality . . . . . . . . . . . . . . . . . . . . . 11
1.3.6 Methods for solving a CQP . . . . . . . . . . . . . . . . . 12
1.4 NewtonÂ’s method for solving nonlinear systems . . . . . . . . . . 13
2 A weighted central path method for CQP 14
2.1 Method description . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Weighted direction . . . . . . . . . . . . . . . . . . . . . . 15
2.2 The proximity measure . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Generic Weighted Interior-Point Algorithm . . . . . . . . . . . . . 17
2.4 Analysis of the algorithm . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 Iteration bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 Numerical results 26
3.1 Examples with Â…xed size . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Example with variable size . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Ameliorated of algorithm . . . . . . . . . . . . . . . . . . . . . . . 32
Conclusion 35
References 36Côte titre : MAM/0772 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0772 MAM/0772 Mémoire Bibliothèque des sciences Anglais Disponible
Disponible
