Soutenance de thèse

Je soutiendrai ma thèse, intitulée “Optimisation et contrôle de systèmes à grande échelle: comment combattre l’optimisation combinatoire” le mercredi 29 septembre à 10h30. La soutenance est publique sera en français. Elle sera suivi d’un pot au même endroit. Une version provisoire du manuscrit est disponible.

Un résumé et les indications pour venir se trouvent ci dessous.

Jury

Comment venir?

La soutenance aura lieu dans le grand amphi de l’INRIA Rhône Alpes. Pour venir à l’INRIA, voir la page contact ou des indications ainsi qu’un plan d’accès sur le site de l’INRIA.

Résumé — abstract

Résumé en français

Dans cette thèse, nous étudions des méthodes permettant le contrôle et l’optimisation de systèmes à grande échelle à travers l’étude de modèles stochastiques. Les modèles classiques souffrent tous du même problème: le nombre d’états pour décrire le système explose lorsque la taille du système étudié grandit.

Dans une première partie, nous présentons deux méthodes différentes pour réduire la complexité du modèle en agrégeant les états des différents objets: l’introduction d’une fonction potentielle manipulée par un adversaire et les modèles champ moyen. Nous montrons comment ces méthodes peuvent être appliquées pour étudier le vol de travail.

Puis, nous nous intéressons au contrôle optimal de grands systèmes stochastiques. Nous étendons les résultats classiques champ moyen à des problèmes d’optimisation et de contrôle. Nous montrons que sous des hypothèses faibles, résoudre le problème d’optimisation initial est asymptotiquement équivalent à la résolution d’un problème d’optimisation déterministe. Cela permet en pratique d’évaluer les performances d’une politique de façon beaucoup plus rapide et de résoudre des problèmes jusqu’ici impossibles.

Résumé en anglais

The goal of this thesis is to provide methods for the control and the optimization of large-scale systems, starting from stochastic models that approximate its behavior. However, such models suffer from the curse of dimensionality: the number of states needed to represent a system explodes when the size of the system grows.

In a first part, we present two different methods to reduce the complexity of the model by aggregating the states of the different objects. These two methods are illustrated by analyzing the performance of a distributed load balancing strategy, namely work-stealing. We first show how the use of a potential function leads to a tight analysis of the total completion time of a bag of tasks. Then we show how a mean field approximation can be used to study the steady-state of a grid scheduled by work-stealing.

Then, we focus on the optimal control of large stochastic systems. We extend classical mean field methods to study the controlled behavior of large systems. We show that under mild assumptions, solving an optimal control problem for a system with a large number of objects can be reduced to the solving of a problem for a deterministic system as the number of objects grows large. In practice, this allows one to evaluate the performance of a policy and provide a way to asymptotically solve problems that used to be intractable.