Perspectives graphiques et géométriques sur les familles positivement génératrices avec applications à l'optimisation sans dérivées
24/11/2025 à 14h00
M. Sébastien KERLEAU présente ses travaux en soutenance le 24/11/2025 à 14h00
À l'adresse suivante : Université Paris Dauphine-PSL, Pl. du Maréchal de Lattre de Tassigny, 75016 Paris Salle des thèses - D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Perspectives graphiques et géométriques sur les familles positivement génératrices avec applications à l'optimisation sans dérivées
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d'Analyse et de Modélisation de Systèmes d'Aide à la Décision
Section CNU
9 - Sciences et technologies de l'information et de la communication
Directeur(s)
Denis CORNAZ
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Denis CORNAZ | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Directeur de these |
| M. Charles AUDET | Professeur des universités | Polytechnique Montréal | Rapporteur |
| M. Clément ROYER | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Co-encadrant de these |
| M. Roland GRAPPE | Professeur des universités | UNIVERSITE PARIS DAUPHINE - PSL | Examinateur |
| M. Mourad BAIOU | Directeur de recherche | LIMOS, Centre National de la Recherche Scientifique | Rapporteur |
| Mme Aurélie LAGOUTTE | Maître de conférences | Université Grenoble-Alpes | Examinateur |
Résumé
Les familles positivement génératrices (PSSs) sont définies par leur capacité à engendrer l'entièreté de l'espace euclidien par des combinaisons linéaires à coefficients positifs ou nuls. De telles familles de vecteurs jouent un rôle important dans le cadre de l'optimisation continue, et plus particulièrement dans celui de l'optimisation sans dérivées. Dans ce contexte, les algorithmes directionnels de recherche directe se basent sur l'utilisation de PSSs pour explorer l'espace en quête d'un extremum de la fonction à optimiser.
Les performances de ces algorithmes sont impactées par la taille des PSSs considérés, mais aussi par la dispersion de leurs éléments dans l'espace, évaluée par leur mesure cosinus. Les bornes de complexité se voient ainsi réduites pour des familles alliant une faible cardinalité à une mesure cosinus élevée. A ce jour, il n'existe pourtant ni de caractérisation satisfaisante des bases positives - nom donné aux PSSs minimaux en termes d'inclusion - ni d'algorithme polynomial permettant d'évaluer la mesure cosinus d'une famille de vecteurs. Dans ce manuscrit, nous nous attachons à examiner chacun de ces deux problèmes, par l'étude théorique des propriétés des familles positivement génératrices.
Dans un premier temps, nous explorons les relations liant les matrices de réseaux de graphes fortement connexes aux représentations matricielles des PSSs. Nous exhibons ainsi une nouvelle caractérisation de ces familles, que nous affinons dans le but de caractériser les bases positives. Par la suite, nous démontrons l'existence d'algorithmes polynomiaux permettant de déterminer la mesure cosinus de certains classes de bases positives.
Nous démontrons qu'il est possible, à l'aide de ces familles, de construire des PSSs résilients qui conservent une mesure cosinus satisfaisante lorsqu'on retire un certain nombre de leurs éléments.
Enfin, nous introduisons un nouvel algorithme de recherche directe, plus robuste que ses prédécesseurs, basé sur l'utilisation de ces PSSs résilients.