Cette thèse s'attache à l'étude des problèmes d'optimisation stochastique, en les abordant sous divers angles. Le premier chapitre donne un panorama des problèmes d'optimisation stochastique. Le deuxième chapitre montre qu'en dimension un, seuls les systèmes à espace d'état à dynamique et observation linéaire sont sans effet dual en boucle ouverte. Le troisième chapitre s'attache à montrer la nécessité de tenir compte de la structure d'information dans la discrétisation et les résultats de stabilité pour les problèmes à plusieurs pas de temps. Le quatrième chapitre propose une nouvelle famille d'algorithmes stochastiques permettant de rechercher les commandes optimales fonctionnellement sans aucune discrétisation préalable de l'aléa, et avec une garantie asymptotique d'optimalité. Le cinquième chapitre étudie les possibilités de décomposition et d'agrégation pour les problèmes stochastiques de grande taille.

Pour optimiser la gestion des réseaux de télécommunication, nous considérons le système de file d'attente M^X / G / 1 avec rappels et clients impatients. En utilisant la méthode des variables supplémentaires, nous obtenons les fonctions génératrices partielles de l'état stationnaire conjointe de l'état du serveur et du nombre de clients dans le groupe de rappels. Pour compléter l'analyse du modèle considéré, nous calculons la distribution stationnaire de la chaîne de Markov induite, grâce à laquelle nous présentons la propriété de la décomposition stochastique. Cependant, la fonction génératrice de la distribution stationnaire du nombre de clients dans le groupe de rappels, est obtenue sous une forme explicite, très complexe et ne révèle pas la nature de la distribution en question. Alors, nous étudions le comportement asymptotique de la variable aléatoire représentant le nombre de clients en orbite et dans le système pour des valeurs limites des différents paramètres. Nous complétons notre travail par des exemples numériques.

La question de l'accès au soin est cruciale dans notre société moderne. Un effet évident de la demande accrue de services de santé est l'augmentation du taux d'occupation dans les hôpitaux. La principale différence entre la dispensation de soins à l'hôpital et au domicile est la suivante: le patient doit se déplacer et toutes les ressources nécessaires à son traitement se trouvent dans le même endroit, tandis que dans les soins délivrés au domicile, les ressources doivent être déplacées au chevet du patient. Il existe plusieurs défis afin de pouvoir réaliser ce changement. Dans cette thèse nous traitons trois problèmes importants dans la conception des structures de soins à domicile. D'abord, la localisation des structures en minimisant les coûts logistiques, où nous développons trois modèles incluant différentes caractéristiques comme du système de santé comme les coûts liés aux déplacements des ressources, la variation de la demande dans le temps et l'existence et évolution des ressource libérales. Ces modèles nous permettent de proposer des localisations robustes dans le temps tout en assurant une couverture maximale et en minimisant les coûts. La deuxième problématique consiste au choix des activités et couverture épidémiologique et spatiale en tenant compte différentes activités et types de ressources, les autorisations pour réaliser les pathologies et la couverture. Deux modèles développés nous ont permis montrer les effets sur l'affectation de la demande et le dimensionnement de ressources induits par changements dans les coûts des libéraux, salaires et d'autorisation de servir la demande. Le troisième problème et celui du dimensionnement de ressources avec incertitudes de demande (volume, épidémiologique et géographique) et le modèle proposé tient compte du problème sous-jacent de déplacement des ressources à l'aide d'une estimation de la tournée réalisée.

Historiquement, les inégalités d'oracle ont été développées comme des outils particulièrement efficaces pour l'adaptation à un paramètre inconnu en statistique mathématique. Initialement dédiées à la démonstration de propriétés statistiques de certains estimateurs, elles peuvent s'inscrire dans le cadre plus général du problème l'agrégation où elles sont au centre de la définition d'une vitesse optimale d'agrégation. Elles constituent alors d'une part des outils mathématiques et d'autre part des résultats précis et non asymptotiques.<br />Les travaux faisant l'objet de cette thèse présentent différentes utilisations des inégalités d'oracle, d'abord dans un cadre général d'agrégation puis dans des modèles statistiques plus particuliers, comme l'estimation de densité et la classification. Les résultats obtenus sont une palette non exhaustive mais représentative de l'utilisation des inégalités d'oracle en statistique mathématique.

