University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Ghanem,AÑ—cha |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Les méthodes d'optimisation globale pour les problèmes quadratiques non convexes. Type de document : texte imprimé Auteurs : Ghanem,Aїcha, Auteur ; Ghanem,Abderrazak, Directeur de thèse Editeur : Setif:UFA Année de publication : 2019 Importance : 1 vol (50 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Optimisation globale
problèmes quadratiques non convexes
Modèle de réseau neurones
points d'équilibre
Convergence globaleIndex. décimale : 510 Mathématique Résumé : Dans ce mémoire on s'intéresse aux méthodes d’optimisation globale pour les problèmes quadratiques non convexe. Nous avons présenté le problème quadratique (QP) non convexe. Grâce à une technique neurodynamique plus particulièrement le modèle de réseau neurones récurrents (RNN) pour la résolution des (QP) non convexes. Il est prouvé que les points d'équilibre du modèle de réseau neurones coïncident avec les solutions optimales. De plus, ce modèle est stable au sens de Lyapunov à chaque point d’équilibre. Les résultats numériques ont montré la supériorité de (RNN) pour fournir rapidement une solution optimale, tout en réserve la convergence globale de la méthode. Note de contenu : Sommaire
INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
I RAPPELS DE BASE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1 Analyse matricielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 La programmation quadratique . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 La programmation quadratique sans contraintes . . . . . . . . . 8
1.3.2 La programmation quadratique avec contraintes . . . . . . . . . 10
1.3.3 Notion de convexité pour les programmes quadratiques . . . . . 12
II LA PROGRAMMATION QUADRATIQUE NON CONVEXE . . 14
2.1 Formulation des problèmes quadratiques . . . . . . . . . . . . . . . . . 14
2.2 Di¢ cultés de résolution d’un problème quadratique non convexe . . . . 15
2.3 Exemples des problèmes quadratiques non convexes . . . . . . . . . . . 17
2.3.1 Les problèmes des moindres carrés booléennes . . . . . . . . . . 17
2.3.2 Le problème de cardinalité minimale . . . . . . . . . . . . . . . 17
2.3.3 Le problème de partitionnement . . . . . . . . . . . . . . . . . . 18
2.3.4 Le problème du coupe maximale . . . . . . . . . . . . . . . . . . 19
2.3.5 Problèmes polynomiaux . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Reformulation convexe pour les problèmes quadratiques non convexes . 21
2.4.1 Relaxation en programme semi-dé…nie positive (RSDP) . . . . . 21
2.4.2 Relaxation programme quadratique en variables bivalentes (BQP) 23
TABLE DES MATIÈRES
2.4.3 Relaxation en programme linéaire en nombres entiers (IQP) . . 24
2.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.1 Relaxation du problème des moindres carrés booléenne . . . . . 26
2.5.2 Relaxation du Problème de partitionnement et coupe maximale 27
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
III LA TECHNIQUE NEURODYNAMIQUE DÂ’OPTIMISATION POUR
LA RÉSOLUTION D’UN PROBLÈME QUADRATIQUE NON CONVEXE 28
3.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Conditions d’optimalité globale . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 Condition su¢ sante d’optimalité globale . . . . . . . . . . . . . 30
3.3 Le modèle de réseau neurones . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.1 Analyse de stabilité et de convergence . . . . . . . . . . . . . . 33
3.3.2 Algorithme basée sur la sous-estimation et surestimation de la
fonction objective . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Implémentations numériques . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49Côte titre : MAM/0309 En ligne : https://drive.google.com/file/d/1LFzcEHnSPC5R2k_LkUoTD4REgX6agjg4/view?usp=shari [...] Format de la ressource électronique : Les méthodes d'optimisation globale pour les problèmes quadratiques non convexes. [texte imprimé] / Ghanem,AÑ—cha, Auteur ; Ghanem,Abderrazak, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (50 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Optimisation globale
problèmes quadratiques non convexes
Modèle de réseau neurones
points d'équilibre
Convergence globaleIndex. décimale : 510 Mathématique Résumé : Dans ce mémoire on s'intéresse aux méthodes d’optimisation globale pour les problèmes quadratiques non convexe. Nous avons présenté le problème quadratique (QP) non convexe. Grâce à une technique neurodynamique plus particulièrement le modèle de réseau neurones récurrents (RNN) pour la résolution des (QP) non convexes. Il est prouvé que les points d'équilibre du modèle de réseau neurones coïncident avec les solutions optimales. De plus, ce modèle est stable au sens de Lyapunov à chaque point d’équilibre. Les résultats numériques ont montré la supériorité de (RNN) pour fournir rapidement une solution optimale, tout en réserve la convergence globale de la méthode. Note de contenu : Sommaire
INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
I RAPPELS DE BASE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1 Analyse matricielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Analyse convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 La programmation quadratique . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 La programmation quadratique sans contraintes . . . . . . . . . 8
1.3.2 La programmation quadratique avec contraintes . . . . . . . . . 10
1.3.3 Notion de convexité pour les programmes quadratiques . . . . . 12
II LA PROGRAMMATION QUADRATIQUE NON CONVEXE . . 14
2.1 Formulation des problèmes quadratiques . . . . . . . . . . . . . . . . . 14
2.2 Di¢ cultés de résolution d’un problème quadratique non convexe . . . . 15
2.3 Exemples des problèmes quadratiques non convexes . . . . . . . . . . . 17
2.3.1 Les problèmes des moindres carrés booléennes . . . . . . . . . . 17
2.3.2 Le problème de cardinalité minimale . . . . . . . . . . . . . . . 17
2.3.3 Le problème de partitionnement . . . . . . . . . . . . . . . . . . 18
2.3.4 Le problème du coupe maximale . . . . . . . . . . . . . . . . . . 19
2.3.5 Problèmes polynomiaux . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Reformulation convexe pour les problèmes quadratiques non convexes . 21
2.4.1 Relaxation en programme semi-dé…nie positive (RSDP) . . . . . 21
2.4.2 Relaxation programme quadratique en variables bivalentes (BQP) 23
TABLE DES MATIÈRES
2.4.3 Relaxation en programme linéaire en nombres entiers (IQP) . . 24
2.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5.1 Relaxation du problème des moindres carrés booléenne . . . . . 26
2.5.2 Relaxation du Problème de partitionnement et coupe maximale 27
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
III LA TECHNIQUE NEURODYNAMIQUE DÂ’OPTIMISATION POUR
LA RÉSOLUTION D’UN PROBLÈME QUADRATIQUE NON CONVEXE 28
3.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Conditions d’optimalité globale . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 Condition su¢ sante d’optimalité globale . . . . . . . . . . . . . 30
3.3 Le modèle de réseau neurones . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.1 Analyse de stabilité et de convergence . . . . . . . . . . . . . . 33
3.3.2 Algorithme basée sur la sous-estimation et surestimation de la
fonction objective . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Implémentations numériques . . . . . . . . . . . . . . . . . . . . . . . . 38
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Conclusion générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49Côte titre : MAM/0309 En ligne : https://drive.google.com/file/d/1LFzcEHnSPC5R2k_LkUoTD4REgX6agjg4/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0309 MAM/0309 Mémoire Bibliothéque des sciences Français Disponible
Disponible