Résultats de l’appel IEA 2023 : 5 lauréats à CNRS Sciences informatiques

Quasi-Polynomial Time Approximation Algorithms for Some Network Design Optimization Problems

Il existe un large éventail d'applications pour les problèmes d'optimisation de la conception des réseaux dans les systèmes de transport et de télécommunication. Néanmoins, une part importante de ces problèmes devient NP-difficile lorsqu'il s'agit de graphes métriques. Malheureusement, l'obtention de solutions même approximatives en temps polynomial s'est avérée difficile pour plusieurs problèmes d'optimisation de la conception des réseaux. Par conséquent, une tendance plus récente a émergé, se concentrant sur les algorithmes d'approximation qui s'exécutent en temps quasi-polynomial.

Ce projet porté par, Ralf Klasing, directeur de recherche CNRS au Laboratoire bordelais de recherche en informatique (LaBRI – CNRS/Bordeaux INP/Université de Bordeaux), vise à faire progresser systématiquement cette orientation de recherche en présentant de nouvelles perspectives concernant les deux problèmes d'optimisation de conception de réseau suivants : le problème du centre p-hub ; le problème du centre p-hub en étoile. L'objectif est de concevoir des algorithmes en temps quasi-polynomial pour résoudre les deux problèmes cibles ou de montrer que de tels algorithmes n'existent pas sous certaines hypothèses de complexité théorique. Le domaine des algorithmes d'approximation en temps quasi-polynomial reste un domaine de recherche relativement naissant, et la construction de son cadre théorique constitue un effort continu. En relevant les défis d'optimisation de la conception des réseaux dans ce projet, les scientifiques impliqués dans le projets espèrent découvrir des stratégies globales et contribuer à l'établissement de la théorie de l'inapproximabilité relative aux algorithmes en temps quasi-polynomial.

Blackbox Optimization with a Novel Use of Subspaces

Les outils de calcul numérique toujours plus performants ont conduit à de grandes avancées dans le recours à la simulation physique ainsi qu'à l'intelligence artificielle. À mesure que ces processus gagnent en complexité, ils incorporent un nombre croissant de paramètres, qui doivent être calibrés pour obtenir la meilleure performance. L'optimisation de boîtes noires s'intéresse à l'obtention des meilleurs paramètres au sens d'un critère donné, au moyen d'algorithmes dits sans dérivées. Ces techniques sont par nature peu efficaces en présence d'un grand nombre de paramètres. Le projet BONUS, piloté par Clément Royer, maître de conférences à l’Université Paris Dauphine - PSL, membre du Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE - CNRS/Université Paris Dauphine - PSL) et co-porté par Lindon Roberts, maître de conférences à l’Université de Sydney, s'intéresse à l'utilisation d'aléatoire dans les algorithmes sans dérivées, notamment en présence de contraintes sur les paramètres, qui représentent à la fois des difficultés pratiques et des considérations pratiques.

Distributed optimization-inspired samplers for high dimensional inverse problems in imaging

L'inférence bayésienne est régulièrement utilisée pour résoudre des problèmes inverses de grande dimension en imagerie, notamment pour des applications en astronomie et en télédétection. Le coût calculatoire des algorithmes d'inférence peut être important, notamment lorsque le nombre d'observations et de paramètres à estimer augmentent. En l'absence de vérité terrain, la capacité à former efficacement des estimateurs dont l'incertitude est quantifiable est primordiale.

Pour traiter des problèmes inverses de grande dimension en un temps raisonnable, des algorithmes d'inférence rapides et distribués sont nécessaires, déployés sur de grandes infrastructures de calcul. Une approche synchrone est pertinente lorsque le problème peut être décomposé en sous-tâches de coûts de calcul similaire. Dans le cas contraire, un algorithme asynchrone peut être plus adapté. Plusieurs algorithmes d'optimisation asynchrones ont été proposés afin de limiter l'impact des unités de calcul les plus lentes sur la vitesse de production d'un estimateur. Les algorithmes MCMC asynchrones, qui fournissent d'emblée une quantification des incertitudes d'estimation, ont peu été explorés jusqu'ici.