L'utilisation d'équipes de robots a pris de l'ampleur ces dernières années. Cela est dû aux avantages que peut offrir une équipe de robot par rapport à un robot seul pour la réalisation d'une même tâche. Cela s'explique aussi par le fait que ce type de plates-formes deviennent de plus en plus abordables et fiables. Ainsi, l'utilisation d'une équipe de véhicules aériens devient une alternative viable. Cette thèse se concentre sur le problème du déploiement d'une équipe de Micro-Véhicules Aériens (MAV) pour effectuer des missions de surveillance sur un terrain inconnu de morphologie arbitraire. Puisque la morphologie du terrain est inconnue et peut être complexe et non-convexe, les algorithmes standards ne sont pas applicables au problème particulier traité dans cette thèse. Pour y remédier, une nouvelle approche basée sur un algorithme d'optimisation cognitive et adaptatif (CAO) est proposée et évaluée. Une propriété fondamentale de cette approche est qu'elle partage les mêmes caractéristiques de convergence que les algorithmes de descente de gradient avec contraintes qui exigent une connaissance parfaite de la morphologie du terrain pour optimiser la couverture. Il est également proposé une formulation différente du problème afin d'obtenir une solution distribuée, ce qui nous permet de surmonter les inconvénients d'une approche centralisée et d'envisager également des capacités de communication limitées. De rigoureux arguments mathématiques et des simulations étendues établissent que l'approche proposée fournit une méthodologie évolutive et efficace qui intègre toutes les contraintes physiques particulières et est capable de guider les robots vers un arrangement qui optimise localement la surveillance. Finalement, la méthode proposée est mise en œuvre sur une équipe de MAV réels pour réaliser la surveillance d'un environnement extérieur complexe.

Le travail présenté ici s'intéresse à la résolution numérique de problèmes de commande optimale stochastique de grande taille. Nous considérons un système dynamique, sur un horizon de temps discret et fini, pouvant être influencé par des bruits exogènes et par des actions prises par le décideur. L'objectif est de contrôler ce système de sorte à minimiser une certaine fonction objectif, qui dépend de l'évolution du système sur tout l'horizon. Nous supposons qu'à chaque instant des observations sont faites sur le système, et éventuellement gardées en mémoire. Il est généralement profitable, pour le décideur, de prendre en compte ces observations dans le choix des actions futures. Ainsi sommes-nous à la recherche de stratégies, ou encore de lois de commandes, plutôt que de simples décisions. Il s'agit de fonctions qui à tout instant et à toute observation possible du système associent une décision à prendre. Ce manuscrit présente trois contributions. La première concerne la convergence de méthodes numériques basées sur des scénarios. Nous comparons l'utilisation de méthodes basées sur les arbres de scénarios aux méthodes particulaires. Les premières ont été largement étudiées au sein de la communauté "Programmation Stochastique". Des développements récents, tant théoriques que numériques, montrent que cette méthodologie est mal adaptée aux problèmes à plusieurs pas de temps. Nous expliquons ici en détails d'où provient ce défaut et montrons qu'il ne peut être attribué à l'usage de scénarios en tant que tel, mais plutôt à la structure d'arbre. En effet, nous montrons sur des exemples numériques comment les méthodes particulaires, plus récemment développées et utilisant également des scénarios, ont un meilleur comportement même avec un grand nombre de pas de temps. La deuxième contribution part du constat que, même à l'aide des méthodes particulaires, nous faisons toujours face à ce qui est couramment appelé, en commande optimale, la malédiction de la dimension. Lorsque la taille de l'état servant à résumer le système est de trop grande taille, on ne sait pas trouver directement, de manière satisfaisante, des stratégies optimales. Pour une classe de systèmes, dits décomposables, nous adaptons des résultats bien connus dans le cadre déterministe, portant sur la décomposition de grands systèmes, au cas stochastique. L'application n'est pas directe et nécessite notamment l'usage d'outils statistiques sophistiqués afin de pouvoir utiliser la variable duale qui, dans le cas qui nous intéresse, est un processus stochastique. Nous proposons un algorithme original appelé Dual Approximate Dynamic Programming (DADP) et étudions sa convergence. Nous appliquons de plus cet algorithme à un problème réaliste de gestion de production électrique sur un horizon pluri-annuel. La troisième contribution de la thèse s'intéresse à une propriété structurelle des problèmes de commande optimale stochastique : la question de la consistance dynamique d'une suite de problèmes de décision au cours du temps. Notre but est d'établir un lien entre la notion de consistance dynamique, que nous définissons de manière informelle dans le dernier chapitre, et le concept de variable d'état, qui est central dans le contexte de la commande optimale. Le travail présenté est original au sens suivant. Nous montrons que, pour une large classe de modèles d'optimisation stochastique n'étant pas a priori consistants dynamiquement, on peut retrouver la consistance dynamique quitte à étendre la structure d'état du système

