University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Achache, M |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Absolute value equations. Theoretical and Numerical study Type de document : texte imprimé Auteurs : Nassima Anane, Auteur ; Achache, M, Directeur de thèse Editeur : Setif:UFA Année de publication : 2021 Importance : 1 vol (56 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Mathématique Index. décimale : 510 Mathématique Côte titre : DM/0166 En ligne : http://dspace.univ-setif.dz:8888/jspui/bitstream/123456789/3899/1/E-th1982%20Ana [...] Format de la ressource électronique : Absolute value equations. Theoretical and Numerical study [texte imprimé] / Nassima Anane, Auteur ; Achache, M, Directeur de thèse . - [S.l.] : Setif:UFA, 2021 . - 1 vol (56 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Mathématique Index. décimale : 510 Mathématique Côte titre : DM/0166 En ligne : http://dspace.univ-setif.dz:8888/jspui/bitstream/123456789/3899/1/E-th1982%20Ana [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0166 DM/0166 Thèse Bibliothéque des sciences Anglais Disponible
DisponibleComplexité et implémentation numérique d’une méthode de points intérieurs pour la programmation convexe / Goutali, Moufida
Titre : Complexité et implémentation numérique d’une méthode de points intérieurs pour la programmation convexe Type de document : texte imprimé Auteurs : Goutali, Moufida, Auteur ; Achache, M, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (92 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation convexe acontraintes linéaires
Complexité des AgorithmesIndex. décimale : 510 Mathématique Résumé : Résumé
Dans cette thèse, on s’intéresse à l’étude théorique (notamment la complexité polynomi-
ale) et à l’implémentation numérique d’une méthode de points intérieurs de trajectoire
centrale de type primal-dual pour résoudre les problèmes de la programmation convexe Ã
contraintes linéaires (PCCL). Dans notre étude, nous proposons de nouveaux paramètres
qui décrivent le paramètre barrière et le seuil qui mesure la taille du voisinage de la
trajectoire centrale. À travers ces derniers, un algorithme primal-dual à pas court et
d’itération de Newton complet bien dé…ni est présenté et de plus sa complexité est cal-
culée. L’e¢ cacité numérique de cet algorithme est con…rmée par des tests numériques.
Note de contenu : Sommaire
Analyse convexe et programmation mathématique 14
1.1 Éléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.1 Dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.2 Ensemble a¢ ne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.3 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.4 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.5 Cônes Convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 Programmation Mathématique . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1 Solutions optimales locales et globales . . . . . . . . . . . . . . . 18
1.2.2 Classi…cation d’un programme mathématique . . . . . . . . . . . 19
1.2.3 QualiÂ…cation des contraintes . . . . . . . . . . . . . . . . . . . . . 19
1.2.4 Résolution d’un programme mathématique . . . . . . . . . . . . . 20
1.3 Programmation convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.1 Existence (unicité) d’une solution optimale . . . . . . . . . . . . . 22
1.3.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.3 Le dual dÂ’un programme convexe . . . . . . . . . . . . . . . . . . 23
1.4 Algorithme dÂ’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5 Méthode de Newton-Raphson pour un système non linéaire . . . . . . . . 27
1.6 Méthodes de résolution d’un programme mathématique . . . . . . . . . . 28
1.6.1 Méthodes de type gradient . . . . . . . . . . . . . . . . . . . . . . 28
1.6.2 Méthodes simpliciales . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . 29
2 Méthodes de points intérieurs de type de TC pour (PCCL) 32
2.1 Existence et unicité de la trajectoire centrale (suivi de chemin) pour PCCL 32
2.1.1 Le problème perturbé . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.2 Les conditions d’optimalité de (K.K.T) . . . . . . . . . . . . . . 34
2.1.3 Le chemin central est bien dé…ni . . . . . . . . . . . . . . . . . . . 36
2.1.4 Le Théorème principal de la trajectoire centrale . . . . . . . . . . 37
2.2 Principe des méthodes de trajectoire centrale . . . . . . . . . . . . . . . . 40
2.2.1 Concept de proximité ou de centralisation . . . . . . . . . . . . . 41
2.2.2 Mise à jour du paramètre barrière . . . . . . . . . . . . . . . . . 42
2.2.3 Itération de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.4 Pas de déplacement . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3 Algorithme générale primal-dual de suivi de trajectoire . . . . . . . . . . 44
3 Méthodes primal-dual pour (PCCL) 45
3.1 Directions de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.1 Description algorithmique . . . . . . . . . . . . . . . . . . . . . . 48
3.1.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Convergence de l’algorithme et analyse de la complexité . . . . . . . . . . 49
3.2.1 Résultats préliminaires . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.2 Analyse de la faisabilité . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.3 Analyse de la complexité . . . . . . . . . . . . . . . . . . . . . . . 56
4 Simulation numérique 58
4.1 Mise en Âœuvre de cet algorithme . . . . . . . . . . . . . . . . . . . . . . 58
4.1.1 Paramètre barrière . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.1.2 Directions de déplacement . . . . . . . . . . . . . . . . . . . . . . 59
4.1.3 Point dÂ’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.1 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.2 Programmation quadratique . . . . . . . . . . . . . . . . . . . . . 66
4.2.3 Cas dÂ’une fonction convexe . . . . . . . . . . . . . . . . . . . . . 72
4.2.4 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4 Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Côte titre : DM/0140 En ligne : https://drive.google.com/file/d/1N-LtJ9dgX_smqAuQLpOV4bz1Rg28767N/view?usp=shari [...] Format de la ressource électronique : Complexité et implémentation numérique d’une méthode de points intérieurs pour la programmation convexe [texte imprimé] / Goutali, Moufida, Auteur ; Achache, M, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (92 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation convexe acontraintes linéaires
Complexité des AgorithmesIndex. décimale : 510 Mathématique Résumé : Résumé
Dans cette thèse, on s’intéresse à l’étude théorique (notamment la complexité polynomi-
ale) et à l’implémentation numérique d’une méthode de points intérieurs de trajectoire
centrale de type primal-dual pour résoudre les problèmes de la programmation convexe Ã
contraintes linéaires (PCCL). Dans notre étude, nous proposons de nouveaux paramètres
qui décrivent le paramètre barrière et le seuil qui mesure la taille du voisinage de la
trajectoire centrale. À travers ces derniers, un algorithme primal-dual à pas court et
d’itération de Newton complet bien dé…ni est présenté et de plus sa complexité est cal-
culée. L’e¢ cacité numérique de cet algorithme est con…rmée par des tests numériques.
Note de contenu : Sommaire
Analyse convexe et programmation mathématique 14
1.1 Éléments d’analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.1 Dé…nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.1.2 Ensemble a¢ ne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.3 Ensemble convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.4 Fonction convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.1.5 Cônes Convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2 Programmation Mathématique . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1 Solutions optimales locales et globales . . . . . . . . . . . . . . . 18
1.2.2 Classi…cation d’un programme mathématique . . . . . . . . . . . 19
1.2.3 QualiÂ…cation des contraintes . . . . . . . . . . . . . . . . . . . . . 19
1.2.4 Résolution d’un programme mathématique . . . . . . . . . . . . . 20
1.3 Programmation convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.1 Existence (unicité) d’une solution optimale . . . . . . . . . . . . . 22
1.3.2 Conditions d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.3 Le dual dÂ’un programme convexe . . . . . . . . . . . . . . . . . . 23
1.4 Algorithme dÂ’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.5 Méthode de Newton-Raphson pour un système non linéaire . . . . . . . . 27
1.6 Méthodes de résolution d’un programme mathématique . . . . . . . . . . 28
1.6.1 Méthodes de type gradient . . . . . . . . . . . . . . . . . . . . . . 28
1.6.2 Méthodes simpliciales . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.6.3 Méthodes de points intérieurs . . . . . . . . . . . . . . . . . . . . 29
2 Méthodes de points intérieurs de type de TC pour (PCCL) 32
2.1 Existence et unicité de la trajectoire centrale (suivi de chemin) pour PCCL 32
2.1.1 Le problème perturbé . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.2 Les conditions d’optimalité de (K.K.T) . . . . . . . . . . . . . . 34
2.1.3 Le chemin central est bien dé…ni . . . . . . . . . . . . . . . . . . . 36
2.1.4 Le Théorème principal de la trajectoire centrale . . . . . . . . . . 37
2.2 Principe des méthodes de trajectoire centrale . . . . . . . . . . . . . . . . 40
2.2.1 Concept de proximité ou de centralisation . . . . . . . . . . . . . 41
2.2.2 Mise à jour du paramètre barrière . . . . . . . . . . . . . . . . . 42
2.2.3 Itération de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.4 Pas de déplacement . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3 Algorithme générale primal-dual de suivi de trajectoire . . . . . . . . . . 44
3 Méthodes primal-dual pour (PCCL) 45
3.1 Directions de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.1 Description algorithmique . . . . . . . . . . . . . . . . . . . . . . 48
3.1.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2 Convergence de l’algorithme et analyse de la complexité . . . . . . . . . . 49
3.2.1 Résultats préliminaires . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.2 Analyse de la faisabilité . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.3 Analyse de la complexité . . . . . . . . . . . . . . . . . . . . . . . 56
4 Simulation numérique 58
4.1 Mise en Âœuvre de cet algorithme . . . . . . . . . . . . . . . . . . . . . . 58
4.1.1 Paramètre barrière . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.1.2 Directions de déplacement . . . . . . . . . . . . . . . . . . . . . . 59
4.1.3 Point dÂ’initialisation . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.2 Résultats numériques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.1 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.2 Programmation quadratique . . . . . . . . . . . . . . . . . . . . . 66
4.2.3 Cas dÂ’une fonction convexe . . . . . . . . . . . . . . . . . . . . . 72
4.2.4 Commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.4 Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Côte titre : DM/0140 En ligne : https://drive.google.com/file/d/1N-LtJ9dgX_smqAuQLpOV4bz1Rg28767N/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0140 DM/0140 Thèse Bibliothéque des sciences Français Disponible
Disponible
Titre : Complexity analysis and numerical implementation of a full-Newton step interiorpoint method for nonlinear convex semidefinite optimization Type de document : texte imprimé Auteurs : Yasmina Bendaas, Auteur ; Kaouther Berghout, Auteur ; Achache, M, Directeur de thèse Année de publication : 2022 Importance : 1 vol (76 f.) Format : 29 cm Langues : Anglais (eng) Catégories : Mathématique Mots-clés : The semi definite convex nonlinear programming Index. décimale : 510-Mathématique Résumé :
In this dissertation, we present a theoretical and a numerical study of a path-following
interior-point method for solving the semi definite convex nonlinear programming
based On Nesterov-Tood Newton symmetrical directions. Under a suitable choice of
barrier and its updating parameters, we show that the algorithm with short step has
the best polynomial complexity. This study followed by numerical experience to show
the efficiency on some problems of SDCNLO.Côte titre : MAM/0592 En ligne : https://drive.google.com/file/d/1Hoc-ctLvz3UJUWjQ7PQmWubsNZE3QOW4/view?usp=share [...] Format de la ressource électronique : Complexity analysis and numerical implementation of a full-Newton step interiorpoint method for nonlinear convex semidefinite optimization [texte imprimé] / Yasmina Bendaas, Auteur ; Kaouther Berghout, Auteur ; Achache, M, Directeur de thèse . - 2022 . - 1 vol (76 f.) ; 29 cm.
Langues : Anglais (eng)
Catégories : Mathématique Mots-clés : The semi definite convex nonlinear programming Index. décimale : 510-Mathématique Résumé :
In this dissertation, we present a theoretical and a numerical study of a path-following
interior-point method for solving the semi definite convex nonlinear programming
based On Nesterov-Tood Newton symmetrical directions. Under a suitable choice of
barrier and its updating parameters, we show that the algorithm with short step has
the best polynomial complexity. This study followed by numerical experience to show
the efficiency on some problems of SDCNLO.Côte titre : MAM/0592 En ligne : https://drive.google.com/file/d/1Hoc-ctLvz3UJUWjQ7PQmWubsNZE3QOW4/view?usp=share [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0592 MAM/0592 Mémoire Bibliothéque des sciences Anglais Disponible
Disponible
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 noyauIndex. 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ètresNote 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 : 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 noyauIndex. 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ètresNote 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 : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0143 DM/0143 Thèse Bibliothéque des sciences Français Disponible
Disponible
Titre : M´ethodes de Newton g´en´eralis´ees `a multi-pas pour r´esoudre l’´equation en valeurs absolues Type de document : texte imprimé Auteurs : Bendemagh ,Khaoula, Auteur ; Achache, M, Directeur de thèse Editeur : Setif:UFA Année de publication : 2019 Importance : 1 vol (49 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Mathématique Index. décimale : 510 Mathématique Note de contenu : Sommaire
1 Pr´eliminaire 6
1.1 Calcul matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Diff´erentiabilit´e et sous-diff´erentiabilit´e . . . . . . . . . . . . . . . . . . 8
1.3 Diff´erentiels g´en´eralis´es . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Equation en valeurs absolues . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Quelques r´esultats d’existence et d’unicit´e de la solution de L’EVA 11
1.5 Probl`eme de compl´ementarit´e lin´eaire et ´equation en valeurs absolues . . 11
1.5.1 Reformulation de PCLS comme EVA . . . . . . . . . . . . . . 12
2 M´ethodes de Newton-Raphson et ses variantes pour r´esoudre les ´equations
non lin´eaires dans Rn 13
2.1 Ordre de convergence d’une suite . . . . . . . . . . . . . . . . . . . . . . 13
2.2 M´ethode de Newton-Raphson classique . . . . . . . . . . . . . . . . . . 14
2.3 M´ethode unidimensionnelle de Newton `a deux pas ( dite m´ethode de Traub) 15
2.4 M´ethode de Newton `a trois pas (M´ethode de Frozen) . . . . . . . . . . . 17
2.5 Syst`emes d’´equations non lin´eaires et m´ethode de Newton-Raphson . . . 18
3 M´ethode de Newton et de Traub g´en´eralis´ee pour l’EVA 20
3.1 M´ethode de Newton g´en´eralis´ee . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1 Description de la m´ethode de Newton g´en´eralis´ee pour l’EVA . . 20
3.1.2 Algorithme g´en´eralis´e de Newton . . . . . . . . . . . . . . . . . 22
3.1.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.4 R´esultats num´eriques . . . . . . . . . . . . . . . . . . . . . . . . 23
1
3.2 M´ethode de Traub pour l’EVA . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.1 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Algorithme de Traub . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.3 R´esultats num´eriques . . . . . . . . . . . . . . . . . . . . . . . . 31
4 M´ethode de Newton `a trois pas dite m´ethode de Frozen 33
4.1 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Algorithme de Frozen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 R´esultats num´eriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5 Etude comparative 40
Conclusion et perspectives 46
BibliographieCôte titre : MAM/0359 En ligne : https://drive.google.com/file/d/1iF3GJmp0F8oNMSj2gykPNsjH0dU_6Rjq/view?usp=shari [...] Format de la ressource électronique : M´ethodes de Newton g´en´eralis´ees `a multi-pas pour r´esoudre l’´equation en valeurs absolues [texte imprimé] / Bendemagh ,Khaoula, Auteur ; Achache, M, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (49 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Mathématique Index. décimale : 510 Mathématique Note de contenu : Sommaire
1 Pr´eliminaire 6
1.1 Calcul matriciel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Diff´erentiabilit´e et sous-diff´erentiabilit´e . . . . . . . . . . . . . . . . . . 8
1.3 Diff´erentiels g´en´eralis´es . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Equation en valeurs absolues . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Quelques r´esultats d’existence et d’unicit´e de la solution de L’EVA 11
1.5 Probl`eme de compl´ementarit´e lin´eaire et ´equation en valeurs absolues . . 11
1.5.1 Reformulation de PCLS comme EVA . . . . . . . . . . . . . . 12
2 M´ethodes de Newton-Raphson et ses variantes pour r´esoudre les ´equations
non lin´eaires dans Rn 13
2.1 Ordre de convergence d’une suite . . . . . . . . . . . . . . . . . . . . . . 13
2.2 M´ethode de Newton-Raphson classique . . . . . . . . . . . . . . . . . . 14
2.3 M´ethode unidimensionnelle de Newton `a deux pas ( dite m´ethode de Traub) 15
2.4 M´ethode de Newton `a trois pas (M´ethode de Frozen) . . . . . . . . . . . 17
2.5 Syst`emes d’´equations non lin´eaires et m´ethode de Newton-Raphson . . . 18
3 M´ethode de Newton et de Traub g´en´eralis´ee pour l’EVA 20
3.1 M´ethode de Newton g´en´eralis´ee . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1 Description de la m´ethode de Newton g´en´eralis´ee pour l’EVA . . 20
3.1.2 Algorithme g´en´eralis´e de Newton . . . . . . . . . . . . . . . . . 22
3.1.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.4 R´esultats num´eriques . . . . . . . . . . . . . . . . . . . . . . . . 23
1
3.2 M´ethode de Traub pour l’EVA . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.1 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Algorithme de Traub . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.3 R´esultats num´eriques . . . . . . . . . . . . . . . . . . . . . . . . 31
4 M´ethode de Newton `a trois pas dite m´ethode de Frozen 33
4.1 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2 Algorithme de Frozen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 R´esultats num´eriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5 Etude comparative 40
Conclusion et perspectives 46
BibliographieCôte titre : MAM/0359 En ligne : https://drive.google.com/file/d/1iF3GJmp0F8oNMSj2gykPNsjH0dU_6Rjq/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0359 MAM/0359 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Permalink
Permalink
Permalink
Permalink