Ce projet consiste à résoudre des problèmes inverses de grande dimension, dont les tâches de calcul ont des coûts très hétérogènes. Tirant parti de travaux récents en optimisation, les algorithmes considérés ont pour but de produire rapidement un estimateur, assorti d'une quantification d'incertitude. Le projet développera la collaboration entre Pierre Chainais, professeur à Centrale Lille, membre du CRIStAL, Marcelo Pereyra, professeur à Heriot-Watt University, Audrey Repetti, maîtresse de conférences à Heriot-Watt University et Pierre-Antoine Thouvenin, maître de conférences à Centrale Lille, membre du Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL - CNRS/Université de Lille/Centrale Lille).

Dynamic Configuration of Black-box Optimization Algorithms via Algorithm Configuration and Reinforcement Learning

Sur la base de récents travaux communs, le projet, porté par Carola Doerr, directrice de recherche CNRS au laboratoire LIP6 (CNRS/Sorbonne Université), vise à développer des techniques d'apprentissage automatique (AutoML) pour l'apprentissage de politiques de contrôle dynamique pour les heuristiques d'optimisation boîte noire.

Les deux approches principales étudiées sont les techniques d'apprentissage par renforcement profond (deep-RL) et les algorithmes de configuration automatisés. L'originalité de l’approche réside dans l’utilisation de paramètres dont les politiques de contrôle sont connues et dont l'optimalité est prouvée. Bien que l'on pense généralement que de tels problèmes « jouets » sont trop simplistes, les travaux récents soulignent l'importance de défier les approches AutoML avec ces exemples, afin d'examiner où et pourquoi les techniques de pointe échouent. En contrôlant la dimension du problème, la taille de l'espace d'action et d'état, les niveaux de bruit, etc., les porteurs et porteuses de projet ont un contrôle fin sur les paramètres qui est demandé aux approches AutoML de résoudre. Les travaux récents montrent que les méthodes standard - bien qu’efficaces en robotique et dans les jeux - nécessitent une adaptation substantielle pour être efficients dans les scénarios d'optimisation à boîte noire.

Les deux principaux objectifs sont donc les suivants :

• Le développement de benchmarks avec des politiques optimales éprouvées et des caractéristiques évolutives telles que décrites ci-dessus,
• L'adaptation des techniques deep-RL et configuration automatique des algorithmes à l'optimisation boîte noire.

Pour en savoir plus

• Carola Doerr : la médaille de bronze du CNRS pour l’optimisation de boîtes noires : actualité publiée dans le cadre de la médaille de bronze du CNRS (09/06/2022)

Probabilistic Reliable and Efficient numerics for Stochastically-constrained Trajectory Optimization

Le développement de nouvelles méthodes de contrôle visant à minimiser la consommation de carburant est essentiel pour la conception de systèmes dynamiques durables. Les diverses contraintes associées, déterministes ou probabilistes, issues de conditions environnementales incertaines ou de contraintes opérationnelles, sont difficilement prises en compte par la théorie du contrôle classique et leur traitement nécessite souvent de combiner des techniques plus avancées de modélisation probabiliste et d'optimisation.

Ce projet de recherche rassemble deux scientifiques du Laboratoire de recherche spécialisé dans l’analyse et l’architecture des systèmes (LAAS-CNRS) - Denis Arzelier, directeur de recherche CNRS et Mioara Maria Joldes, directrice de recherche CNRS et un doctorant - Matthieu Masson, et une équipe italienne composée de Fabrizio Dabbene et Martina Mammarella, directeur et directrice de recherche du Conseil national de la recherche (CNR) en Italie au Politecnico di Torino. Les premiers se sont principalement concentrés sur les approximations rigoureuses et robustes, tandis que les seconds sont experts en techniques probabilistes appliquées aux contrôles prédictifs. L'objectif principal de cette première collaboration est de développer des algorithmes numériques efficaces et fiables pour le contrôle optimal en temps fixé. Un exemple pertinent concerne la conception des plans de manœuvres d'évitement de débris pour les satellites situés en orbite basse autour de la Terre.

Pour en savoir plus

• La rigueur au service de l’aérospatial : Mioara Joldes obtient la médaille de bronze du CNRS : actualité publiée dans le cadre de la médaille de bronze du CNRS (08/10/2021)