Cette thèse est consacrée à l'étude théorique et numérique d'algorithmes d'optimisation stochastiques adaptés au traitement du problème de planification des trajectoires d'avions en environnement incertain. L'optimisation des temps de vol et de la consommation de carburant est un élément central de la compétitivité des compagnies aériennes. Elles sont à la recherche d'outils permettant d'optimiser le choix de leurs routes aériennes avec toujours plus de précision. Pourtant, les méthodes actuellement disponibles pour l'optimisation de ces routes aériennes requièrent l'utilisation de représentations simplifiées des performances avion. Nous proposons, dans cette thèse, de répondre à cette exigence de précision et d'adapter, par conséquent, nos méthodes de résolution aux contraintes de la modélisation industrielle des performances avion tout en tenant compte de l'incertitude qui pèse sur les conditions réelles de vol (trafic aérien et conditions atmosphériques). Nous appuyons notre démarche par trois contributions scientifiques. Premièrement, nous avons mis en place un environnement de test pour algorithmes d'optimisation de trajectoires. Ce cadre a permis d'unifier la procédure de test pour l'ensemble des modèles de performances avion. Deuxièmement, nous avons développé et analysé sur le plan théorique deux nouveaux algorithmes d'optimisation stochastique globale en l'absence de dérivés. La première approche, très générique, n'utilise pas d'information particulière liée à la dynamique avion. Il s'agit de l'algorithme NSA basé sur la méthode du recuit simulé. Les développements théoriques ont abouti à la formulation des conditions et vitesse de convergence de cet algorithme. La seconde approche, l'algorithme SPY, est plus spécifique, il utilise une information de régularité lipschitzienne autour de l'optimum recherche. Il s'agit d'un algorithme de type bandits Lipschitz, basé sur la méthode de Piyavskii. De même, nous analysons les conditions de convergence de cet algorithme et fournissons une borne supérieure sur son erreur d'optimisation (regret simple). / This PhD thesis is dedicated to the theoretical and numerical analysis of stochastic algorithms for the stochastic flight planning problem. Optimizing the fuel consumption and flight time is a key factor for airlines to be competitive. These companies thus look for flight optimization tools with higher and higher accuracy requirements. However, nowadays available methodologies for flight planning are based on simplified aircraft performance models. In this PhD, we propose to fulfill the accuracy requirements by adapting our methodology to both the constraints induced by the utilization of an industrial aircraft performance computation code and the consideration of the uncertainty about the real flight conditions, i.e., air traffic and weather conditions. Our proposal is supported by three main contributions. First, we design a numerical framework for benchmarking aircraft trajectory optimization tools. This provides us a unified testing procedure for all aircraft performance models. Second, we propose and study (both theoretically and numerically) two global derivative-free algorithms for stochastic optimization problems. The first approach, the NSA algorithm, is highly generic and does not use any prior knowledge about the aircraft performance model. It is an extension of the simulated annealing algorithm adapted to noisy cost functions. We provide an upper bound on the convergence speed of NSA to globally optimal solutions. The second approach, the SPY algorithm, is a Lipschitz bandit algorithm derived from Piyavskii's algorithm. It is more specific as it requires the knowledge of some Lipschitz regularity property around the optimum, but it is therefore far more efficient. We also provide a theoretical study of this algorithm through an upper bound on its simple regret.

