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 vector
Index. 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 algorithm
Note 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 36
Cô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 vector
Index. 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 algorithm
Note 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 36
Côte titre :	MAM/0772