|
| Titre : |
Interior-point methos of primal-dual central-path type for solving some classes of liear complementarity problems over symmetric coes |
| Type de document : |
texte imprimé |
| Auteurs : |
Tabchouche,Nesrine, Auteur ; Achache, M, Directeur de thèse |
| Editeur : |
Setif:UFA |
| Année de publication : |
2019 |
| Importance : |
1 vol (86 f.) |
| Format : |
29 cm |
| Langues : |
Anglais (eng) |
| Catégories : |
Thèses & Mémoires:Mathématique
|
| Mots-clés : |
Problèmes de complémentarité linéaire semi-finie
Complémentarité linéaire horizontale
des problèmes
Méthodes de point intérieur
Fonction du noyau |
| Index. décimale : |
510 Mathématique |
| Résumé : |
Résumé
Depuis les années 1950, la théorie de la programmation mathématique et la théorie des jeux ont été
développé rapidement et largement. La littérature montre la riche théorie de la programmation linéaire,
programmation quadratique convexe et jeu bimatrice, qui sont fondamentaux
sujets dans ces domaines. En tant que cadre unificateur de tels problèmes, la complémentarité linéaire
problème a été introduit dans la programmation mathématique au milieu des années 1960.
Le problème de la complémentarité linéaire est de trouver, pour une matrice carrée et un vecteur, un vecteur
satisfaisant les constituants linéaires et les conditions de complémentarité.
Cette thèse concerne l'analyse, la mise en œuvre de méthodes de points intérieurs. Dans
En particulier, nous nous concentrons sur deux types de problèmes: les problèmes de complémentarité linéaire horizontale
(HLCP) et problèmes de complémentarité linéaire semi-définie (SDLCP).
Au chapitre 1, nous présentons les définitions et les termes qui seront utilisés tout au long de la thèse.
Au chapitre 2: nous présentons un algorithme de points intérieurs par étapes réalisable de Newton complet pour résoudre
problèmes de complémentarité linéaire horizontale monotone. L’idée de cet algorithme est de
suivez les centres du HLCP perturbé en n'utilisant que des étapes full-Newton avec l'avantage
qu'aucune recherche de ligne n'est requise et limite les itérations dans un petit quartier de
le trajet central en introduisant une mesure proximale appropriée pendant le processus de résolution.
Ensuite, nous prouvons un nouveau choix approprié des valeurs par défaut du seuil de la
paramètre? qui définit la taille du voisinage du chemin central et du
mettre à jour le paramètre barrière? que notre algorithme est bien défini et l'étape complète de Newton pour
le chemin central est localement convergent quadratiquement. De plus, nous tirons sa complexité
lié. qui coïncide avec la meilleure itération connue à destination de tels IPM réalisables. Enfin,
nous rapportons quelques résultats numériques pour montrer la capacité de cette approche.
Au chapitre 3: nous traitons de l’analyse de complexité et de la mise en oeuvre numérique
des méthodes primales-doubles du point intérieur pour la complémentarité linéaire semi-définie monotone
problèmes basés sur une nouvelle fonction du noyau paramétrique. La fonction du noyau proposée est soit
une fonction auto-régulière et ni la fonction de barrière logarithmique habituelle. Au moyen de la fonctionnalité
de la fonction du noyau, nous étudions l’analyse de complexité des IPM à double primal et en déduisons
l'itération la mieux connue actuellement pour l'algorithme de mise à jour volumineuse. Enfin, nous rapportons
quelques résultats numériques pour montrer la performance pratique de l'algorithme proposé
avec différents paramètres |
| Note de contenu : |
Sommaire
Convex Analysis and matrix theory 17
1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2 Matrix theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3 Tensor product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.1 Application to Sylvester and Lyapunov Equations . . . . . . . . . 22
1.4 Convex sets and functions . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1 Convex optimization . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 Convex Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.3 Examples of symmetric and nonsymmetric cones . . . . . . . . . 26
1.5 Newton-Raphson’s method for nonlinear systems . . . . . . . . . . . . . 26
1.5.1 Newton-Raphson’s Method . . . . . . . . . . . . . . . . . . . . 27
1.6 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.6.1 Linear Complementarity Problem . . . . . . . . . . . . . . . . . 28
1.6.2 Classes of LCP . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.6.3 Horizontal Linear Complementarity Problems . . . . . . . . . . . 30
1.6.4 Classes of HLCP . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.6.5 Semidefinite Linear Complementarity Problem . . . . . . . . . . 32
1.6.6 Classes of SDLCP . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.6.7 Some results of the existence and uniqueness of solution of monotone SDLCP . . . . . . . 33
2 A full-Newton step IP algorithm for HLCP 35
2.1 Central-path for HLCP . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.1.1 Search directions for HLCP . . . . . . . . . . . . . . . . . . . . 37
2.1.2 Algorithm for HLCP . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2 Complexity analysis of the algorithm . . . . . . . . . . . . . . . . . . . . 39
2.2.1 Feasibility and locally quadratically convergence of the feasible
full-Newton step . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.2 Updating the barrier parameter . . . . . . . . . . . . . . . . . . . 42
2.2.3 Iteration bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3 IP Methods for SDLCP based on a new kernel function 53
3.1 Some results on matrices and matrix functions . . . . . . . . . . . . . . 54
3.2 The central-path for SDLCP . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2.1 The search directions determined by kernel functions . . . . . . . 56
3.3 The generic primal-dual IPM for SDLCP . . . . . . . . . . . . . . . . . 59
3.4 Properties of the Kernel (barrier) function . . . . . . . . . . . . . . . . . 59
3.5 Analysis of the interior-point algorithm . . . . . . . . . . . . . . . . . . 62
3.5.1 Decrease of the barrier function and choice of the default step-size 63
3.5.2 Iteration bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.6 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
General conclusion and future work 77
Bibliography 80
|
| Côte titre : |
DM/0143 |
| En ligne : |
https://drive.google.com/file/d/1odC7FMfewlcBRrXzfq6-Zq2Ia7oPK2bd/view?usp=shari [...] |
| Format de la ressource électronique : |
pdf |
Interior-point methos of primal-dual central-path type for solving some classes of liear complementarity problems over symmetric coes [texte imprimé] / Tabchouche,Nesrine, Auteur ; Achache, M, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (86 f.) ; 29 cm. Langues : Anglais ( eng)
| Catégories : |
Thèses & Mémoires:Mathématique
|
| Mots-clés : |
Problèmes de complémentarité linéaire semi-finie
Complémentarité linéaire horizontale
des problèmes
Méthodes de point intérieur
Fonction du noyau |
| Index. décimale : |
510 Mathématique |
| Résumé : |
Résumé
Depuis les années 1950, la théorie de la programmation mathématique et la théorie des jeux ont été
développé rapidement et largement. La littérature montre la riche théorie de la programmation linéaire,
programmation quadratique convexe et jeu bimatrice, qui sont fondamentaux
sujets dans ces domaines. En tant que cadre unificateur de tels problèmes, la complémentarité linéaire
problème a été introduit dans la programmation mathématique au milieu des années 1960.
Le problème de la complémentarité linéaire est de trouver, pour une matrice carrée et un vecteur, un vecteur
satisfaisant les constituants linéaires et les conditions de complémentarité.
Cette thèse concerne l'analyse, la mise en œuvre de méthodes de points intérieurs. Dans
En particulier, nous nous concentrons sur deux types de problèmes: les problèmes de complémentarité linéaire horizontale
(HLCP) et problèmes de complémentarité linéaire semi-définie (SDLCP).
Au chapitre 1, nous présentons les définitions et les termes qui seront utilisés tout au long de la thèse.
Au chapitre 2: nous présentons un algorithme de points intérieurs par étapes réalisable de Newton complet pour résoudre
problèmes de complémentarité linéaire horizontale monotone. L’idée de cet algorithme est de
suivez les centres du HLCP perturbé en n'utilisant que des étapes full-Newton avec l'avantage
qu'aucune recherche de ligne n'est requise et limite les itérations dans un petit quartier de
le trajet central en introduisant une mesure proximale appropriée pendant le processus de résolution.
Ensuite, nous prouvons un nouveau choix approprié des valeurs par défaut du seuil de la
paramètre? qui définit la taille du voisinage du chemin central et du
mettre à jour le paramètre barrière? que notre algorithme est bien défini et l'étape complète de Newton pour
le chemin central est localement convergent quadratiquement. De plus, nous tirons sa complexité
lié. qui coïncide avec la meilleure itération connue à destination de tels IPM réalisables. Enfin,
nous rapportons quelques résultats numériques pour montrer la capacité de cette approche.
Au chapitre 3: nous traitons de l’analyse de complexité et de la mise en oeuvre numérique
des méthodes primales-doubles du point intérieur pour la complémentarité linéaire semi-définie monotone
problèmes basés sur une nouvelle fonction du noyau paramétrique. La fonction du noyau proposée est soit
une fonction auto-régulière et ni la fonction de barrière logarithmique habituelle. Au moyen de la fonctionnalité
de la fonction du noyau, nous étudions l’analyse de complexité des IPM à double primal et en déduisons
l'itération la mieux connue actuellement pour l'algorithme de mise à jour volumineuse. Enfin, nous rapportons
quelques résultats numériques pour montrer la performance pratique de l'algorithme proposé
avec différents paramètres |
| Note de contenu : |
Sommaire
Convex Analysis and matrix theory 17
1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2 Matrix theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3 Tensor product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.1 Application to Sylvester and Lyapunov Equations . . . . . . . . . 22
1.4 Convex sets and functions . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1 Convex optimization . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 Convex Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.3 Examples of symmetric and nonsymmetric cones . . . . . . . . . 26
1.5 Newton-Raphson’s method for nonlinear systems . . . . . . . . . . . . . 26
1.5.1 Newton-Raphson’s Method . . . . . . . . . . . . . . . . . . . . 27
1.6 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.6.1 Linear Complementarity Problem . . . . . . . . . . . . . . . . . 28
1.6.2 Classes of LCP . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.6.3 Horizontal Linear Complementarity Problems . . . . . . . . . . . 30
1.6.4 Classes of HLCP . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.6.5 Semidefinite Linear Complementarity Problem . . . . . . . . . . 32
1.6.6 Classes of SDLCP . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.6.7 Some results of the existence and uniqueness of solution of monotone SDLCP . . . . . . . 33
2 A full-Newton step IP algorithm for HLCP 35
2.1 Central-path for HLCP . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.1.1 Search directions for HLCP . . . . . . . . . . . . . . . . . . . . 37
2.1.2 Algorithm for HLCP . . . . . . . . . . . . . . . . . . . . . . . . 38
2.2 Complexity analysis of the algorithm . . . . . . . . . . . . . . . . . . . . 39
2.2.1 Feasibility and locally quadratically convergence of the feasible
full-Newton step . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.2.2 Updating the barrier parameter . . . . . . . . . . . . . . . . . . . 42
2.2.3 Iteration bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3 IP Methods for SDLCP based on a new kernel function 53
3.1 Some results on matrices and matrix functions . . . . . . . . . . . . . . 54
3.2 The central-path for SDLCP . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2.1 The search directions determined by kernel functions . . . . . . . 56
3.3 The generic primal-dual IPM for SDLCP . . . . . . . . . . . . . . . . . 59
3.4 Properties of the Kernel (barrier) function . . . . . . . . . . . . . . . . . 59
3.5 Analysis of the interior-point algorithm . . . . . . . . . . . . . . . . . . 62
3.5.1 Decrease of the barrier function and choice of the default step-size 63
3.5.2 Iteration bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.6 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
General conclusion and future work 77
Bibliography 80
|
| Côte titre : |
DM/0143 |
| En ligne : |
https://drive.google.com/file/d/1odC7FMfewlcBRrXzfq6-Zq2Ia7oPK2bd/view?usp=shari [...] |
| Format de la ressource électronique : |
pdf |
|
Ajouter le résultat dans votre panier Affiner la rechercheInterior-point methos of primal-dual central-path type for solving some classes of liear complementarity problems over symmetric coes / Tabchouche,Nesrine