L'utilisation d'équipes de robots a pris de l'ampleur ces dernières années. Cela est dû aux avantages que peut offrir une équipe de robot par rapport à un robot seul pour la réalisation d'une même tâche. Cela s'explique aussi par le fait que ce type de plates-formes deviennent de plus en plus abordables et fiables. Ainsi, l'utilisation d'une équipe de véhicules aériens devient une alternative viable. Cette thèse se concentre sur le problème du déploiement d'une équipe de Micro-Véhicules Aériens (MAV) pour effectuer des missions de surveillance sur un terrain inconnu de morphologie arbitraire. Puisque la morphologie du terrain est inconnue et peut être complexe et non-convexe, les algorithmes standards ne sont pas applicables au problème particulier traité dans cette thèse. Pour y remédier, une nouvelle approche basée sur un algorithme d'optimisation cognitive et adaptatif (CAO) est proposée et évaluée. Une propriété fondamentale de cette approche est qu'elle partage les mêmes caractéristiques de convergence que les algorithmes de descente de gradient avec contraintes qui exigent une connaissance parfaite de la morphologie du terrain pour optimiser la couverture. Il est également proposé une formulation différente du problème afin d'obtenir une solution distribuée, ce qui nous permet de surmonter les inconvénients d'une approche centralisée et d'envisager également des capacités de communication limitées. De rigoureux arguments mathématiques et des simulations étendues établissent que l'approche proposée fournit une méthodologie évolutive et efficace qui intègre toutes les contraintes physiques particulières et est capable de guider les robots vers un arrangement qui optimise localement la surveillance. Finalement, la méthode proposée est mise en œuvre sur une équipe de MAV réels pour réaliser la surveillance d'un environnement extérieur complexe. / The use of multi-robot teams has gained a lot of attention in recent years. This is due to the extended capabilities that the teams offer compared to the use of a single robot for the same task. Moreover, as these platforms become more and more affordable and robust, the use of teams of aerial vehicles is becoming a viable alternative. This thesis focuses on the problem of deploying a swarm of Micro Aerial Vehicles (MAV) to perform surveillance coverage missions over an unknown terrain of arbitrary morphology. Since the terrain's morphology is unknown and it can be quite complex and non-convex, standard algorithms are not applicable to the particular problem treated in this thesis. To overcome this, a new approach based on the Cognitive-based Adaptive Optimization (CAO) algorithm is proposed and evaluated. A fundamental property of this approach is that it shares the same convergence characteristics as those of constrained gradient-descent algorithms, which require perfect knowledge of the terrain's morphology to optimize coverage. In addition, it is also proposed a different formulation of the problem in order to obtain a distributed solution, which allows us to overcome the drawbacks of a centralized approach and to consider also limited communication capabilities. Rigorous mathematical arguments and extensive simulations establish that the proposed approach provides a scalable and efficient methodology that incorporates any particular physical constraints and limitations able to navigate the robots to an arrangement that (locally) optimizes the surveillance coverage. The proposed method is finally implemented in a real swarm of MAVs to carry out surveillance coverage in an outdoor complex area.

Nous établissons un théorème de convergence locale de l'algorithme classique d'optimisation de système dynamique RTRL, appliqué à un système non linéaire. L'algorithme RTRL est un algorithme en ligne, mais il doit maintenir une grande quantités d'informations, ce qui le rend impropre à entraîner des systèmes d'apprentissage de taille moyenne. L'algorithme NBT y remédie en maintenant une approximation aléatoire non biaisée de faible taille de ces informations. Nous prouvons également la convergence avec probabilité arbitrairement proche de un, de celui-ci vers l'optimum local atteint par l'algorithme RTRL. Nous formalisons également l'algorithme LLR et en effectuons une étude expérimentale, sur des données synthétiques. Cet algorithme met à jour de manière adaptive le pas d'une descente de gradient, par descente de gradient sur celui-ci. Il apporte ainsi une réponse partielle au problème de la fixation numérique du pas de descente, dont le choix influence fortement la procédure de descente et qui doit sinon faire l'objet d'une recherche empirique potentiellement longue par le praticien. / We prove a local convergence theorem for the classical dynamical system optimization algorithm called RTRL, in a nonlinear setting. The rtrl works on line, but maintains a huge amount of information, which makes it unfit to train even moderately big learning models. The NBT algorithm turns it by replacing these informations by a non-biased, low dimension, random approximation. We also prove the convergence with arbitrarily close to one probability, of this algorithm to the local optimum reached by the RTRL algorithm. We also formalize the LLR algorithm and conduct experiments on it, on synthetic data. This algorithm updates in an adaptive fashion the step size of a gradient descent, by conducting a gradient descent on this very step size. It therefore partially solves the issue of the numerical choice of a step size in a gradient descent. This choice influences strongly the descent and must otherwise be hand-picked by the user, following a potentially long research.

