| Titre : | STUDY OF INTERIOR-POINT METHOD FOR MONOTONE SEMIDEFINITE LINEAR COMPLEMENTARITY PROBLEMS |
| Auteurs : | SOUHEILA LAIDI, Auteur ; Nadjette Bouziane, Directeur de thèse |
| Type de document : | Mémoire magistere |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2025 |
| Format : | 1 vol. (77 p.) / ill.couv.ill.encoul / 30cm |
| Langues: | Français |
| Langues originales: | Français |
| Résumé : |
Cette thèse étudie les méthodes de points intérieurs pour résoudre les problèmes de complémentarité linéaire semi-définis monotones (SDLCP). Elle présente les fondements théoriques de l'analyse convexe, de l'optimisation matricielle et de la théorie de la complémentarité, en se concentrant sur les algorithmes primaux-duaux basés sur des fonctions noyau. L'étude analyse le chemin central, les directions de Nesterov- Todd et l'impact de diverses fonctions noyau sur la complexité algorithmique. Les applications en optimisation, théorie du contrôle et problèmes aux valeurs propres sont discutées. Le travail fournit des bornes de complexité pour les méthodes à grands et petits pas, démontrant leur convergence en temps polynomial. Les résultats clés incluent des théorèmes d'équivalence entre SDLCP et problèmes connexes, ainsi que des techniques de décomposition spectrale pour matrices symétrique |
| Sommaire : |
Dedication i Acknowledgment ii Notations and symbols iv Introduction 1 1 General Notions 4 1.1 Some Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Gradient and Hessian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Notion of Partial Derivative . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Hessian Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Convex Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.1 Convex Sets and Functions . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Taylor Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 General Optimization Problem . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5.1 Necessary Conditions for a Minimum . . . . . . . . . . . . . . . . . . 10 1.5.2 Extremum Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5.3 Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.6 Mathematical Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Dedication i Acknowledgment ii Notations and symbols iv Introduction 1 1 General Notions 4 1.1 Some Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Gradient and Hessian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Notion of Partial Derivative . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Hessian Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Convex Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3.1 Convex Sets and Functions . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Taylor Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 General Optimization Problem . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5.1 Necessary Conditions for a Minimum . . . . . . . . . . . . . . . . . . 10 1.5.2 Extremum Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5.3 Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.6 Mathematical Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3.2 Stein transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.4 Primal-dual central path . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4.1 Logarithmic barrier function . . . . . . . . . . . . . . . . . . . . . . 50 3.4.2 Classical search direction . . . . . . . . . . . . . . . . . . . . . . . . 52 3.5 Nesterov-Todd direction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.6 The generic primal-dual Interior point algorithm . . . . . . . . . . . . . . . 55 3.7 Kernel function and its qualification . . . . . . . . . . . . . . . . . . . . . . 56 3.8 Spectral decomposition for symmetric matrices . . . . . . . . . . . . . . . . 58 3.9 The search directions determined by kernel functions . . . . . . . . . . . . . 60 3.10 The Generic Primal–Dual IPM for SDLCP . . . . . . . . . . . . . . . . . . 61 Bibliography 62 |
| Type de document : | Mémoire master |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| MM/1362 | Mémoire master | bibliothèque sciences exactes | Consultable |
