paysage et complexité pour des classes de problèmes d'optimisation non convexe
26/09/2025 à 14h00
M. Iskander LEGHERABA présente ses travaux en soutenance le 26/09/2025 à 14h00
À l'adresse suivante : Université Paris Dauphine-PSL - Place de Lattre de Tassigny 75775 Paris Cedex 16 Salle des thèses - D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
paysage et complexité pour des classes de problèmes d'optimisation non convexe
É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)
Yann CHEVALEYRE
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Yann CHEVALEYRE | Professeur des universités | Université Paris Dauphine-PSL | Directeur de these |
| M. Clément W. ROYER | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Co-encadrant de these |
| M. Serge GRATTON | Professeur des universités | Toulouse INP-ENSEEIHT | Rapporteur |
| Mme Elisa RICCIETTI | Associate professor | ENS Lyon | Examinateur |
| Mme Irène WALDSPURGER | Chargé de recherche | CEREMADE | Examinateur |
| M. Youssef DIOUANE | Professor | Polytechnique Montréal | Rapporteur |
Résumé
L'optimisation non convexe joue un rôle fondamental en mathématiques appliquées modernes, intervenant dans l'apprentissage automatique, le traitement du signal, la théorie du contrôle et l'algèbre linéaire numérique. Bien que les problèmes non convexes soient souvent complexes en raison de paysages comportant de multiples minima locaux et points-selles, des travaux récents ont montré que certains d'entre eux bénéficiant d'une structure spécifique—en particulier ceux possédant certaines caractéristiques algébriques ou géométriques—admettent des solutions efficaces.
Cette thèse aborde l'optimisation non convexe sous deux angles complémentaires. Premièrement, nous analysons des problèmes d'optimisation matricielle, motivés par leurs liens avec la théorie de l'apprentissage profond—notamment l'entraînement des réseaux linéaires—et avec l'algèbre linéaire numérique—notamment l'approximation de fonctions matricielles. Plus précisément, nous nous concentrons sur l'approximation de la racine carrée et, par une analyse du paysage d'optimisation, nous caractérisons des classes de points critiques, identifions certaines conditions garantissant que tous les minima locaux sont globaux, et étudions des phénomènes tels que l'apparition de points-selles d'ordre supérieur. Dans un second temps, nous abordons des problèmes non convexes plus généraux, en nous concentrant sur les problèmes de type moindres carrés non linéaires. Nous y analysons différents algorithmes, incluant des méthodes de type Newton, pour lesquels nous établissons des garanties de complexité en termes de nombre d'itérations et d'opérations pour obtenir des points critiques au premier et second ordre.