Le fil rouge de cette thèse est l'étude des processus de Hawkes. Ces processus ponctuels décryptent l'inter-causalité qui peut avoir lieu entre plusieurs séries d'événements. Concrètement, ils déterminent l'influence qu'ont les événements d'une série sur les événements futurs de toutes les autres séries. Par exemple, dans le contexte des réseaux sociaux, ils décrivent à quel point l'action d'un utilisateur, par exemple un Tweet, sera susceptible de déclencher des réactions de la part des autres.Le premier chapitre est une brève introduction sur les processus ponctuels suivie par un approfondissement sur les processus de Hawkes et en particulier sur les propriétés de la paramétrisation à noyaux exponentiels, la plus communément utilisée. Dans le chapitre suivant, nous introduisons une pénalisation adaptative pour modéliser, avec des processus de Hawkes, la propagation de l'information dans les réseaux sociaux. Cette pénalisation est capable de prendre en compte la connaissance a priori des caractéristiques de ces réseaux, telles que les interactions éparses entre utilisateurs ou la structure de communauté, et de les réfléchir sur le modèle estimé. Notre technique utilise des pénalités pondérées dont les poids sont déterminés par une analyse fine de l'erreur de généralisation.Ensuite, nous abordons l'optimisation convexe et les progrès réalisés avec les méthodes stochastiques du premier ordre avec réduction de variance. Le quatrième chapitre est dédié à l'adaptation de ces techniques pour optimiser le terme d'attache aux données le plus couramment utilisé avec les processus de Hawkes. En effet, cette fonction ne vérifie pas l'hypothèse de gradient-Lipschitz habituellement utilisée. Ainsi, nous travaillons avec une autre hypothèse de régularité, et obtenons un taux de convergence linéaire pour une version décalée de Stochastic Dual Coordinate Ascent qui améliore l'état de l'art. De plus, de telles fonctions comportent beaucoup de contraintes linéaires qui sont fréquemment violées par les algorithmes classiques du premier ordre, mais, dans leur version duale ces contraintes sont beaucoup plus aisées à satisfaire. Ainsi, la robustesse de notre algorithme est d'avantage comparable à celle des méthodes du second ordre dont le coût est prohibitif en grandes dimensions.Enfin, le dernier chapitre présente une nouvelle bibliothèque d'apprentissage statistique pour Python 3 avec un accent particulier mis sur les modèles temporels. Appelée tick, cette bibliothèque repose sur une implémentation en C++ et les algorithmes d'optimisation issus de l'état de l'art pour réaliser des estimations très rapides dans un environnement multi-cœurs. Publiée sur Github, cette bibliothèque a été utilisée tout au long de cette thèse pour effectuer des expériences. / The common thread of this thesis is the study of Hawkes processes. These point processes decrypt the cross-causality that occurs across several event series. Namely, they retrieve the influence that the events of one series have on the future events of all series. For example, in the context of social networks, they describe how likely an action of a certain user (such as a Tweet) will trigger reactions from the others.The first chapter consists in a general introduction on point processes followed by a focus on Hawkes processes and more specifically on the properties of the widely used exponential kernels parametrization. In the following chapter, we introduce an adaptive penalization technique to model, with Hawkes processes, the information propagation on social networks. This penalization is able to take into account the prior knowledge on the social network characteristics, such as the sparse interactions between users or the community structure, to reflect them on the estimated model. Our technique uses data-driven weighted penalties induced by a careful analysis of the generalization error.Next, we focus on convex optimization and recall the recent progresses made with stochastic first order methods using variance reduction techniques. The fourth chapter is dedicated to an adaptation of these techniques to optimize the most commonly used goodness-of-fit of Hawkes processes. Indeed, this goodness-of-fit does not meet the gradient-Lipschitz assumption that is required by the latest first order methods. Thus, we work under another smoothness assumption, and obtain a linear convergence rate for a shifted version of Stochastic Dual Coordinate Ascent that improves the current state-of-the-art. Besides, such objectives include many linear constraints that are easily violated by classic first order algorithms, but in the Fenchel-dual problem these constraints are easier to deal with. Hence, our algorithm's robustness is comparable to second order methods that are very expensive in high dimensions.Finally, the last chapter introduces a new statistical learning library for Python 3 with a particular emphasis on time-dependent models, tools for generalized linear models and survival analysis. Called tick, this library relies on a C++ implementation and state-of-the-art optimization algorithms to provide very fast computations in a single node multi-core setting. Open-sourced and published on Github, this library has been used all along this thesis to perform benchmarks and experiments.