Mémoires de Fin d’Etudes
Etablissement
Université de Sétif 1 - Ferhat Abbas
Affiliation
Département de Mathématique
Auteur
GUERRA, Loubna
Directeur de thèse
ACHACHE Mohamed (Professeur)
Co-directeur
BENTERKI Djamel (Professeur)
Filière
Mathématiques
Diplôme
Magister
Titre
Etude théorique et numérique de quelques méthodes de points intérieurs pour l’optimisation quadratique semi-définie
Mots clés
algébrique-centralité-symétrisations---quadratique
Résumé
La méthode de trajectoire centrale de type primal-dual est é¢cace pour résoudre plusieurs problèmes d’optimisations. Notamment, la programmation quadratique semidé… nie (QSDP), car au niveau de la théorie, on obtient une meilleure complexité polynomiale qui est de l’ordre O(pn log(n¹0 ² )): Mais, l’absence de la symétrie des directions et l’obtention d’un point strictement réalisable (qui n’est pas évoqué dans notre étude) avec la mesure de proximité ±(X; Z; ¹) < 1 p2 justi…ent la di¢culté de cette méthode. Dans ce mémoire, on développe un algorithme de trajectoire centrale de type primaldual à petit pas pour résoudre un problème quadratique semi-dé…ni (QSDP). Notons que notre étude à réaliser les contributions suivantes : - Etablir une condition su¢sante pour assurer la stricte faisabilité du pas de Newton complète. - Etablir l’in‡uence du pas de Newton complète en saut de dualité. - Etablir le taux de la réduction de ¹ pour réster proche de la trjectoire centrale dans le cas (QSDP) où les directions ne sont pas orthogonales. - Etablir l’existence et l’unicité de la direction de déplacement de (NT) par une condition su¢sante, qui devient une généralisation du résultat obtenu par Todd, Toh et Tütüncü en (SDP). Notre prochain travail concernant la résolution d’un problème (QSDP) par la méthode de trajectoire centrale basée sur les fonctions noyaux et une nouvelle transformation algébrique équivalente de puissance (Ã(t) = pt) appliquée à l’équation de centralité non linéaire avec d’autre schéma de symétrisations
Date de soutenance
2011
Cote
TH719
Pagination
P74
Format
CD
Statut
Soutenue