Search

Hybrid electric vehicle have known a quickly grow in the last 10 years.Between conventional vehicles which are criticized for their CO2 emissionand electric vehicles which have a big issue about autonomy, hybrid electricones seems to be a good trade of. No standard has been set yet, and the architecturesresulting of theses productions vary between brands. Nevertheless,all of them are design as a thermal vehicle with battery added which leadsto bad sizing of the component, specially internal combustion engine andbattery capacity. Consequently, the control strategy applied to its componentshas a lot of constraints and cannot be optimal.This thesis investigate a new methodology to design and control a hybridelectric vehicle. Based on statistical description of driving cycle and the generationof random cycle, a new way of sizing component is presented. Thecontrol associate is then determined and apply for different scenarios : firstlya heavy vehicle : A truck and then a lightweight vehicle. An offline controlbased on the optimization of the power split via a dynamic programmingalgorithm is presented to get the optimal results for a given driving cycle.A real time control strategy is then define with its optimization for a givenpatterns and compared to the offline results. Finally, a new control of plug inhybrid electric vehicle based on destination predictions is presented., Depuis une dizaine d’années, les constructeurs et les grands groupesdu secteur de l’automobile se sont mobilisés autour de la recherche et dudéveloppement de nouveaux prototypes de véhicules économes (moins consommateursd’énergie) et propres (moins de rejets de polluants) tels queles véhicules hybrides et tout électriques. C’est une nouvelle mutation. Ellefait profondément évoluer l’automobile, d’une architecture de propulsionthermique, devenue maîtrisée mais fortement polluante, vers une tractionélectrique ou hybride plus complexe et peu, voire pas du tout, maîtrisée ;le nombre de composants (sources d’énergie, actionneurs, contrôleurs, calculateurs,...) devient important, de nature multidisciplinaire et possédantbeaucoup de non linéarités. De plus, faute de maturité dans ce domaine, àce jour l’industrie de l’automobile ne possède pas encore les connaissancessuffisantes nécessaires à la modélisation, à la simulation et à la conceptionde ces nouveaux véhicules et plus particulièrement les dispositifs relatifs auxsources d’énergie et aux différents actionneurs de propulsion.Les travaux de cette thèse visent à donner des méthodes de conceptiond’une chaine de traction hybride et d’en gérer la gestion de l’énergie. Lathèse s’appuie sur l’exemple de la conception et la gestion de l’énergie d’unvéhicule hybride basé sur une pile à combustible et des batteries.Dans un premier temps, un méthode de dimensionnement des composantsde la chaine de traction est présentée : Elle consiste en l’étude statistique decycle de conduite générés pseudo aléatoirement représentatif de la conduiteen condition réelle de véhicule. Un générateur de cycle de conduite à été créeet est présenté, et la méthode de dimensionnement de la source primaire, iciune pile a combustible, ainsi que le source secondaire de puissance, ici desbatteries, est détaillée. Un exemple est pris pour illustrer cette méthode avecla conception d’un véhicule de type camion poubelle décrivant des cycles deconduites urbains à arrêts fréquents.Dans un second temps, la gestion de l’énergie de la chaine de traction hybridesérie est étudiée : une gestion de l’énergie “offline” est présentée, basé surl’optimisation par programmation dynamique. Cette optimisation permetd’avoir le découpage de la puissance par les deux sources de la chaine detraction de manière optimal pour un cycle précis. De part l’aspect déterministede la programmation dynamique, les résultats servent de référence quant aufuturs développements de gestion temps réel.Un contrôleur temps réel basé sur la logique floue est ainsi exposé et lesrésultats sont comparés par rapport à la gestion “offline”. Le contrôleurest ensuite optimisé et rendu adaptatif par un algorithme génétique et unalgorithme de reconnaissance de type de profil routier.Enfin, une introduction à la gestion de l’énergie dans les véhicules hybrides de type : “plug in” est présentée : Elle repose sur le principe de la déterminationde la distance restante à parcourir par la reconnaissance de la destination àl’aide d’une matrice de probabilité de Markov.

In this thesis, we studied the problem of traffic control by considering the new technologies as part of Intelligent Transport Systems (ITS). A new control strategy is introduced to exploit the potential of infrastructure traffic at a maximum level. Specifically, based Technology VII "Vehicle-Infrastructure Integration", the road infrastructure at intersections (considered also as a controller) can communicate with autonomous vehicles that arrive at a crossroads on a continuous basis. Important data such as vehicle speed, position and destination are then received by advanced sensors and sent to the controller in real time. Therefore, it is possible to develop a strategy for traffic control by treating each vehicle as an independent entity. In other words, the right of way is assigned to each vehicle based on its status and function of the overall state of traffic at the intersection. Only vehicles that have received the right of way may cross the junction. Traffic control at an intersection is therefore to determine the sequence of passage of vehicles, that is to say the sequences distribution rights passage.Cependant, the greatest difficulty to implement this new strategy is the contradiction between the optimization of sequences of passes of vehicles and time complexity. To resolve this contradiction, we first mathematically formulated the problem of regulation and we then studied its complexity. We proved initially that the problem of traffic control at the intersection isolated formulated is NP-hard under certain conditions (arbitrary number of groups CFA compliant streams, ...) and this is based on reducing the problem of 3-Partition. In a second step, we applied the methods of accurate resolutions on an isolated intersection to propose exact algorithms (Branch and Bound and Dynamic Programming) for finding an optimal sequence of passage. Several properties of the problem have been introduced and this proved and so they are exploited by these algorithms. These properties are intended to significantly reduce the search space and consequently the execution time of these algorithms exacts.Par Moreover, we have not limited our research on isolated intersections but we applied the approach control proposed a network of nodes while considering a single controller. However, an exact algorithm applied to several intersections can not be fast enough especially when you need to communicate information almost instantaneously to vehicles (real time). So we proposed methods to find approximate resolutions in a reasonable time a sequence of way satisfactory to each intersection. These algorithms (Genetic Algorithms) have indeed require less computation time while maintaining a good quality of solution.Enfin, we illustrate the implementation of deferential proposed approaches through simulation results to evaluate their performance ., Dans ce mémoire de thèse, nous avons étudié le problème de régulation du trafic en considérant les nouvelles technologies dans le cadre des Systèmes de Transport Intelligent (STI). Une nouvelle stratégie de contrôle est introduite afin d’exploiter le potentiel des infrastructures de la circulation à un niveau maximum. Plus précisément, basée sur la technologie VII « Intégration Véhicule-Infrastructure », l'infrastructure routière aux carrefours (considérée aussi comme contrôleur) peut communiquer avec les véhicules autonomes qui arrivent à un carrefour de manière continue. Les données importantes sur les véhicules telles que la vitesse, la position et la destination sont alors reçues par des capteurs avancés et envoyées au contrôleur en temps réel. Par conséquent, il est possible d'élaborer une stratégie de contrôle du trafic en considérant chaque véhicule comme une entité indépendante. En d'autres termes, le droit de passage est attribué à chaque véhicule en fonction de son état et en fonction de l'état global du trafic au carrefour. Seuls les véhicules qui ont reçu le droit de passage peuvent traverser le carrefour. Le contrôle du trafic au niveau d’un carrefour vise donc à déterminer les séquences de passage des véhicules, c’est-à-dire les séquences de distribution des droits de passage.Cependant, la plus grande difficulté pour appliquer cette nouvelle stratégie est la contradiction entre l'optimisation des séquences de passages des véhicules et la complexité temporelle. Pour résoudre cette contradiction, nous avons d’abord formulé mathématiquement la problématique de régulation et nous avons ensuite étudié sa complexité. Nous avons prouvé dans un premier temps que le problème de régulation du trafic formulé à l’intersection isolée est NP-hard sous certaines conditions (nombre arbitraire de groupes de flux compatibles GFC,…) et ceci en se basant sur la réduction au problème de 3-Partition. Dans un deuxième temps, nous avons appliqué les méthodes de résolutions exactes sur un carrefour isolé pour proposer des algorithmes exacts (Branch and Bound et Programmation dynamique) permettant de trouver une séquence de passage optimale. Plusieurs propriétés du problème ont été introduites et prouvées et ceci afin qu’elles soient exploitées par ces algorithmes. Ces propriétés ont pour objectif de réduire considérablement l’espace de recherche et par conséquent le temps d’exécution de ces algorithmes exacts.Par ailleurs, nous n’avons pas limité nos recherches sur des carrefours isolées mais nous avons appliqué l’approche de contrôle proposée sur un réseau de carrefours tout en considérant un seul contrôleur. Cependant, un algorithme exact appliqué sur plusieurs carrefours ne peut pas être assez rapide surtout lorsqu’on a besoin de communiquer presque instantanément des informations aux véhicules (en temps réel). Nous avons proposé donc des méthodes de résolutions approchées afin de trouver en un temps raisonnable une séquence de passage satisfaisante pour chaque carrefour. Ces algorithmes (Algorithmes génétiques) ont en effet, besoin de moins de temps de calcul tout en assurant une bonne qualité de solution.Enfin, nous illustrons la mise en œuvre des déférentes approches proposées à travers des résultats de simulation afin d’évaluer leurs performances.

Hybrid electric vehicle have known a quickly grow in the last 10 years.Between conventional vehicles which are criticized for their CO2 emissionand electric vehicles which have a big issue about autonomy, hybrid electricones seems to be a good trade of. No standard has been set yet, and the architecturesresulting of theses productions vary between brands. Nevertheless,all of them are design as a thermal vehicle with battery added which leadsto bad sizing of the component, specially internal combustion engine andbattery capacity. Consequently, the control strategy applied to its componentshas a lot of constraints and cannot be optimal.This thesis investigate a new methodology to design and control a hybridelectric vehicle. Based on statistical description of driving cycle and the generationof random cycle, a new way of sizing component is presented. Thecontrol associate is then determined and apply for different scenarios : firstlya heavy vehicle : A truck and then a lightweight vehicle. An offline controlbased on the optimization of the power split via a dynamic programmingalgorithm is presented to get the optimal results for a given driving cycle.A real time control strategy is then define with its optimization for a givenpatterns and compared to the offline results. Finally, a new control of plug inhybrid electric vehicle based on destination predictions is presented., Depuis une dizaine d’années, les constructeurs et les grands groupesdu secteur de l’automobile se sont mobilisés autour de la recherche et dudéveloppement de nouveaux prototypes de véhicules économes (moins consommateursd’énergie) et propres (moins de rejets de polluants) tels queles véhicules hybrides et tout électriques. C’est une nouvelle mutation. Ellefait profondément évoluer l’automobile, d’une architecture de propulsionthermique, devenue maîtrisée mais fortement polluante, vers une tractionélectrique ou hybride plus complexe et peu, voire pas du tout, maîtrisée ;le nombre de composants (sources d’énergie, actionneurs, contrôleurs, calculateurs,...) devient important, de nature multidisciplinaire et possédantbeaucoup de non linéarités. De plus, faute de maturité dans ce domaine, àce jour l’industrie de l’automobile ne possède pas encore les connaissancessuffisantes nécessaires à la modélisation, à la simulation et à la conceptionde ces nouveaux véhicules et plus particulièrement les dispositifs relatifs auxsources d’énergie et aux différents actionneurs de propulsion.Les travaux de cette thèse visent à donner des méthodes de conceptiond’une chaine de traction hybride et d’en gérer la gestion de l’énergie. Lathèse s’appuie sur l’exemple de la conception et la gestion de l’énergie d’unvéhicule hybride basé sur une pile à combustible et des batteries.Dans un premier temps, un méthode de dimensionnement des composantsde la chaine de traction est présentée : Elle consiste en l’étude statistique decycle de conduite générés pseudo aléatoirement représentatif de la conduiteen condition réelle de véhicule. Un générateur de cycle de conduite à été créeet est présenté, et la méthode de dimensionnement de la source primaire, iciune pile a combustible, ainsi que le source secondaire de puissance, ici desbatteries, est détaillée. Un exemple est pris pour illustrer cette méthode avecla conception d’un véhicule de type camion poubelle décrivant des cycles deconduites urbains à arrêts fréquents.Dans un second temps, la gestion de l’énergie de la chaine de traction hybridesérie est étudiée : une gestion de l’énergie “offline” est présentée, basé surl’optimisation par programmation dynamique. Cette optimisation permetd’avoir le découpage de la puissance par les deux sources de la chaine detraction de manière optimal pour un cycle précis. De part l’aspect déterministede la programmation dynamique, les résultats servent de référence quant aufuturs développements de gestion temps réel.Un contrôleur temps réel basé sur la logique floue est ainsi exposé et lesrésultats sont comparés par rapport à la gestion “offline”. Le contrôleurest ensuite optimisé et rendu adaptatif par un algorithme génétique et unalgorithme de reconnaissance de type de profil routier.Enfin, une introduction à la gestion de l’énergie dans les véhicules hybrides de type : “plug in” est présentée : Elle repose sur le principe de la déterminationde la distance restante à parcourir par la reconnaissance de la destination àl’aide d’une matrice de probabilité de Markov.

In this thesis, we studied the problem of traffic control by considering the new technologies as part of Intelligent Transport Systems (ITS). A new control strategy is introduced to exploit the potential of infrastructure traffic at a maximum level. Specifically, based Technology VII "Vehicle-Infrastructure Integration", the road infrastructure at intersections (considered also as a controller) can communicate with autonomous vehicles that arrive at a crossroads on a continuous basis. Important data such as vehicle speed, position and destination are then received by advanced sensors and sent to the controller in real time. Therefore, it is possible to develop a strategy for traffic control by treating each vehicle as an independent entity. In other words, the right of way is assigned to each vehicle based on its status and function of the overall state of traffic at the intersection. Only vehicles that have received the right of way may cross the junction. Traffic control at an intersection is therefore to determine the sequence of passage of vehicles, that is to say the sequences distribution rights passage.Cependant, the greatest difficulty to implement this new strategy is the contradiction between the optimization of sequences of passes of vehicles and time complexity. To resolve this contradiction, we first mathematically formulated the problem of regulation and we then studied its complexity. We proved initially that the problem of traffic control at the intersection isolated formulated is NP-hard under certain conditions (arbitrary number of groups CFA compliant streams, ...) and this is based on reducing the problem of 3-Partition. In a second step, we applied the methods of accurate resolutions on an isolated intersection to propose exact algorithms (Branch and Bound and Dynamic Programming) for finding an optimal sequence of passage. Several properties of the problem have been introduced and this proved and so they are exploited by these algorithms. These properties are intended to significantly reduce the search space and consequently the execution time of these algorithms exacts.Par Moreover, we have not limited our research on isolated intersections but we applied the approach control proposed a network of nodes while considering a single controller. However, an exact algorithm applied to several intersections can not be fast enough especially when you need to communicate information almost instantaneously to vehicles (real time). So we proposed methods to find approximate resolutions in a reasonable time a sequence of way satisfactory to each intersection. These algorithms (Genetic Algorithms) have indeed require less computation time while maintaining a good quality of solution.Enfin, we illustrate the implementation of deferential proposed approaches through simulation results to evaluate their performance ., Dans ce mémoire de thèse, nous avons étudié le problème de régulation du trafic en considérant les nouvelles technologies dans le cadre des Systèmes de Transport Intelligent (STI). Une nouvelle stratégie de contrôle est introduite afin d’exploiter le potentiel des infrastructures de la circulation à un niveau maximum. Plus précisément, basée sur la technologie VII « Intégration Véhicule-Infrastructure », l'infrastructure routière aux carrefours (considérée aussi comme contrôleur) peut communiquer avec les véhicules autonomes qui arrivent à un carrefour de manière continue. Les données importantes sur les véhicules telles que la vitesse, la position et la destination sont alors reçues par des capteurs avancés et envoyées au contrôleur en temps réel. Par conséquent, il est possible d'élaborer une stratégie de contrôle du trafic en considérant chaque véhicule comme une entité indépendante. En d'autres termes, le droit de passage est attribué à chaque véhicule en fonction de son état et en fonction de l'état global du trafic au carrefour. Seuls les véhicules qui ont reçu le droit de passage peuvent traverser le carrefour. Le contrôle du trafic au niveau d’un carrefour vise donc à déterminer les séquences de passage des véhicules, c’est-à-dire les séquences de distribution des droits de passage.Cependant, la plus grande difficulté pour appliquer cette nouvelle stratégie est la contradiction entre l'optimisation des séquences de passages des véhicules et la complexité temporelle. Pour résoudre cette contradiction, nous avons d’abord formulé mathématiquement la problématique de régulation et nous avons ensuite étudié sa complexité. Nous avons prouvé dans un premier temps que le problème de régulation du trafic formulé à l’intersection isolée est NP-hard sous certaines conditions (nombre arbitraire de groupes de flux compatibles GFC,…) et ceci en se basant sur la réduction au problème de 3-Partition. Dans un deuxième temps, nous avons appliqué les méthodes de résolutions exactes sur un carrefour isolé pour proposer des algorithmes exacts (Branch and Bound et Programmation dynamique) permettant de trouver une séquence de passage optimale. Plusieurs propriétés du problème ont été introduites et prouvées et ceci afin qu’elles soient exploitées par ces algorithmes. Ces propriétés ont pour objectif de réduire considérablement l’espace de recherche et par conséquent le temps d’exécution de ces algorithmes exacts.Par ailleurs, nous n’avons pas limité nos recherches sur des carrefours isolées mais nous avons appliqué l’approche de contrôle proposée sur un réseau de carrefours tout en considérant un seul contrôleur. Cependant, un algorithme exact appliqué sur plusieurs carrefours ne peut pas être assez rapide surtout lorsqu’on a besoin de communiquer presque instantanément des informations aux véhicules (en temps réel). Nous avons proposé donc des méthodes de résolutions approchées afin de trouver en un temps raisonnable une séquence de passage satisfaisante pour chaque carrefour. Ces algorithmes (Algorithmes génétiques) ont en effet, besoin de moins de temps de calcul tout en assurant une bonne qualité de solution.Enfin, nous illustrons la mise en œuvre des déférentes approches proposées à travers des résultats de simulation afin d’évaluer leurs performances.

Due to the emergence of new generation mobiles and media streaming services, data traffic on mobile networks is continuously exploding. Despite the emergence of standards such as LTE, resources still remain scarce and limited. Thus, efficiently sharing resources among broadcasters or between unicast receivers connected to the same base station is necessary. An efficient resources allocation, where a fair received video quality between users and an equal transmission delay are achieved, is targeted. To that end, the variety of the rate-distortion trade-off of multimedia content is exploited. First, a centralized joint encoding and transmission rate control of multiple programs sharing the same channel is considered. A satisfactory and a comparable video quality among the transmitted programs, with limited variations, as well as a comparable transmission delay are targeted. The problem is solved using constrained optimization tools. Second, only the bandwidth allocation control is centralized, the control of the encoding rate characteristics of each stream is carried in a distributed manner. By modeling the problem as a feedback control system, the centralized bandwidth allocation is required to feed back only the buffer level to its associated remote content provider. The equilibrium and stability issues are addressed for both bit and second buffer control. In the case of simple unicast connection, a cross-layer optimization of scalable video delivery over wireless channel is performed. The optimization problem is cast in the context of dynamic programming. When low complex model are considered and when the system characteristics are known, optimal solutions can be obtained. When the system is partially known, for example, when the state of the channel reaches the control process with delay, learning techniques are implemented.; Le développement simultané de terminaux mobiles multimédia (smartphones, tablettes) et de réseaux d’accès offrant des débits élevés conduit à une explosion du trafic liés aux contenus multimédia. Cette croissance nécessite un partage efficace des ressources radio entre fournisseurs de contenus (dans le cas de la diffusion) ou entre récepteurs (dans le cas de services de vidéo à la demande). Cette thèse propose des outils de partage équitable des ressources en termes de qualité des contenus multimédia reçu et de délai de transmission dans les deux contextes précédents. La variété des compromis débit-distorsion des contenus multimédia est exploitée à cet effet. Dans un premier temps, une solution centralisée de contrôle conjoint du débit de codage et de transmission de plusieurs programmes transmis sur un même canal est considérée. L’objectif est de fournir des flux de qualités similaires avec des variations limitées, tout en assurant des délais de transmission comparables. Ce problème est résolu en synthétisant une commande prédictive à l’aide d’outils d’optimisation sous contrainte. Dans un second temps, seule l’allocation de bande est centralisée, le contrôle des caractéristiques de compression de chaque flux est réalisé de manière distribuée. Le contrôleur centralisé ne renvoie que le niveau de remplissage des tampons associés à chaque flux aux fournisseurs de contenus distants. Une stratégie de régulation des débits de codage est alors mise en place par ces fournisseurs, de manière à réguler le niveau en bits ou en image des tampons. La stabilité de ce système de régulation couplé est étudiée en détails. Enfin, l’optimisation inter-couches d’une chaine de transmission de contenus multimédia scalable est considérée. Ce problème est formulé dans le contexte de la programmation dynamique. Lorsque des modèles de complexité raisonnable sont considérés et avec des caractéristiques du système bien connues, des solutions optimales peuvent être obtenues. Des techniques d’apprentissage sont mises en œuvre, lorsque le système n’est que partiellement connu, par exemple, lorsque l’état du canal de transmission parvient avec du retard à l’organe de commande.

Due to the emergence of new generation mobiles and media streaming services, data traffic on mobile networks is continuously exploding. Despite the emergence of standards such as LTE, resources still remain scarce and limited. Thus, efficiently sharing resources among broadcasters or between unicast receivers connected to the same base station is necessary. An efficient resources allocation, where a fair received video quality between users and an equal transmission delay are achieved, is targeted. To that end, the variety of the rate-distortion trade-off of multimedia content is exploited. First, a centralized joint encoding and transmission rate control of multiple programs sharing the same channel is considered. A satisfactory and a comparable video quality among the transmitted programs, with limited variations, as well as a comparable transmission delay are targeted. The problem is solved using constrained optimization tools. Second, only the bandwidth allocation control is centralized, the control of the encoding rate characteristics of each stream is carried in a distributed manner. By modeling the problem as a feedback control system, the centralized bandwidth allocation is required to feed back only the buffer level to its associated remote content provider. The equilibrium and stability issues are addressed for both bit and second buffer control. In the case of simple unicast connection, a cross-layer optimization of scalable video delivery over wireless channel is performed. The optimization problem is cast in the context of dynamic programming. When low complex model are considered and when the system characteristics are known, optimal solutions can be obtained. When the system is partially known, for example, when the state of the channel reaches the control process with delay, learning techniques are implemented.; Le développement simultané de terminaux mobiles multimédia (smartphones, tablettes) et de réseaux d’accès offrant des débits élevés conduit à une explosion du trafic liés aux contenus multimédia. Cette croissance nécessite un partage efficace des ressources radio entre fournisseurs de contenus (dans le cas de la diffusion) ou entre récepteurs (dans le cas de services de vidéo à la demande). Cette thèse propose des outils de partage équitable des ressources en termes de qualité des contenus multimédia reçu et de délai de transmission dans les deux contextes précédents. La variété des compromis débit-distorsion des contenus multimédia est exploitée à cet effet. Dans un premier temps, une solution centralisée de contrôle conjoint du débit de codage et de transmission de plusieurs programmes transmis sur un même canal est considérée. L’objectif est de fournir des flux de qualités similaires avec des variations limitées, tout en assurant des délais de transmission comparables. Ce problème est résolu en synthétisant une commande prédictive à l’aide d’outils d’optimisation sous contrainte. Dans un second temps, seule l’allocation de bande est centralisée, le contrôle des caractéristiques de compression de chaque flux est réalisé de manière distribuée. Le contrôleur centralisé ne renvoie que le niveau de remplissage des tampons associés à chaque flux aux fournisseurs de contenus distants. Une stratégie de régulation des débits de codage est alors mise en place par ces fournisseurs, de manière à réguler le niveau en bits ou en image des tampons. La stabilité de ce système de régulation couplé est étudiée en détails. Enfin, l’optimisation inter-couches d’une chaine de transmission de contenus multimédia scalable est considérée. Ce problème est formulé dans le contexte de la programmation dynamique. Lorsque des modèles de complexité raisonnable sont considérés et avec des caractéristiques du système bien connues, des solutions optimales peuvent être obtenues. Des techniques d’apprentissage sont mises en œuvre, lorsque le système n’est que partiellement connu, par exemple, lorsque l’état du canal de transmission parvient avec du retard à l’organe de commande.

This thesis is divided into two parts that may be read independently. The first part is about the mathematical modelling of liquidity risk. The aspect of illiquidity studied here is the constraint on the trading dates, meaning that in opposition to the classical models where investors may trade continuously, we assume that trading is only possible at discrete random times. We then use optimal control techniques (dynamic programming and Hamilton-Jacobi-Bellman equations) to identify the value functions and optimal investment strategies under these constraints. The first chapter focuses on a utility maximisation problem in finite horizon, in a framework inspired by energy markets. In the second chapter we study an illiquid market with regime-switching, and in the third chapter we consider a market in which the agent has the possibility to invest in a liquid asset and an illiquid asset which are correlated. In the second part we present probabilistic quantization methods to solve numerically an optimal switching problem. We first consider a discrete time approximation of our problem and prove a convergence rate. Then we propose two numerical quantization methods : a markovian approach where we quantize the gaussian in the Euler scheme, and, in the case where the underlying diffusion is not controlled, a marginal quantization approach inspired by numerical methods for the optimal stopping problem., Cette thèse est constituée de deux parties pouvant être lues indépendamment. Dans la première partie on s'intéresse à la modélisation mathématique du risque de liquidité. L'aspect étudié ici est la contrainte sur les dates des transactions, c'est-à-dire que contrairement aux modèles classiques où les investisseurs peuvent échanger les actifs en continu, on suppose que les transactions sont uniquement possibles à des dates aléatoires discrètes. On utilise alors des techniques de contrôle optimal (programmation dynamique, équations d'Hamilton-Jacobi-Bellman) pour identifier les fonctions valeur et les stratégies d'investissement optimales sous ces contraintes. Le premier chapitre étudie un problème de maximisation d'utilité en horizon fini, dans un cadre inspiré des marchés de l'énergie. Dans le deuxième chapitre on considère un marché illiquide à changements de régime, et enfin dans le troisième chapitre on étudie un marché où l'agent a la possibilité d'investir à la fois dans un actif liquide et un actif illiquide, ces derniers étant corrélés. Dans la deuxième partie on présente des méthodes probabilistes de quantification pour résoudre numériquement un problème de switching optimal. On considère d'abord une approximation en temps discret du problème et on prouve un taux de convergence. Ensuite on propose deux méthodes numériques de quantification : une approche markovienne où on quantifie la loi normale dans le schéma d'Euler, et dans le cas où la diffusion n'est pas contrôlée, une approche de quantification marginale inspirée de méthodes numériques pour le problème d'arrêt optimal.

Energy management of a hybrid vehicle is to develop a strategy that determines at each time the distribution flow of thermal and electricity energy that minimizes the overall consumption of the vehicle. The modelling of hybrid vehicles consumption enables to study energy management as a dynamic optimization problems under evolution constraints. The optimal solution is found when all the driving conditions are known a priori. The optimal control provides a benchmark and is used to assess the performance of embedded strategies. Two strategies based on the optimal optimization theory were created : one predictive, which has been tested on a numerical simulator and another one, based on the dual problem principle, which was successfully embedded on two conventional hybrids vehicles. For plug-in hybrids, their electrical energy capacity and their ability to be recharged from the grid relaxes some constraints on the energy optimization problem. Therefore, in order to minimize the overall emissions of the vehicle, a new strategy was developed to make the most of embedded electric energy. For all hybrid vehicles, the battery is the keystone component, whose aging alters its profitability and energy efficiency. Thus, in order to provide an accurate internal temperature of cells, an observer was designed. This information has been used by a specific strategy which optimizes consumption while preserving the battery from extreme temperatures that are prejudicial to its longevity., La gestion d'énergie d'un véhicule hybride consiste à développer une stratégie, qui détermine à chaque instant la répartition des flux d'énergie thermique et électrique, minimisant la consommation globale du véhicule. La modélisation de la consommation du véhicule hybride permet d'écrire cette problématique sous la forme d'un problème d'optimisation dynamique sous contraintes d'évolutions. Ce problème est résolu de façon optimale lorsque l'ensemble des conditions de roulage sont connues à priori. La commande optimale obtenue sert de référence pour évaluer la performance des stratégies embarquées dans le véhicule. En s'appuyant sur la théorie de l'optimisation optimale, deux stratégies ont été crées : l'une prédictive qui a été testée sur un simulateur numérique et une autre, reposant sur le principe du problème dual, qui a été embarqué avec succès sur deux véhicules hybrides conventionnels. Pour les hybrides rechargeables, leur capacité énergétique et la possibilité de se recharger sur le réseau électrique libère des contraintes dans la problématique d'optimisation énergétique. C'est pourquoi, une nouvelle stratégie spécifique a été développée dans l'objectif de profiter au maximum de l'énergie électrique embarquée pour minimiser les émissions du véhicule. Pour l'ensemble des véhicules hybrides, la batterie est un composant clef dont le vieillissement vient modifier sa rentabilité économique et énergétique. C'est pourquoi un observateur a été conçu pour fournir une information précise de la température interne des cellules. Cette information est utilisée par une stratégie spécifique optimisant la consommation tout en préservant la batterie des températures extrêmes, nuisibles à sa longévité.

Mass spectrometry is a general method used in proteomics to identify unknown proteins in a sample. The mass spectrometer measures the masses of several protein's fragments and provide spectra. A spectrum is a series of peaks that indicate the presence of those fragments. By studying these spectra, we aim at retrieving the analyzed protein in a reference databank. In this thesis, we propose a new method to study these spectra. However, our solution must be able to work on proteins coming from unsequenced species, which means that we can't find exactly the same proteins in the databank, only similar ones. At first, we propose a new spectra comparison algorithm: PacketSpectralAlignment. This algorithm allows to compare experimental spectra produced by a mass spectrometer to spectra created from the reference databank data in presence of modifications. This comparison allows to associate to each spectrum, a peptide from the databank. Then, we explain several preprocessing and filtering methods that enhance the results of our new algorithm. All of those methods are used in the SIFpackets framework. Finally, we validate PacketSpectralAlignment and SIFpackets results using several experimental datasets.; La spectrométrie de masse est une technique utilisée en protéomique pour identifier des protéines inconnues dans un échantillon. Le spectromètre mesure la masse de fragments de la protéine et fournit ainsi des spectres expérimentaux qui sont des représentations, sous forme de séries de pics, de la présence de ces différents fragments. En étudiant ces spectres, nous espérons pouvoir identifier la protéine d'origine en la retrouvant dans une banque. L'objectif de cette thèse est de proposer de nouvelles méthodes permettant d'étudier ces spectres. Cependant, ces méthodes doivent fonctionner sur des organismes non séquencés. Dans ce cas particulier, nous ne retrouverons pas exactement ces protéines dans la banque, mais uniquement des protéines qui y ressemblent. Nous proposons tout d'abord un nouvel algorithme dit de comparaison de spectres : PacketSpectralAlignment. Cet algorithme permet de comparer des spectres expérimentaux à des spectres créés à partir des données contenues dans la banque, et ce, même en présence de modifications. Cette comparaison permet l'association de chacun des spectres à un peptide de cette banque. Ensuite, nous détaillerons différents prétraitements et filtrages permettant d'améliorer l'exploitation de notre nouvel algorithme. Tous ces éléments sont intégrés dans une plate-forme intitulé SIFpackets. Enfin, nous validons les résultats de PacketSpectralAlignment ainsi que de SIFpackets sur différents jeux de données réelles.

International audience; Dans le cadre de la modélisation du dialogue, nous présentons une méthode générique permettant l'alignement de motifs approchés en deux dimensions appliquée à des matrices d'annotations codant des dialogues. L'approche utilisée, basée sur un algorithme de programmation dynamique et une mesure de similarité, permet l'identification de motifs similaires à un motif de référence. Ce procédé a été mis en pratique par la recherche de motifs récurrents dans des annotations de dialogues entre parents et enfants, lors de la narration d'histoires enfantines. Les motifs de référence utilisés sont issus d'un précédent travail [12]. Nous présentons brièvement quelques exemples d'alignements obtenus à partir d'un motif.

The aim of this work is to benefit from the potential of the cooperative driving in order to optimize the traffic throughput at isolated intersections. To achieve this objective, we have proposed a new traffic control system for isolated intersections: Cooperative Vehicle-Actuation Signalization (CVAS). The concept of this new system is based on the assumption of the ability of exchanging information between each vehicle and the surrounding vehicles or the nearby infrastructure.The system allows more precise control of the traffic since it determines the right-of-way of each vehicle according to its corresponding data sent by the embedded wireless device. The right-of-way is displayed to the driver by means of the onboard signalization. The control system determines the sequence of the vehicles to be directed through the intersection. For the sake of benefiting the improvement brought by the new system, we face several challenges. On the one hand, we are confronted with the absence of a mathematical model to address the control problem. On the other hand, despite the fact that the optimal passing sequence of vehicles can be found by the simple enumeration of all feasible sequences, the exhaustive search does not fulfill the requirements of the real-time application. To overcome these two problems, we seek help from the P-timed Petri nets. This mathematical modeling tool is able to describe the events observed by the position markers in the form of mathematical equations. Two different objectives of the control have been derived from the Little's formula. The first one aims to minimize the maximum exit time of vehicles present in the intersection. An algorithm of dynamic programming and two heuristics have been proposed to achieve this objective. The first heuristic is based on the analysis of the properties of the control problem. The second heuristic is based on the analogy between the dealt problem and the problem of Traveling Salesman Problem, which can be solved successfully by the algorithm of ant colony system. The second objective of the control is to instantly minimize the queue length. A protocol of relaying the right of way has been determined from the assumption of a Petri net that operates at its maximum speed. This simple protocol of control can be extended to all possible layouts of the isolated intersections by using the technique of “mapping”.In this work, a microscopic model (car-following model) is used to simulate the driving behavior. The simulations show that the CVAS system outperforms the other systems which are popularly used at present. It is even better than some innovative systems based on the technology of the cooperative driving. The good results encouraged us to replicate the system under real conditions through a prototype of NXT robots. The tests of this prototype prove the feasibility of the system at least for industrial applications., L’objectif de ce travail est d’exploiter les potentialités offertes par la conduite coopérative afin de fluidifier le trafic au niveau des intersections isolées. Pour ce faire, nous avons proposé un nouveau système de régulation au sein des intersections en s’inspirant du principe de l’intersection autonome. Nous avons appelé notre système : SVAC (système du véhicule-actionneur coopératif). Il repose sur la possibilité des échanges d’information entre le véhicule et son environnement de conduite.Le SVAC permet une régulation plus précise du trafic puisqu’il se base sur les requêtes de droit de passage envoyées par les véhicules réellement présents dans l’intersection. En outre, grâce à la signalisation à bord, la régulation consiste à définir les séquences de passage des véhicules, ce qui permet de personnaliser la signalisation. Le gain de précision soulève plusieurs obstacles. D’une part, nous nous heurtons systématiquement à l’absence de modèles mathématiques permettant d’aborder le problème. D’autre part, la simple énumération des séquences implique une explosion combinatoire, ce qui ne convient pas à l’application temps-réelle de la régulation des intersections. Pour s’affranchir des deux problématiques nous avons utilisé les réseaux de Petri P-temporisés. Le modèle nous a permis de décrire sous la forme d’équations mathématiques les compteurs des différents évènements observés par les véhicules. Deux objectifs de régulation ont été dégagés après avoir déduit le temps moyen d’attente basé sur la formule de Little. Le premier consiste à vider les intersections au plus tôt. Nous avons proposé un algorithme de programmation dynamique et deux heuristiques. La première heuristique est directement issue de l’analyse des propriétés du problème posé. La deuxième est basée sur l’algorithme de colonies de fourmis. En effet, le problème défini est un cas particulier du problème du voyageur de commerce. Le deuxième objectif de régulation consiste à minimiser instantanément la longueur de la file d’attente. Dans ce cadre, nous avons supposé le fonctionnement à vitesse maximale du réseau de Petri. L’utilisation des contraintes sur les ressources nous a permis de définir des règles simples de régulation en utilisant le mapping.Dans ce mémoire, nous avons utilisé la simulation microscopique basée sur les lois de poursuite pour s’approcher du comportement de conduite. La simulation a servi pour la comparaison des différentes approches proposées dans ce mémoire avec les régulateurs adaptatifs et les intersections autonomes. Dans tous les cas notre approche se distingue par un gain de capacité, ce qui nous a encouragé de reproduire le SVAC à travers un prototype de robots. Cette maquette montre la faisabilité du système au moins pour des applications industrielles.

The aim of this work is to benefit from the potential of the cooperative driving in order to optimize the traffic throughput at isolated intersections. To achieve this objective, we have proposed a new traffic control system for isolated intersections: Cooperative Vehicle-Actuation Signalization (CVAS). The concept of this new system is based on the assumption of the ability of exchanging information between each vehicle and the surrounding vehicles or the nearby infrastructure.The system allows more precise control of the traffic since it determines the right-of-way of each vehicle according to its corresponding data sent by the embedded wireless device. The right-of-way is displayed to the driver by means of the onboard signalization. The control system determines the sequence of the vehicles to be directed through the intersection. For the sake of benefiting the improvement brought by the new system, we face several challenges. On the one hand, we are confronted with the absence of a mathematical model to address the control problem. On the other hand, despite the fact that the optimal passing sequence of vehicles can be found by the simple enumeration of all feasible sequences, the exhaustive search does not fulfill the requirements of the real-time application. To overcome these two problems, we seek help from the P-timed Petri nets. This mathematical modeling tool is able to describe the events observed by the position markers in the form of mathematical equations. Two different objectives of the control have been derived from the Little's formula. The first one aims to minimize the maximum exit time of vehicles present in the intersection. An algorithm of dynamic programming and two heuristics have been proposed to achieve this objective. The first heuristic is based on the analysis of the properties of the control problem. The second heuristic is based on the analogy between the dealt problem and the problem of Traveling Salesman Problem, which can be solved successfully by the algorithm of ant colony system. The second objective of the control is to instantly minimize the queue length. A protocol of relaying the right of way has been determined from the assumption of a Petri net that operates at its maximum speed. This simple protocol of control can be extended to all possible layouts of the isolated intersections by using the technique of “mapping”.In this work, a microscopic model (car-following model) is used to simulate the driving behavior. The simulations show that the CVAS system outperforms the other systems which are popularly used at present. It is even better than some innovative systems based on the technology of the cooperative driving. The good results encouraged us to replicate the system under real conditions through a prototype of NXT robots. The tests of this prototype prove the feasibility of the system at least for industrial applications., L’objectif de ce travail est d’exploiter les potentialités offertes par la conduite coopérative afin de fluidifier le trafic au niveau des intersections isolées. Pour ce faire, nous avons proposé un nouveau système de régulation au sein des intersections en s’inspirant du principe de l’intersection autonome. Nous avons appelé notre système : SVAC (système du véhicule-actionneur coopératif). Il repose sur la possibilité des échanges d’information entre le véhicule et son environnement de conduite.Le SVAC permet une régulation plus précise du trafic puisqu’il se base sur les requêtes de droit de passage envoyées par les véhicules réellement présents dans l’intersection. En outre, grâce à la signalisation à bord, la régulation consiste à définir les séquences de passage des véhicules, ce qui permet de personnaliser la signalisation. Le gain de précision soulève plusieurs obstacles. D’une part, nous nous heurtons systématiquement à l’absence de modèles mathématiques permettant d’aborder le problème. D’autre part, la simple énumération des séquences implique une explosion combinatoire, ce qui ne convient pas à l’application temps-réelle de la régulation des intersections. Pour s’affranchir des deux problématiques nous avons utilisé les réseaux de Petri P-temporisés. Le modèle nous a permis de décrire sous la forme d’équations mathématiques les compteurs des différents évènements observés par les véhicules. Deux objectifs de régulation ont été dégagés après avoir déduit le temps moyen d’attente basé sur la formule de Little. Le premier consiste à vider les intersections au plus tôt. Nous avons proposé un algorithme de programmation dynamique et deux heuristiques. La première heuristique est directement issue de l’analyse des propriétés du problème posé. La deuxième est basée sur l’algorithme de colonies de fourmis. En effet, le problème défini est un cas particulier du problème du voyageur de commerce. Le deuxième objectif de régulation consiste à minimiser instantanément la longueur de la file d’attente. Dans ce cadre, nous avons supposé le fonctionnement à vitesse maximale du réseau de Petri. L’utilisation des contraintes sur les ressources nous a permis de définir des règles simples de régulation en utilisant le mapping.Dans ce mémoire, nous avons utilisé la simulation microscopique basée sur les lois de poursuite pour s’approcher du comportement de conduite. La simulation a servi pour la comparaison des différentes approches proposées dans ce mémoire avec les régulateurs adaptatifs et les intersections autonomes. Dans tous les cas notre approche se distingue par un gain de capacité, ce qui nous a encouragé de reproduire le SVAC à travers un prototype de robots. Cette maquette montre la faisabilité du système au moins pour des applications industrielles.

With more than 1000 complete genomes available (among which, the vast majority come from bacteria), comparative genomic analysis become essential for the functional annotation of genomes, the understanding of their structure and evolution and have applications in phylogenomics or vaccine design. One of the main approaches for comparing genomes is by aligning their DNA sequences, i.e. whole genome alignment (WGA), which means identifying the similarity regions without any prior annotation knowledge. Despite the significant improvements during the last years, reliable tools for WGA and methodology for estimating its quality, in particular for bacterial genomes, still need to be designed. Besides their extremely large lengths that make classical dynamic programming alignment methods unsuitable, aligning whole genomes involves several additional difficulties, due to the mechanisms through which genomes evolve: the divergence, which let sequence similarity vanish over time, the re- ordering of genomic segments (rearrangements), or the acquisition of external genetic material generating regions that are unalignable between sequences, e.g. horizontal gene transfer, phages. Therefore, whole genome alignment tools implement heuristics, among which the most common is the anchor based strategy. It starts by detecting an initial set of similarity regions (phase 1), and, through a chaining phase (phase 2), selects a non-overlapping maximum-weighted, usually collinear, subset of those similarities, called anchors. Phases 1 and 2 are recursively applied on yet unaligned regions (phase 3). The last phase (phase 4) consists in systematically applying classical alignment tools to all short regions still left unaligned.This thesis addresses several problems related to whole genome alignment: the evaluation of the quality of results given by WGA tools and the improvement of the classical anchor based strategy. We first designed a protocol for evaluating the quality of alignment results, based on both computational and biological measures. An evaluation of the results given by two state of the art WGA tools on pairs of intra-species bacterial genomes revealed their shortcomings: the failure of detecting some of the similarities between sequences and the misalignment of some regions. Based on these results, which imply a lack in both sensitivity and specificity, we propose a novel, pair- wise whole genome alignment tool, YOC, implementing a simplified two-phase version of the anchor strategy. In phase 1, YOC improves sensitivity by using as anchors, for the first time, local similarities based on spaced seeds that are capable of detecting larger similarity regions in divergent sequences. This phase is followed by a chaining method adapted to local similarities, a novel type of collinear chaining, allowing for proportional overlaps. We give a formulation for this novel problem and provide the first algorithm for it. The algorithm, implementing a dynamic programming approach based on the sweep-line paradigm, is exact and runs in quadratic time. We show that, compared to classical collinear chaining, chaining with overlaps improves on real bacterial data, while remaining almost as efficient in practice. Our novel tool, YOC, is evaluated together with other four WGA tools on a dataset composed of 694 pairs of intra-species bacterial genomes. The results show that YOC improves on divergent cases by detecting more distant similarities and by avoiding misaligned regions. In conclusion, YOC should be easier to apply automatically and systematically to in- coming genomes, for it does not require a post-filtering step to detect misalignment and is less complex to calibrate.; Avec plus de 1000 génomes complets disponibles (la grande majorité venant de bactéries), les analyses comparatives de génomes deviennent indispensables pour leur annotation fonctionnelle, ainsi que pour la compréhension de leur structure et leur évolution, et s’appliquent par exemple en phylogénomique ou au design des vaccins. L’une des approches les plus utilisées pour comparer des génomes est l’alignement de leurs séquences d’ADN, i.e. alignement de génomes complets, c’est-à-dire identifier les régions de similarité en s’affranchissant de toute annotation. Malgré des améliorations significatives durant les dernières années, des outils performants pour cette approche ainsi que des méthodes pour l’estimation de la qualité des résultats qu’elle produit, en particulier sur les génomes bactériens, restent encore à développer. Outre leurs grandes tailles qui rendent les solutions classiques basées sur la programmation dynamique inutilisables, l’alignement de génomes complets pose des difficultés supplémentaires dues à des mécanismes d’évolution particuliers: la divergence, qui estompe les similarités entre les séquences, le réordonnancent des portions génomiques (réarrangements), ou l’acquisition de matériel génétique extérieur, qui produit des régions non alignables entres les séquences, e.g. transfert horizontal des gènes, phages. En conséquence, les solutions pour l’alignement de génomes sont des heuristiques, dont la plus commune est la stratégie basée sur des ancres. Cette stratégie commence par identifier un ensemble initial de régions de similarité (phase 1). Ensuite une phase de chaînage sélectionne un sous-ensemble (non-chevauchantes et généralement colinéaires) de ces similarités de poids maximal, nommées ancres (phase 2). Les phases 1 et 2 sont appliquées de manière récursive sur les régions encore non-alignées (phase 3). La dernière phase consiste en l’application systématique des outils d’alignement classiques sur toutes les régions courtes qui n’ont pas encore été alignées.Cette thèse traite plusieurs problèmes liés à l’alignement de génomes complets dont: l’évaluation de la qualité des résultats produits par les outils d’alignement et l’amélioration de la stratégie basée sur des ancres. Premièrement, nous avons créé un protocole pour évaluer la qualité des résultats d’alignement, comprenant des mesures de calcul quantitatives et qualitatives, dont certaines basées sur des connaissances biologiques. Une analyse de la qualité des alignements produits par deux des principaux outils existants sur des paires de génomes bactériens intra-espèces révèle leurs limitations: des similarités non détectées et des portions d’alignement incorrectes. À partir de ces résultats, qui suggèrent un manque de sensibilité et spécificité, nous pro- posons un nouvel outil pour l’alignement deux à deux de génomes complets, YOC, qui implémente une version simplifiée de la stratégie basée sur des ancres, contenant seulement deux phases. Dans la phase 1, YOC améliore la sensibilité en utilisant comme ancres, pour la première fois dans cette stratégie, des similarités locales basées sur des graines espacées, capables de détecter des similarités plus longues dans des régions plus divergentes. Cette phase est suivie par une méthode de chainage adaptée aux similarités locales, un nouveau type de chaînage colinéaire, permettant des chevauchements proportionnels. Nous avons donné une formulation de ce nouveau problème et réalisé un premier algorithme. L’algorithme, qui adopte une approche de programmation dynamique basée sur le paradigme de la “sweep-line”, donne une solution optimale, i.e. est exacte, et s’exécute en temps quadratique. Nous avons montré que cet algorithme, comparé au chainage colinéaire classique, améliore les résultats sur des génomes bactériens, tout en restant aussi efficace en pratique. Notre nouvel outil, YOC, a été évalué ensemble avec quatre autres outils d’alignement sur un en- semble de données composé de 694 couples de génomes bactériens intra-espèces. Les résultats montrent que YOC améliore les cas divergents en détectant des similarités plus distantes et en évitant les régions mal alignées. En conclusion, YOC semble être plus facile à appliquer de manière automatique et systématique, parce qu’il nécessite pas un post-traitement des régions mal alignées, ni un paramétrage complexe.

Biological sequence alignment is a fundamental technique in bioinformatics, and consists of iden- tifying series of similar (conserved) characters that appear in the same order in both sequences, and eventually deducing a set of modifications (substitutions, insertions and deletions) involved in the transformation of one sequence into the other. This technique allows one to infer, based on sequence similarity, if two or more biological sequences are potentially homologous, i.e. if they share a common ancestor, thus enabling the understanding of sequence evolution. This thesis addresses sequence comparison problems in two different contexts: homology detection and high throughput DNA sequencing. The goal of this work is to develop sensitive alignment methods that provide solutions to the following two problems: i) the detection of hidden protein homologies by protein sequence comparison, when the source of the divergence are frameshift mutations, and ii) mapping short SOLiD reads (sequences of overlapping di- nucleotides encoded as colors) to a reference genome. In both cases, the same general idea is applied: to implicitly compare DNA sequences for detecting changes occurring at this level, while manipulating, in practice, other representations (protein sequences, sequences of di-nucleotide codes) that provide additional information and thus help to improve the similarity search. The aim is to design and implement exact and heuristic alignment methods, along with scoring schemes, adapted to these scenarios.; L'alignement de séquences biologiques est une technique fondamentale en bioinformatique, et consiste à identifier des séries de caractères similaires (conservés) qui apparaissent dans le même ordre dans les deux séquences, et à inférer un ensemble de modifications (substitutions, insertions et suppressions) impliquées dans la transformation d'une séquence en l'autre. Cette technique permet de déduire, sur la base de la similarité de séquence, si deux ou plusieurs séquences biologiques sont potentiellement homologues, donc si elles partagent un ancêtre commun, permettant ainsi de mieux comprendre l'évolution des séquences. Cette thèse aborde les problèmes de comparaison de séquences dans deux cadres différents: la détection d'homologies et le séquençage à haut débit. L'objectif de ce travail est de développer des méthodes d'alignement qui peuvent apporter des solutions aux deux problèmes suivants: i) la détection d'homologies cachées entre des protéines par comparaison de séquences protéiques, lorsque la source de leur divergence sont les mutations qui changent le cadre de lecture, et ii) le mapping de reads SOLiD (séquences de di-nucléotides chevauchantes codés par des couleurs) sur un génome de référence. Dans les deux cas, la même idée générale est appliquée: comparer implicitement les séquences d'ADN pour la détection de changements qui se produisent à ce niveau, en manipulant, en pratique, d'autres représentations (séquences de protéines, séquences de codes di-nucléotides) qui fournissent des informations supplémentaires et qui aident à améliorer la recherche de similarités. Le but est de concevoir et d'appliquer des méthodes exactes et heuristiques d'alignement, ainsi que des systemes de scores, adaptés à ces scénarios.

Biological sequence alignment is a fundamental technique in bioinformatics, and consists of iden- tifying series of similar (conserved) characters that appear in the same order in both sequences, and eventually deducing a set of modifications (substitutions, insertions and deletions) involved in the transformation of one sequence into the other. This technique allows one to infer, based on sequence similarity, if two or more biological sequences are potentially homologous, i.e. if they share a common ancestor, thus enabling the understanding of sequence evolution. This thesis addresses sequence comparison problems in two different contexts: homology detection and high throughput DNA sequencing. The goal of this work is to develop sensitive alignment methods that provide solutions to the following two problems: i) the detection of hidden protein homologies by protein sequence comparison, when the source of the divergence are frameshift mutations, and ii) mapping short SOLiD reads (sequences of overlapping di- nucleotides encoded as colors) to a reference genome. In both cases, the same general idea is applied: to implicitly compare DNA sequences for detecting changes occurring at this level, while manipulating, in practice, other representations (protein sequences, sequences of di-nucleotide codes) that provide additional information and thus help to improve the similarity search. The aim is to design and implement exact and heuristic alignment methods, along with scoring schemes, adapted to these scenarios.; L'alignement de séquences biologiques est une technique fondamentale en bioinformatique, et consiste à identifier des séries de caractères similaires (conservés) qui apparaissent dans le même ordre dans les deux séquences, et à inférer un ensemble de modifications (substitutions, insertions et suppressions) impliquées dans la transformation d'une séquence en l'autre. Cette technique permet de déduire, sur la base de la similarité de séquence, si deux ou plusieurs séquences biologiques sont potentiellement homologues, donc si elles partagent un ancêtre commun, permettant ainsi de mieux comprendre l'évolution des séquences. Cette thèse aborde les problèmes de comparaison de séquences dans deux cadres différents: la détection d'homologies et le séquençage à haut débit. L'objectif de ce travail est de développer des méthodes d'alignement qui peuvent apporter des solutions aux deux problèmes suivants: i) la détection d'homologies cachées entre des protéines par comparaison de séquences protéiques, lorsque la source de leur divergence sont les mutations qui changent le cadre de lecture, et ii) le mapping de reads SOLiD (séquences de di-nucléotides chevauchantes codés par des couleurs) sur un génome de référence. Dans les deux cas, la même idée générale est appliquée: comparer implicitement les séquences d'ADN pour la détection de changements qui se produisent à ce niveau, en manipulant, en pratique, d'autres représentations (séquences de protéines, séquences de codes di-nucléotides) qui fournissent des informations supplémentaires et qui aident à améliorer la recherche de similarités. Le but est de concevoir et d'appliquer des méthodes exactes et heuristiques d'alignement, ainsi que des systemes de scores, adaptés à ces scénarios.

La phylogénie moléculaire est un champ de recherche qui étudie l’histoire évolutive d’espèces à partir de séquences moléculaires issues de leurs génomes. Les progrès technologiques nous permettent désormais d’avoir facilement accès aux génomes complets d’un nombre toujours plus grand d’espèces. On parle maintenant de “phylogénomique” pour désigner les études phylogénétiques qui se basent sur l’analyse de génomes complets. Parallèlement, le nombre d’espèces étudiées augmente lui aussi très rapidement, le but en ligne de mire (même si on le sait inatteignable) étant de proposer la phylogénie de l’ensemble des êtres vivants : “l’Arbre de la Vie”. Cet objectif est avant tout un défi intellectuel qui reflète l’envie intarissable de l’homme de connaître et de comprendre le monde qui l’entoure. Mais cette connaissance, toujours meilleure, de l’Arbre de la Vie est également un outil clef pour mieux protéger ce monde fragile. En effet, la préservation des espèces est un enjeu majeur de notre siècle. La phylogénie moléculaire fournit un cadre théorique permettant une définition formelle de la notion, souvent floue, de biodiversité. L’obtention d’un Arbre de la Vie (même partiel) est donc un outil précieux qui permet de définir de manière objective les espèces (ou les zones) à protéger prioritairement. L’obtention d’alignements de séquences orthologues est l’une des premières étapes de nombreuses analyses moléculaires et phylogénétiques. La qualité de cette étape est primordiale et conditionne, en partie, la validité des résultats obtenus ultérieurement sur la base de ces données. Ceci explique que nous ayons mené un effort particulier pour constituer la base de données OrthoMaM qui propose un ensemble de marqueurs phylogénétiques conservés en simple copie à l’échelle des mammifères. Nous avons également proposé un algorithme, basé sur une approche de programmation dynamique, qui permet d’aligner des séquences nucléotidiques codantes, en prenant en compte à la fois leurs traductions en acides aminés et la possibilité de changements de cadre de lecture. Sur la base d’un alignement des séquences orthologues d’un gène, on peut inférer son histoire évolutive. On utilise généralement plusieurs de ces histoires pour inférer l’arbre des espèces. Les méthodes de super-arbre permettent de combiner des phylogénies partielles (aussi appelés arbres sources) en une seule phylogénie plus large offrant une synthèse des différents arbres sources. L’une des difficultés inhérentes aux méthodes de super-arbre est l’utilisation d’arbres sources incongruents, c’est à-dire en désaccord sur la position phylogénétique de certaines espèces. Parce qu’elles permettent de combiner des arbres en une phylogénie toujours plus grande, les méthodes de super-arbre font partie des outils clefs pour assembler l’Arbre de la Vie. Nous avons formalisé deux propriétés qu’elles devraient respecter dans ce contexte. La première assure que toute information du super-arbre est présente (ou induite) par les arbres sources ; tandis que la seconde assure que le super-arbre ne contredit aucune des informations présentes (ou induites) par les arbres sources. Après avoir montré l’intérêt de ces propriétés enles comparant à d’autres, nous avons proposé une méthode de super-arbre, PhySIC_IST, qui les respecte. De plus, en introduisant un pré-traitement statistique (STC) qui élimine les résolutions minoritaires des arbres sources, nous avons généré toute une graduation de méthodes de super-arbre (STC + PhySIC_IST)qui, selon le paramètre STC utilisé, sont plus ou moins stringeantes sur les critères requis pour qu’une information soit présente dans le super-arbre. Au cours de l’évolution, il est fréquent que des gènes soient dupliqués ou perdus au sein d’un génome. Il arrive également qu’il y ait un transfert de patrimoine génétique entre deux espèces contemporaines vivant dans un même environnement. Ces évènements engendrent des différences entre l’histoire des espèces(ou arbre des espèces) et celle d’un gène les ayant subits (ou arbre de gènes). De plus, une espèce peut alors étiqueter plusieurs feuilles d’un arbre de gènes ce qui le rend inutilisable par les approches classiques de super-arbres. Nos travaux permettent d’intégrer le signal phylogénétique de tels arbres dans une analyse de type super-arbre visant à inférer l’Arbre de la Vie. Ce travail est l’un des premiers à permettre d’exploiter cette source d’information, qui est pourtant essentielle. Parallèlement nous avons développé un algorithme polynomial efficace pour inférer le scénario le plus parcimonieux (en terme de duplication, perte et transfert) permettant d’expliquer les différences entre un arbre de gènes et un arbre d’espèces. Les travaux décrits dans ce manuscrit vont de l’informatique théorique à l’étude de données biologiques en passant par le développement de logiciels et de services Web. Cependant, ils s’inscrivent tous dans une perspective à long terme qui vise à obtenir, à partir des génomes actuels, un Arbre de la Vie fiable, complet et annoté.

This thesis studies policy iteration methods with linear approximation of the value function for large state space problems in the reinforcement learning context. We first introduce a unified algorithm that generalizes the main stochastic optimal control methods. We show the convergence of this unified algorithm to the optimal value function in the tabular case, and a performance bound in the approximate case when the value function is estimated. We then extend the literature of second-order linear approximation algorithms by proposing a generalization of Least-Squares Policy Iteration (LSPI) (Lagoudakis and Parr, 2003). Our new algorithm, Least-Squares λ Policy Iteration (LSλPI), adds to LSPI an idea of λ-Policy Iteration (Bertsekas and Ioffe, 1996): the damped (or optimistic) evaluation of the value function, which allows to reduce the variance of the estimation to improve the sampling efficiency. Thus, LSλPI offers a bias-variance trade-off that may improve the estimation of the value function and the performance of the policy obtained. In a second part, we study in depth the game of Tetris, a benchmark application that several works from the literature attempt to solve. Tetris is a difficult problem because of its structure and its large state space. We provide the first full review of the literature that includes reinforcement learning works, evolutionary methods that directly explore the policy space and handwritten controllers. We observe that reinforcement learning is less successful on this problem than direct policy search approaches such as the cross-entropy method (Szita et Lőrincz, 2006). We finally show how we built a controller that outperforms the previously known best controllers, and shortly discuss how it allowed us to win the Tetris event of the 2008 Reinforcement Learning Competition.; Cette thèse s'intéresse aux méthodes d'itération sur les politiques dans l'apprentissage par renforcement à grand espace d'états avec approximation linéaire de la fonction de valeur. Nous proposons d'abord une unification des principaux algorithmes du contrôle optimal stochastique. Nous montrons la convergence de cette version unifiée vers la fonction de valeur optimale dans le cas tabulaire, ainsi qu'une garantie de performances dans le cas où la fonction de valeur est estimée de façon approximative. Nous étendons ensuite l'état de l'art des algorithmes d'approximation linéaire du second ordre en proposant une généralisation de Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Notre nouvel algorithme, Least-Squares λ Policy Iteration (LSλPI), ajoute à LSPI un concept venant de λ-Policy Iteration (Bertsekas et Ioffe, 1996) : l'évaluation amortie (ou optimiste) de la fonction de valeur, qui permet de réduire la variance de l'estimation afin d'améliorer l'efficacité de l'échantillonnage. LSλPI propose ainsi un compromis biais-variance réglable qui peut permettre d'améliorer l'estimation de la fonction de valeur et la qualité de la politique obtenue. Dans un second temps, nous nous intéressons en détail au jeu de Tetris, une application sur laquelle se sont penchés plusieurs travaux de la littérature. Tetris est un problème difficile en raison de sa structure et de son grand espace d'états. Nous proposons pour la première fois une revue complète de la littérature qui regroupe des travaux d'apprentissage par renforcement, mais aussi des techniques de type évolutionnaire qui explorent directement l'espace des politiques et des algorithmes réglés à la main. Nous constatons que les approches d'apprentissage par renforcement sont à l'heure actuelle moins performantes sur ce problème que des techniques de recherche directe de la politique telles que la méthode d'entropie croisée (Szita et Lőrincz, 2006). Nous expliquons enfin comment nous avons mis au point un joueur de Tetris qui dépasse les performances des meilleurs algorithmes connus jusqu'ici et avec lequel nous avons remporté l'épreuve de Tetris de la Reinforcement Learning Competition 2008.

This thesis studies policy iteration methods with linear approximation of the value function for large state space problems in the reinforcement learning context. We first introduce a unified algorithm that generalizes the main stochastic optimal control methods. We show the convergence of this unified algorithm to the optimal value function in the tabular case, and a performance bound in the approximate case when the value function is estimated. We then extend the literature of second-order linear approximation algorithms by proposing a generalization of Least-Squares Policy Iteration (LSPI) (Lagoudakis and Parr, 2003). Our new algorithm, Least-Squares λ Policy Iteration (LSλPI), adds to LSPI an idea of λ-Policy Iteration (Bertsekas and Ioffe, 1996): the damped (or optimistic) evaluation of the value function, which allows to reduce the variance of the estimation to improve the sampling efficiency. Thus, LSλPI offers a bias-variance trade-off that may improve the estimation of the value function and the performance of the policy obtained. In a second part, we study in depth the game of Tetris, a benchmark application that several works from the literature attempt to solve. Tetris is a difficult problem because of its structure and its large state space. We provide the first full review of the literature that includes reinforcement learning works, evolutionary methods that directly explore the policy space and handwritten controllers. We observe that reinforcement learning is less successful on this problem than direct policy search approaches such as the cross-entropy method (Szita et Lőrincz, 2006). We finally show how we built a controller that outperforms the previously known best controllers, and shortly discuss how it allowed us to win the Tetris event of the 2008 Reinforcement Learning Competition.; Cette thèse s'intéresse aux méthodes d'itération sur les politiques dans l'apprentissage par renforcement à grand espace d'états avec approximation linéaire de la fonction de valeur. Nous proposons d'abord une unification des principaux algorithmes du contrôle optimal stochastique. Nous montrons la convergence de cette version unifiée vers la fonction de valeur optimale dans le cas tabulaire, ainsi qu'une garantie de performances dans le cas où la fonction de valeur est estimée de façon approximative. Nous étendons ensuite l'état de l'art des algorithmes d'approximation linéaire du second ordre en proposant une généralisation de Least-Squares Policy Iteration (LSPI) (Lagoudakis et Parr, 2003). Notre nouvel algorithme, Least-Squares λ Policy Iteration (LSλPI), ajoute à LSPI un concept venant de λ-Policy Iteration (Bertsekas et Ioffe, 1996) : l'évaluation amortie (ou optimiste) de la fonction de valeur, qui permet de réduire la variance de l'estimation afin d'améliorer l'efficacité de l'échantillonnage. LSλPI propose ainsi un compromis biais-variance réglable qui peut permettre d'améliorer l'estimation de la fonction de valeur et la qualité de la politique obtenue. Dans un second temps, nous nous intéressons en détail au jeu de Tetris, une application sur laquelle se sont penchés plusieurs travaux de la littérature. Tetris est un problème difficile en raison de sa structure et de son grand espace d'états. Nous proposons pour la première fois une revue complète de la littérature qui regroupe des travaux d'apprentissage par renforcement, mais aussi des techniques de type évolutionnaire qui explorent directement l'espace des politiques et des algorithmes réglés à la main. Nous constatons que les approches d'apprentissage par renforcement sont à l'heure actuelle moins performantes sur ce problème que des techniques de recherche directe de la politique telles que la méthode d'entropie croisée (Szita et Lőrincz, 2006). Nous expliquons enfin comment nous avons mis au point un joueur de Tetris qui dépasse les performances des meilleurs algorithmes connus jusqu'ici et avec lequel nous avons remporté l'épreuve de Tetris de la Reinforcement Learning Competition 2008.

The growing number of video data makes often difficult, even impossible, any attemptof watching them entirely. In the context of automatic analysis of videos, a recurring request is to identify moments in the video when something unusual happens.We propose several algorithms to identify unusual events, making the hypothesis that these events have a low probability. We address several types of events, from those generates by moving areas to the trajectories of objects tracked. In the first part of the study, we build a simple tracking system. We propose several measures of similarity between trajectories. These measures give an estimate of the similarity of trajectories by taking into account both spatial and/or temporal aspects. It is possible to differentiate between objects moving on the same path, but with different speeds. Based on these measures, we build models of trajectories representing the common behavior of objects, so that we can identify those that are abnormal.We noticed that the tracking yields bad results, especially in crowd situations. Therefore, we use the optical flow vectors to build a movement model based on a codebook. This model stores the preferred movement directions for each pixel. It is possible to identify abnormal movement at pixel-level, without having to use a tracker. By using temporal coherence, we can further improve the detection rate, affected by errors of estimation of optic flow. In a second step, we change the method of construction of this model. With the new approach, we can extract higher-level features — the equivalent trajectories, but still without the notion of object tracking. In this situation, we can reuse partial trajectory analysis to detect rare events.All aspects presented in this study have been implemented. In addition, we have design some applications, like predicting the trajectories of visible objects or storing and retrieving tracked objects in a database., Le travail présenté dans cette étude se place dans le contexte de l’analyse automatique des vidéos. A cause du nombre croissant des données vidéo, il est souvent difficile, voire impossible qu’un ou plusieurs opérateurs puissent les regarder toutes. Une demande récurrente est d’identifier les moments dans la vidéo quand il y a quelque chose d’inhabituel qui se passe, c’est-à-dire la détection des événements anormaux.Nous proposons donc plusieurs algorithmes permettant d’identifier des événements inhabituels, en faisant l’hypothèse que ces événements ont une faible probabilité. Nous abordons plusieurs types d’événements, de l’analyse des zones en mouvement à l’analyse des trajectoires des objets suivis.Après avoir dédié une partie de la thèse à la construction d’un système de suivi,nous proposons plusieurs mesures de similarité entre des trajectoires. Ces mesures, basées sur DTW (Dynamic Time Warping), estiment la similarité des trajectoires prenant en compte différents aspects : spatial, mais aussi temporel, pour pouvoir - par exemple - faire la différence entre des trajectoires qui ne sont pas parcourues de la même façon (en termes de vitesse de déplacement). Ensuite, nous construisons des modèles de trajectoires, permettant de représenter les comportements habituels des objets pour pouvoir ensuite détecter ceux qui s’éloignent de la normale.Pour palier les défauts de suivi qui apparaissent dans la pratique, nous analysons lesvecteurs de flot optique et nous construisons une carte de mouvement. Cette carte modélise sous la forme d’un codebook les directions privilégiées qui apparaissent pour chaque pixel, permettant ainsi d’identifier tout déplacement anormal, sans avoir pour autant la notion d’objet suivi. En utilisant la cohérence temporelle, nous pouvons améliorer encore plus le taux de détection, affecté par les erreurs d’estimation de flot optique. Dans un deuxième temps, nous changeons la méthode de constructions de cette carte de mouvements, pour pouvoir extraire des caractéristiques de plus haut niveau — l’équivalent des trajectoires, mais toujours sans nécessiter le suivi des objets. Nous pouvons ainsi réutiliser partiellement l’analyse des trajectoires pour détecter des événements rares.Tous les aspects présentés dans cette thèse ont été implémentés et nous avons construit certaines applications, comme la prédiction des déplacements des objets ou la mémorisation et la recherche des objets suivis.

National audience; Répartissez un groupe de personnes entre deux ascenseurs, sans dépasser leur charge maximale.

National audience; Qu’est-ce que les mathématiques ont à nous dire sur le comportement des espèces vivantes ? Pierre Bernhard nous en parle dans cet épisode du podcast audio.

National audience; Des progrès spectaculaires ont été faits ces deux dernières décennies quant à l'exploration systématique et exhaustive des génomes et des protéomes (ensemble des protéines produites au sein d'un organisme). Mais l'obtention des séquences génomiques et protéiques ne constitue en fait que le début d'un long travail d'analyse dans lequel l'informatique joue un rôle fondamental. Ainsi, face à un génome nouvellement séquencé, il s'agit de répondre aux questions suivantes : Où sont localisés les gènes ? Comment sont organisées leurs régions codantes ? Quelles sont les fonctions du produit de leur expression que sont en particulier les protéines ? Comment cette expression est-elle régulée ? Les bioinformaticiens ont donc adapté ou développé des algorithmes dédiés à l'analyse des séquences biologiques, toujours plus puissants et pertinents.

This work is intended at providing resolution methods for Stochastic Optimal Control (SOC) problems. We consider a dynamical system on a discrete and finite horizon, which is influenced by exogenous noises and actions of a decision maker. The aim is to minimize a given function of the behaviour of the system over the whole time horizon. We suppose that, at every instant, the decision maker is able to make observations on the system and even to keep some in memory. Since it is generally profitable to take these observations into account in order to draw further actions, we aim at designing decision rules rather than simple decisions. Such rules map to every instant and every possible observation of the system a decision to make. The present manuscript presents three main contributions. The first is concerned with the study of scenario-based solving methods for SOC problems. We compare the use of the so-called scenario trees technique to the particle method. The first one has been widely studied among the Stochastic Programming community and has been somehow popular in applications, until recent developments showed numerically as well as theoretically that this methodology behaved poorly when the number of time steps of the problem grows. We here explain this fact in details and show that this negative feature is not to be attributed to the scenario setting, but rather to the use of a tree structure. Indeed, we show on numerical examples how the particle method, which is a newly developed variational technique also based on scenarios, behaves in a better way even when dealing with a large number of time steps. The second contribution starts from the observation that, even with particle methods, we are still facing some kind of curse of dimensionality. In other words, decision rules intrisically suffer from the dimension of their domain, that is observations (or state in the Dynamic Programming framework). For a certain class of systems, namely decomposable systems, we adapt results concerning the decomposition of large-scale systems which are well known in the deterministic case to the SOC case. The application is not straightforward and requires some statistical analysis for the dual variable, which is in our context a stochastic process. We propose an original algorithm called Dual Approximate Dynamic Programming (DADP) and study its convergence. We also apply DADP to a real-life power management problem. The third contribution is concerned with a rather structural property for SOC problems: the question of dynamic consistency for a sequence of decision making problems over time. Our aim is to establish a link between the notion of time consistency, that we loosely define in the last chapter, and the central concept of state structure within optimal control. This contribution is original in the following sense. Many works in the literature aim at finding optimization models which somehow preserve the "natural" time consistency property for the sequence of decision making problems. On the contrary, we show for a broad class of SOC problems which are not a priori time-consistent that it is possible to regain this property by simply extending the state structure of the model, 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

This PhD dissertation consists of three independent parts and deals with applications of stochastic control to finance. In the first part, we study the utility maximization problem in a market with defaults and total/partial information. The dynamic programming principle is used to characterize the value function. Given this characterization, we find a BSDE of which the value function is a solution. We also give an approximation of this value function. In the second part, we study BSDEs with jumps. We link BSDEs with jumps and Brownian BSDEs using the decomposition of processes in the reference filtration. With this link, we get a result of existence, a comparison theorem and a decomposition of Feynman-Kac formula. We use these techniques to work out the price of a European option in a complete market and the indifference price of a contingent claim in an incomplete market. Finally, in the third part, we use the error theory to explain the liquidity risk and to model the Bid-Ask spread. Then we solve an optimal liquidation problem for a large portfolio in discrete and deterministic time., Cette thèse se compose de trois parties indépendantes portant sur l'application du contrôle stochastique à la finance. Dans la première partie, nous étudions le problème de maximisation de la fonction d'utilité dans un marché incomplet avec défauts et information totale/partielle. Nous utilisons le principe de la programmation dynamique pour pouvoir caractériser la fonction valeur solution du problème. Ensuite, nous utilisons cette caractérisation pour en déduire une EDSR dont la fonction valeur est solution. Nous donnons également une approximation de cette fonction valeur. Dans la seconde partie, nous étudions les EDSR à sauts. En utilisant les résultats de décomposition des processus à sauts liée au grossissement progressif de filtration, nous faisons un lien entre les EDSR à sauts et les EDSR browniennes. Cela nous permet de donner un résultat d'existence, un théorème de comparaison ainsi qu'une décomposition de la formule de Feynman-Kac. Puis nous utilisons ces techniques pour la détermination du prix d'une option européenne dans un marché complet et le prix d'indifférence d'un actif contingent non duplicable dans un marché incomplet. Enfin, dans la troisième partie, nous utilisons la théorie des erreurs pour expliquer le risque de liquidité comme une propriété intrinsèque au marché. Cela nous permet de modéliser la fourchette Bid-Ask. Puis nous résolvons dans ce modèle le problème de liquidation optimale d'un portefeuille en temps discret et déterministe en utilisant la programmation dynamique.

This work is intended at providing resolution methods for Stochastic Optimal Control (SOC) problems. We consider a dynamical system on a discrete and finite horizon, which is influenced by exogenous noises and actions of a decision maker. The aim is to minimize a given function of the behaviour of the system over the whole time horizon. We suppose that, at every instant, the decision maker is able to make observations on the system and even to keep some in memory. Since it is generally profitable to take these observations into account in order to draw further actions, we aim at designing decision rules rather than simple decisions. Such rules map to every instant and every possible observation of the system a decision to make. The present manuscript presents three main contributions. The first is concerned with the study of scenario-based solving methods for SOC problems. We compare the use of the so-called scenario trees technique to the particle method. The first one has been widely studied among the Stochastic Programming community and has been somehow popular in applications, until recent developments showed numerically as well as theoretically that this methodology behaved poorly when the number of time steps of the problem grows. We here explain this fact in details and show that this negative feature is not to be attributed to the scenario setting, but rather to the use of a tree structure. Indeed, we show on numerical examples how the particle method, which is a newly developed variational technique also based on scenarios, behaves in a better way even when dealing with a large number of time steps. The second contribution starts from the observation that, even with particle methods, we are still facing some kind of curse of dimensionality. In other words, decision rules intrisically suffer from the dimension of their domain, that is observations (or state in the Dynamic Programming framework). For a certain class of systems, namely decomposable systems, we adapt results concerning the decomposition of large-scale systems which are well known in the deterministic case to the SOC case. The application is not straightforward and requires some statistical analysis for the dual variable, which is in our context a stochastic process. We propose an original algorithm called Dual Approximate Dynamic Programming (DADP) and study its convergence. We also apply DADP to a real-life power management problem. The third contribution is concerned with a rather structural property for SOC problems: the question of dynamic consistency for a sequence of decision making problems over time. Our aim is to establish a link between the notion of time consistency, that we loosely define in the last chapter, and the central concept of state structure within optimal control. This contribution is original in the following sense. Many works in the literature aim at finding optimization models which somehow preserve the "natural" time consistency property for the sequence of decision making problems. On the contrary, we show for a broad class of SOC problems which are not a priori time-consistent that it is possible to regain this property by simply extending the state structure of the model, 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

RÉSUMÉ. Nous présentons dans cet article une approche basée sur l'utilisation de l'Alpha- bet Phonétique International (API) pour l'indexation et la recherche par le contenu de docu- ments audiovisuels multilingues. L'approche fonctionne même si les documents contiennent des langues inconnues. Elle a été validée dans le cadre de la compétition u Star Challenge » sur les moteurs de recherche organisée par l'Agence A*STAR de Singapour. Notre approche comprend la construction d'un modèle acoustique multilingue basé sur l'API et une méthode fondée sur la programmation dynamique pour la recherche de segments de documents par u détection de chaînes API ». La programmation dynamique permet de repérer la chaîne de la requête dans la chaîne du document, même avec un taux d'erreur de transcription au niveau phonétique signifi- catif. Les méthodes que nous avons développées nous ont classés premiers et troisièmes sur les tâches de recherche monolingues (anglais), cinquièmes sur la tâche de recherche multilingue et premiers sur la tâche de recherche multimodale (audio et image).

In this thesis, we deal with the question of reliability of electricity system and particularly the problem of generation capacity adequacy in electricity markets, characterized by uncertain and volatile demand. This question is currently the object of many politics and economics debates in the European Commission of energy. It occurs within the context of deregulations and reforms of liberalization operated in western countries. This deregulation was caused many shortages and crisis in many electricity markets in the world. Failures are caused by several factors such as, the presence of uncertainties on future demand and fuel prices, the risk-averse behavior of investors and the market power exercised by existing generators. They had lead to high spot market prices and a fundamental imbalance between the steadily growing demand for power and the limited increases, due to the lack of investments, in generation capacities. Many mechanisms, additional to the energy market, that ensure an adequate incentive for investments and a stable and socially acceptable electricity prices have been proposed. In this work, we compare different investment incentive mechanisms, in terms of long-term capacity adequacy in an uncertain environment, cost effectiveness and the ability of reducing market power. In the literature, the problem of long- term system reliability has been largely studied in qualitative terms. A few works attempt to model the quantitative effects of those market designs. The contribution of this work is to propose a quantitative analysis based on dynamics models. Competition is considered by using the principles of game theory. Stochastic dynamic programming is used to deal with the stochastic environment of the market and mixed complementarity problem and variational inequality formulations are employed to find Nash equilibrium. In addition to the analytic analysis, an experimental study is carried out in order to include a larger diversity of strategy. The main finding of this thesis is that market-based mechanisms would be the most cost-efficient mechanisms for assuring long-term system adequacy, encouraging earlier and adequate new investments in the system and for reducing market power., Dans cette thèse, nous traitons la question de la fiabilité du système électrique et notamment le problème d'adéquation des capacités de production d'électricité avec une demande future, qui évolue d'une façon hautement imprévisible. Cette question suscite actuellement des débats économiques et politiques au sein de la commission européenne de l'énergie. Elle s'inscrit dans le contexte de déréglementation et de réformes de libéralisation opérées aux seins de pays occidentaux. Les défaillances qui se sont accompagnées avec cette déréglementation et qui ont provoqué diverses crises ont pour origine l'aversion aux risques des investisseurs, l'incertitude sur la demande future et les prix du carburants et le pouvoir de marché exercé pour les producteurs existants particulièrement en période de tension. Ceci a provoqué d'une part, des prix d'électricité hautement aléatoires et élevés et d'autre part, un manque d'incitations aux nouveaux investissements. Pour y faire face, plusieurs mécanismes additionnels assurant une incitation adéquate aux investissements et une maîtrise des prix d'électricité ont été proposés. Dans ce travail, on compare l'efficacité relative des mécanismes marchands d'incitation aux investissements. L'adéquation des capacités de production dans le long terme constitue le principal critère d'évaluation de ces mécanismes. Par ailleurs l'efficacité en termes de coût et de réduction des manipulations des prix dans les marchés forment deux éléments importants à prendre en considération lors de leur évaluation. Dans la littérature, ces mécanismes ont été traités d'un point de vue purement qualitatif, ce qui limite les enseignements qu'on peut tirer sur l'efficacité de chacun. L'apport de ce travail est de proposer une analyse conduite dans le cadre d'un modèle dynamique numérique. La dimension concurrentielle est prise en compte en mobilisant la théorie des jeux. La résolution du modèle fait appel à la méthode de la programmation dynamique et aux méthodes de problème de complémentarité et de l'inégalité variationnelle. En complément à l'analyse théorique, une étude expérimentale est conduite afin d'intégrer une plus grande diversité de stratégie. Nous concluons de ces recherches que la mise en place d'un mécanisme marchand d'incitation aux investissements est prometteuse. Il permet d'assurer l'adéquation future du système électrique à faible coût et de lutter efficacement contre le problème de pouvoir de marché.

In this thesis, we propose new methods hybridizing dynamic programming and integer programming exact methods to solve bilevel knapsack problems. The numerical experiments show that our algorithms are robust and surpass significantly the algorithms of the literature. Iterative hybrid heuristics based on relaxations are designed for solving multiple-choice multidimensional knapsack problem. These heuristics converge theoretically towards an optimal solution of the problem by solving a series of sub problems of small size produced by exploiting the information of relaxations. Our methods are enriched by using fixation and by the addition of cuts and pseudo-cuts induced by local search and relaxations. These added constraints are used to reduce the search space. The results show that the heuristics converge quickly to good solutions and provide 13 new better values from 33 instances of the literature. Lastly, an oscillation strategy combining the mathematical programming and constructive and destructive heuristics is proposed to solve a real problem for the management of disruptions in the air industry. Our approach was ranked second of an international challenge.; Cette thèse porte sur l’étude de variantes du problème de sac à dos. Nous étudions d’abord des problèmes de sac à dos bi-niveaux pour lesquels nous proposons de nouvelles méthodes hybridant programmation dynamique et méthode de séparations et évaluations. Les expériences numériques montrent que les algorithmes présentés sont robustes et surpassent significativement les algorithmes de la littérature. Des heuristiques itératives hybrides basées sur des relaxations sont également conçues pour le problème du sac à dos multidimensionnel à choix multiples. Ce sont des variantes d’un schéma itératif qui convergent théoriquement vers une solution optimale du problème en résolvant une série de sous-problèmes de petite taille produits en exploitant l’information de relaxations. Nos méthodes sont enrichies par des techniques de fixation et l’ajout de coupes et pseudo-coupes induites par la recherche locale et les relaxations pour réduire l’espace de recherche. Les résultats montrent que ces heuristiques convergent rapidement vers des solutions élites et fournissent 13 nouvelles meilleures valeurs sur un ensemble de 33 instances de la littérature. Enfin, une stratégie d’oscillation combinant la programmation mathématique et des heuristiques constructives et destructives est proposée dans le but de résoudre un problème réel pour la gestion de perturbations dans le domaine aérien. Notre approche a été classée seconde d’un challenge international.

The work done during this thesis contributes to the intensive penetration of the photovoltaic electricity production into the electric grid. Photovoltaic energy holds an immense potential, in particular in the housing sector, but intermittent nature limits its large scale development. In this thesis, we propose to add a storage element to the grid connected photovoltaic system (housing application). First, we introduce the notion of energy management in these systems called « hybrids systems ». The objective is to reduce the peak power consumption and production. Next, we propose and study optimized energy strategies based on predictive indications of irradiation, ambient temperature, power consumption and electricity grid prices. Finally, we bring theoretical solutions to the real time energy management, notably by proposing a solution to the problem of prediction uncertainty., Ces travaux de thèse constituent une contribution à l'introduction massive de la production photovoltaïque (PV) sur le réseau électrique. L'énergie PV possède un potentiel immense, notamment dans le secteur de l'habitat, mais l'effet d'intermittence limite son développement à grande échelle. Dans cette thèse nous proposons d'ajouter un élément de stockage aux systèmes photovoltaïques connectés au réseau dans l'habitat. Nous commençons par introduire la notion de gestion d'énergie dans ces systèmes dits « hybrides », dont l'objectif qui a été fixé est de réduire les pics de puissance appelée, voire produite. Ensuite, nous proposons et étudions des stratégies de gestion optimisées d'énergie basées sur des données prévisionnelles d'irradiations, de températures ambiante, de consommation et des prix de l'énergie. Enfin, nous apportons des solutions théoriques originales de gestion en temps réel, notamment en introduisant des réponses au problème des incertitudes sur les prévisions.

The work done during this thesis contributes to the intensive penetration of the photovoltaic electricity production into the electric grid. Photovoltaic energy holds an immense potential, in particular in the housing sector, but intermittent nature limits its large scale development. In this thesis, we propose to add a storage element to the grid connected photovoltaic system (housing application). First, we introduce the notion of energy management in these systems called « hybrids systems ». The objective is to reduce the peak power consumption and production. Next, we propose and study optimized energy strategies based on predictive indications of irradiation, ambient temperature, power consumption and electricity grid prices. Finally, we bring theoretical solutions to the real time energy management, notably by proposing a solution to the problem of prediction uncertainty.; Ces travaux de thèse constituent une contribution à l'introduction massive de la production photovoltaïque (PV) sur le réseau électrique. L'énergie PV possède un potentiel immense, notamment dans le secteur de l'habitat, mais l'effet d'intermittence limite son développement à grande échelle. Dans cette thèse nous proposons d'ajouter un élément de stockage aux systèmes photovoltaïques connectés au réseau dans l'habitat. Nous commençons par introduire la notion de gestion d'énergie dans ces systèmes dits « hybrides », dont l'objectif qui a été fixé est de réduire les pics de puissance appelée, voire produite. Ensuite, nous proposons et étudions des stratégies de gestion optimisées d'énergie basées sur des données prévisionnelles d'irradiations, de températures ambiante, de consommation et des prix de l'énergie. Enfin, nous apportons des solutions théoriques originales de gestion en temps réel, notamment en introduisant des réponses au problème des incertitudes sur les prévisions.

National audience; Dans le cadre du contrôle optimal stochastique, nous proposons une manière modifiée de mettre en oeuvre l'algorithme λ-Policy Iteration (Bertsekas & Tsitsiklis, 1996), une méthode qui généralise Value Iteration et Policy Iteration en introduisant un paramètre λ. Nous montrons que cette version modifiée, qui est analogue à Modified Policy Iteration, généralise tous ces algorithmes et converge vers la fonction de valeur optimale. En nous appuyant sur des arguments analytiques et expérimentaux, nous mettons en évidence le fait que lorsque l'algorithme est appliqué de manière exacte, le paramètre λ ne permet pas d'améliorer la vitesse de convergence de manière significative.

National audience; Nous proposons une approche heuristique pour calculer une politique approchée d'un Dec-POMDP. Il s'agit d'une approche par programmation dynamique à base de points dans la lignée des algorithmes PBDP \citep{szer2006a}, MBDP \citep{seuken2007a} et IMBDP \citep{seuken2007b} : Elle formule le choix des politiques retenues à chaque étape de la construction comme un problème d'optimisation. Le critère de ce problème repose sur une estimation de la distribution de probabilité {\em a priori} des croyances atteignables pour un horizon donné : Il s'agit de maximiser l'espérance des récompenses cumulées pour l'horizon considéré étant donné cette distribution. L'estimation de cette espérance peut se faire par échantillonnage des croyances en simulant une politique heuristique.

Rappel des fonctions de l'hybridation / Position du problème de la gestion de l'énergie / Méthode de la programmation dynamique / Méthode du calcul variationnel / Eléments pour un dimensionnement optimal /Applications en ligne : RN ou l-control

Handwriting recognition is one of the leading applications of pattern recognition and machine learning. Despite having some limitations, handwriting recognition systems have been used as an input method of many electronic devices and helps in the automation of many manual tasks requiring processing of handwriting images. In general, a handwriting recognition system comprises three functional components; preprocessing, recognition and post-processing. There have been improvements made within each component in the system. However, to further open the avenues of expanding its applications, specific improvements need to be made in the recognition capability of the system. Hidden Markov Model (HMM) has been the dominant methods of recognition in handwriting recognition in offline and online systems. However, the use of Gaussian observation densities in HMM and representational model for word modeling often does not lead to good classification. Hybrid of Neural Network (NN) and HMM later improves word recognition by taking advantage of NN discriminative property and HMM representational capability. However, the use of NN does not optimize recognition capability as the use of Empirical Risk minimization (ERM) principle in its training leads to poor generalization. In this thesis, we focus on improving the recognition capability of a cursive online handwritten word recognition system by using an emerging method in machine learning, the support vector machine (SVM). We first evaluated SVM in isolated character recognition environment using IRONOFF and UNIPEN character databases. SVM, by its use of principle of structural risk minimization (SRM) have allowed simultaneous optimization of representational and discriminative capability of the character recognizer. We finally demonstrate the various practical issues in using SVM within a hybrid setting with HMM. In addition, we tested the hybrid system on the IRONOFF word database and obtained favourable results.; Nos travaux concernent la reconnaissance de l'écriture manuscrite qui est l'un des domaines de prédilection pour la reconnaissance des formes et les algorithmes d'apprentissage. Dans le domaine de l'écriture en-ligne, les applications concernent tous les dispositifs de saisie permettant à un usager de communiquer de façon transparente avec les systèmes d'information. Dans ce cadre, nos travaux apportent une contribution pour proposer une nouvelle architecture de reconnaissance de mots manuscrits sans contrainte de style. Celle-ci se situe dans la famille des approches hybrides locale/globale où le paradigme de la segmentation/reconnaissance va se trouver résolu par la complémentarité d'un système de reconnaissance de type discriminant agissant au niveau caractère et d'un système par approche modèle pour superviser le niveau global. Nos choix se sont portés sur des Séparateurs à Vastes Marges (SVM) pour le classifieur de caractères et sur des algorithmes de programmation dynamique, issus d'une modélisation par Modèles de Markov Cachés (HMM). Cette combinaison SVM/HMM est unique dans le domaine de la reconnaissance de l'écriture manuscrite. Des expérimentations ont été menées, d'abord dans un cadre de reconnaissance de caractères isolés puis sur la base IRONOFF de mots cursifs. Elles ont montré la supériorité des approches SVM par rapport aux solutions à bases de réseaux de neurones à convolutions (Time Delay Neural Network) que nous avions développées précédemment, et leur bon comportement en situation de reconnaissance de mots.

Handwriting recognition is one of the leading applications of pattern recognition and machine learning. Despite having some limitations, handwriting recognition systems have been used as an input method of many electronic devices and helps in the automation of many manual tasks requiring processing of handwriting images. In general, a handwriting recognition system comprises three functional components; preprocessing, recognition and post-processing. There have been improvements made within each component in the system. However, to further open the avenues of expanding its applications, specific improvements need to be made in the recognition capability of the system. Hidden Markov Model (HMM) has been the dominant methods of recognition in handwriting recognition in offline and online systems. However, the use of Gaussian observation densities in HMM and representational model for word modeling often does not lead to good classification. Hybrid of Neural Network (NN) and HMM later improves word recognition by taking advantage of NN discriminative property and HMM representational capability. However, the use of NN does not optimize recognition capability as the use of Empirical Risk minimization (ERM) principle in its training leads to poor generalization. In this thesis, we focus on improving the recognition capability of a cursive online handwritten word recognition system by using an emerging method in machine learning, the support vector machine (SVM). We first evaluated SVM in isolated character recognition environment using IRONOFF and UNIPEN character databases. SVM, by its use of principle of structural risk minimization (SRM) have allowed simultaneous optimization of representational and discriminative capability of the character recognizer. We finally demonstrate the various practical issues in using SVM within a hybrid setting with HMM. In addition, we tested the hybrid system on the IRONOFF word database and obtained favourable results.; Nos travaux concernent la reconnaissance de l'écriture manuscrite qui est l'un des domaines de prédilection pour la reconnaissance des formes et les algorithmes d'apprentissage. Dans le domaine de l'écriture en-ligne, les applications concernent tous les dispositifs de saisie permettant à un usager de communiquer de façon transparente avec les systèmes d'information. Dans ce cadre, nos travaux apportent une contribution pour proposer une nouvelle architecture de reconnaissance de mots manuscrits sans contrainte de style. Celle-ci se situe dans la famille des approches hybrides locale/globale où le paradigme de la segmentation/reconnaissance va se trouver résolu par la complémentarité d'un système de reconnaissance de type discriminant agissant au niveau caractère et d'un système par approche modèle pour superviser le niveau global. Nos choix se sont portés sur des Séparateurs à Vastes Marges (SVM) pour le classifieur de caractères et sur des algorithmes de programmation dynamique, issus d'une modélisation par Modèles de Markov Cachés (HMM). Cette combinaison SVM/HMM est unique dans le domaine de la reconnaissance de l'écriture manuscrite. Des expérimentations ont été menées, d'abord dans un cadre de reconnaissance de caractères isolés puis sur la base IRONOFF de mots cursifs. Elles ont montré la supériorité des approches SVM par rapport aux solutions à bases de réseaux de neurones à convolutions (Time Delay Neural Network) que nous avions développées précédemment, et leur bon comportement en situation de reconnaissance de mots.

In the actual automobile market, tightly connected to the overall will to decrease CO2 emissions, hybrid vehicles seem to be a necessary short and medium-term milestone. Typically, a hybrid vehicle has two energy sources: a regular gas engine is usually the main energy source, and an electric motor as a secondary energy source. The ability of a hybrid vehicle to consume less fuel and to emit less CO2 comes from its electric motor. It can be used either alongside with the engine, or alone, with no gas being burnt. Because of the two energy sources, the global powertrain needs to be managed by a strategy that chooses the power split between the engine and the motor, based on the state of charge of the battery. This power split can be optimized based on criteria like fuel consumption, CO2 emissions, etc. The objective of this thesis is to develop optimization models on optimal torque repartition between the motor and the engine of a hybrid vehicle, in order to minimize the CO2 emissions. The first step is to develop models corresponding to a reference hybrid powertrain, which are adapted to the optimization algorithms. The optimization algorithms are different depending if offline or real-time optimization is considered. Among the studied offline algorithms, dynamic programming was used to determine the optimal size of the main elements of the powertrain, and to determine the optimal gain compared to a traditional vehicle. Additionally, an original shooting algorithm called SCOP has been developed, and is able to treat optimal control problems with state constraints. This algorithm is about 50 times faster than dynamic programming. A real-time control strategy, based on the Equivalent Consumption Minimization Strategy (ECMS) and using Pontryagin's Principle, was developed and used on a hybrid prototype vehicle: a Smart equipped with a starter alternator. The results demonstrate the positive impact of the strategy to reduce the fuel consumption and the CO2 emissions.; Dans le contexte automobile actuel, étroitement lié à la volonté de réduire les émissions de CO2 dans l'atmosphère, les véhicules hybrides demeurent un passage obligé à court et moyen terme. Un véhicule hybride possède deux sources d'énergie pour assurer sa propulsion : en général un moteur thermique constitue la principale source d'énergie, tandis qu'un moteur électrique représente la source secondaire. La capacité d'un véhicule hybride à consommer moins de carburant, et à rejeter moins de CO2, provient de la présence du moteur électrique. Celui-ci peut être utilisé soit conjointement avec le moteur thermique, soit seul, aucun carburant n'étant alors consommé. La présence de ces deux sources d'énergie impose au système global d'être régi par une stratégie de contrôle déterminant la répartition du couple entre les deux moteurs en fonction de l'état de charge de la batterie. Cette répartition peut être déterminée pour être optimale vis-à-vis de critères tels que la consommation de carburant, les émissions de polluants, etc. L'objectif de la thèse est de développer des méthodes d'optimisation de la répartition de couple entre les deux moteurs d'un véhicule hybride, dans l'objectif de minimiser les émissions de CO2. Une première étape a consisté à développer des modèles représentatifs d'une architecture type adaptés aux types d'optimisation réalisée. Les algorithmes d'optimisation diffèrent selon qu'ils soient capables de traiter des problèmes hors-ligne, ou temps-réel. Parmi les algorithmes d'optimisation hors-ligne étudiés, la programmation dynamique a été utilisée pour déterminer le dimensionnement optimal des éléments principaux d'une architecture hybride, et en déterminer le gain théorique par rapport à une motorisation traditionnelle. Par ailleurs, un algorithme de tir original nommé SCOP a été développé, celui-ci permettant de traiter des problèmes de commande optimale avec contraintes sur l'état, tout en multipliant les performances par 50 par rapport à la méthode de programmation dynamique. Une stratégie de contrôle temps-réel, basée sur l'Equivalent Consumption Minimization Strategy (ECMS) utilisant le principe de Pontryagin, a été développée et implémentée sur un prototype de véhicule hybride, une Smart équipée d'un alterno-démarreur. Les résultats obtenus démontrent de l'action de la stratégie pour la réduction de la consommation de carburant et des émissions de CO2.

In the actual automobile market, tightly connected to the overall will to decrease CO2 emissions, hybrid vehicles seem to be a necessary short and medium-term milestone. Typically, a hybrid vehicle has two energy sources: a regular gas engine is usually the main energy source, and an electric motor as a secondary energy source. The ability of a hybrid vehicle to consume less fuel and to emit less CO2 comes from its electric motor. It can be used either alongside with the engine, or alone, with no gas being burnt. Because of the two energy sources, the global powertrain needs to be managed by a strategy that chooses the power split between the engine and the motor, based on the state of charge of the battery. This power split can be optimized based on criteria like fuel consumption, CO2 emissions, etc. The objective of this thesis is to develop optimization models on optimal torque repartition between the motor and the engine of a hybrid vehicle, in order to minimize the CO2 emissions. The first step is to develop models corresponding to a reference hybrid powertrain, which are adapted to the optimization algorithms. The optimization algorithms are different depending if offline or real-time optimization is considered. Among the studied offline algorithms, dynamic programming was used to determine the optimal size of the main elements of the powertrain, and to determine the optimal gain compared to a traditional vehicle. Additionally, an original shooting algorithm called SCOP has been developed, and is able to treat optimal control problems with state constraints. This algorithm is about 50 times faster than dynamic programming. A real-time control strategy, based on the Equivalent Consumption Minimization Strategy (ECMS) and using Pontryagin's Principle, was developed and used on a hybrid prototype vehicle: a Smart equipped with a starter alternator. The results demonstrate the positive impact of the strategy to reduce the fuel consumption and the CO2 emissions.; Dans le contexte automobile actuel, étroitement lié à la volonté de réduire les émissions de CO2 dans l'atmosphère, les véhicules hybrides demeurent un passage obligé à court et moyen terme. Un véhicule hybride possède deux sources d'énergie pour assurer sa propulsion : en général un moteur thermique constitue la principale source d'énergie, tandis qu'un moteur électrique représente la source secondaire. La capacité d'un véhicule hybride à consommer moins de carburant, et à rejeter moins de CO2, provient de la présence du moteur électrique. Celui-ci peut être utilisé soit conjointement avec le moteur thermique, soit seul, aucun carburant n'étant alors consommé. La présence de ces deux sources d'énergie impose au système global d'être régi par une stratégie de contrôle déterminant la répartition du couple entre les deux moteurs en fonction de l'état de charge de la batterie. Cette répartition peut être déterminée pour être optimale vis-à-vis de critères tels que la consommation de carburant, les émissions de polluants, etc. L'objectif de la thèse est de développer des méthodes d'optimisation de la répartition de couple entre les deux moteurs d'un véhicule hybride, dans l'objectif de minimiser les émissions de CO2. Une première étape a consisté à développer des modèles représentatifs d'une architecture type adaptés aux types d'optimisation réalisée. Les algorithmes d'optimisation diffèrent selon qu'ils soient capables de traiter des problèmes hors-ligne, ou temps-réel. Parmi les algorithmes d'optimisation hors-ligne étudiés, la programmation dynamique a été utilisée pour déterminer le dimensionnement optimal des éléments principaux d'une architecture hybride, et en déterminer le gain théorique par rapport à une motorisation traditionnelle. Par ailleurs, un algorithme de tir original nommé SCOP a été développé, celui-ci permettant de traiter des problèmes de commande optimale avec contraintes sur l'état, tout en multipliant les performances par 50 par rapport à la méthode de programmation dynamique. Une stratégie de contrôle temps-réel, basée sur l'Equivalent Consumption Minimization Strategy (ECMS) utilisant le principe de Pontryagin, a été développée et implémentée sur un prototype de véhicule hybride, une Smart équipée d'un alterno-démarreur. Les résultats obtenus démontrent de l'action de la stratégie pour la réduction de la consommation de carburant et des émissions de CO2.

The study focuses on the power distribution management between a fuel cells stack and a supercapacitor pack in order to ensure the power demand in a hybrid vehicle. The goal is to minimize the hydrogen consumption on a given cycle. The problem is formulated as a global optimization problem under constraints. In a first approach, the system is described with a discretized dynamic equation and a dynamic programming algorithm is applied. A second approach is to minimize the Hamiltonian after having approached the cost criterion by a polynomial function. These methods require a priori knowledge of the power demand profile and are therefore considered as offline optimization methods. For an online energy management, we applied a decision making system based on fuzzy rules. Inputs and output membership functions of the fuzzy system are optimized using a genetic algorithm. In order to implement the outlined strategies, efficiency of the elements of the power train formed by the fuel cells stack and auxiliaries, the storage element and the static converters is characterized.; L'étude porte sur la gestion de la distribution instantanée de la puissance entre une pile à combustible et un élément de stockage afin d'assurer la puissance électrique nécessaire à la traction d'un véhicule électrique hybride. L'objectif visé est la minimisation de la consommation d'hydrogène sur un cycle donné. Le problème est formulé en tant que problème d'optimisation globale sous contraintes. Dans une première approche, le système est décrit sous forme d'une équation dynamique discrétisée et un algorithme de programmation dynamique est appliqué. Une seconde approche consiste à minimiser le hamiltonien après avoir approché le critère coût par une fonction polynomiale. Ces méthodes nécessitent la connaissance a priori du profil de puissance demandée et se classent parmi les méthodes d'optimisation hors ligne. Pour une gestion en ligne de l'énergie, nous avons appliqué un système de décision à base de règles floues. Les fonctions d'appartenance des entrées et sorties du système flou sont optimisés à l'aide d'un algorithme génétique. Afin d'appliquer les stratégies évoquées, un bilan énergétique du groupe électrogène formé de la pile et ses auxiliaires, de l'élément de stockage et des convertisseurs statiques est effectué.

The study focuses on the power distribution management between a fuel cells stack and a supercapacitor pack in order to ensure the power demand in a hybrid vehicle. The goal is to minimize the hydrogen consumption on a given cycle. The problem is formulated as a global optimization problem under constraints. In a first approach, the system is described with a discretized dynamic equation and a dynamic programming algorithm is applied. A second approach is to minimize the Hamiltonian after having approached the cost criterion by a polynomial function. These methods require a priori knowledge of the power demand profile and are therefore considered as offline optimization methods. For an online energy management, we applied a decision making system based on fuzzy rules. Inputs and output membership functions of the fuzzy system are optimized using a genetic algorithm. In order to implement the outlined strategies, efficiency of the elements of the power train formed by the fuel cells stack and auxiliaries, the storage element and the static converters is characterized.; L'étude porte sur la gestion de la distribution instantanée de la puissance entre une pile à combustible et un élément de stockage afin d'assurer la puissance électrique nécessaire à la traction d'un véhicule électrique hybride. L'objectif visé est la minimisation de la consommation d'hydrogène sur un cycle donné. Le problème est formulé en tant que problème d'optimisation globale sous contraintes. Dans une première approche, le système est décrit sous forme d'une équation dynamique discrétisée et un algorithme de programmation dynamique est appliqué. Une seconde approche consiste à minimiser le hamiltonien après avoir approché le critère coût par une fonction polynomiale. Ces méthodes nécessitent la connaissance a priori du profil de puissance demandée et se classent parmi les méthodes d'optimisation hors ligne. Pour une gestion en ligne de l'énergie, nous avons appliqué un système de décision à base de règles floues. Les fonctions d'appartenance des entrées et sorties du système flou sont optimisés à l'aide d'un algorithme génétique. Afin d'appliquer les stratégies évoquées, un bilan énergétique du groupe électrogène formé de la pile et ses auxiliaires, de l'élément de stockage et des convertisseurs statiques est effectué.

Several real life industrial applications require the allocation of a set of rectangular items (or pieces) to a larger rectangular standardized stock unit. For instance, in the glass, plastic or metal industries, rectangular components have to be cut from a large sheet of material. Similarly, when filling the pages of a newspaper, the editor has to arrange articles and advertisements, presented as rectangular areas, on pages of xed dimensions. Generally, industrial applications require cutting or packing the largest number of items/pieces into a rectangular unit as to minimize the waste of the rectangular stock unit. In this thesis, we propose exact, approximate and parallel algorithms for the Two-Dimensional Cutting stock Problem.; Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.

Several real life industrial applications require the allocation of a set of rectangular items (or pieces) to a larger rectangular standardized stock unit. For instance, in the glass, plastic or metal industries, rectangular components have to be cut from a large sheet of material. Similarly, when filling the pages of a newspaper, the editor has to arrange articles and advertisements, presented as rectangular areas, on pages of xed dimensions. Generally, industrial applications require cutting or packing the largest number of items/pieces into a rectangular unit as to minimize the waste of the rectangular stock unit. In this thesis, we propose exact, approximate and parallel algorithms for the Two-Dimensional Cutting stock Problem.; Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.

International audience; This paper deals with the regulation of greenhouse gases emissions related to climate change. We consider a stylized climate-economy sequential model and use a cost-effectiveness approach. The analytical study is based on a dynamic programming method. It provides both a tolerable ceiling of concentration and, under simple conditions involving the marginal abatement cost and emission functions, optimal and effective abatement rates. In particular, we prove how the cost effective abatement rate increases with time. Through the optimal time to act function, we examine in detail the role played by greenhouse gases absorption, growth and discount rates. We also analyze the paths from an intergenerational equity perspective. Numerical examples illustrate the general statements. © 2007 Elsevier Ltd. All rights reserved.

National audience; La théorie des jeux : un vaste domaine de recherche à la frontière de l’économie et des mathématiques, qui n’a rien à voir avec les jeux vidéos. De quels jeux s’agit-il ici ?

Multimedia networks have to support new real-time services with stringent quality of service (QoS) requirements. Therefore, new routing schemes are needed to avoid traffic congestion and the resulting service degradation by tailoring routes to the prevailing traffics. This motivated the development of the MPLS protocol (Multi Protocol Label Switching). Thanks to its per-LSP routing (Label Switched Path), MPLS allows a finer management of the available resources in the network. The first part of this work deals with the problem of optimal LSPs routing in IP/MPLS networks. We propose an original model which takes into account QoS constraints. We also propose a heuristic algorithm (ILSP-OLS-ACO) enabling to manage a great number of operational constraints, such as bandwidth limitations, LSP affinity and resilience constraints. This heuristic algorithm provides close-to-optimal solutions and is very scalable. The second part of this work is devoted to optimal design of access networks. The originality of the proposed approach is to take into account the traffic generated by the customers as well as the equipment costs. We propose an integer linear programming model. We present an exact optimisation algorithm based on "Branch and Cut" techniques. We also propose a heuristic algorithm combining a "clustering" technique and a local-search procedure. This heuristic algorithm enables to obtain close-to-optimal solutions very quickly for real size networks.; La qualité de service (QoS), liée au partage des ressources, prend tout son sens dans le cadre des réseaux multimédias. L'intégration de celle-ci dans les protocoles de routage, nécessite la prise en compte des phénomènes de congestion. Cela a favorisé l'apparition du protocole MPLS (Multi Protocol Label Switching). Cette nouvelle technologie, grâce à son routage par LSP (Label Swithed Path), permet une gestion plus fine des ressources disponibles dans le réseau. Nous traitons en première partie de ce travail le problème du routage des LSPs dans les réseaux IP/MPLS. Nous en formulons une modélisation originale qui tient compte de la QoS. Nous proposons aussi une heuristique de résolution (ILSP-OLS-ACO) qui gère un grand nombre de contraintes opérationnelles, tels que la bande passante, les contraintes d'affinités ou de sécurité sur les LSPs. Celle-ci fournit des solutions quasi-optimales tout en permettant le passage à l'échelle (grands réseaux, milliers de LSPs). La deuxième partie de notre travail concerne la conception optimale de topologie d'accès. L'originalité de l'approche réside dans le fait de prendre en compte le trafic générés par les clients ainsi que les coûts des équipements. Nous élaborons une modélisation basée sur la programmation linéaire en nombres entiers. Nous proposons pour la résoudre une méthode exacte basée sur des techniques de « Branch and Cut ». Nous proposons aussi une heuristique combinant une technique de « clustering » et une technique de recherche locale, qui permet d'obtenir très rapidement des solutions quasi-optimales.

In this paper, we consider the problem of estimation of the break dates and present an efficient algorithm in order to obtain global minimizers of the sum of squared residuals. This algorithm is based on the principle of dynamic programming and requires at most least-squares operations of order O(n2) for any number of breaks. We also study the estimation of the number of breaks by using the information criteria, the test of Bai and Perron (1998), and the method of Lavielle (2004). Finally, we perform a Monte Carlo study to analyse the behaviour of estimators and tests infinite sample size., Dans ce papier, nous considérons le problème d'estimation des dates de rupture et présentons un algorithme efficace pour obtenir les minimums globaux des sommes des carrés des résidus. Cet algorithme est basé sur le principe de la programmation dynamique et nécessite au plus des opérations de moindres carrés d'ordre O(n2) pour tout nombre de ruptures. Ensuite nous abordons le problème d'estimation du nombre de ruptures par les critères d'information, le test de Bai et Perron (1998) et la méthode de Lavielle (2004). Finalement, une analyse par la méthode de Monte Carlo donnera une idée sur le comportement des estimateurs et des tests en échantillons finis.

When dealing with numerical solution for stochastic optimal control problems, stochastic dynamic programming appears to be the natural framework. Due to the curse of dimensionality the stochastic optimization techniques usually focus on scenarios trees. But this latter method faces an important difficulty: at the first time stages (close to the tree root) we have few Monte-Carlo particles and a small variance of the feedback estimator; on the contrary, at the final time stages (near the tree leaves), we have a large number of Monte-Carlo particles with a huge variance. To tackle these difficulties we present some variational approach for numerical solution of stochastic optimal control problems. We consider two different interpretations of the control problem, an algebraic and a functional one from which we derive optimality conditions. An adaptative mesh discretization method will be used to achieve tractable solution algorithm. An application to a hydro-electric dam production management problem will be presented.; Cette thèse, intitulée méthodes particulaires en commande optimale stochastique s'intéresse aux problèmes d'optimisation dans l'incertain et a leur résolution. Le terme particulaire renvoie au fait que nous considèrons des méthodes basées sur une approche de type Monte-Carlo, contrairement aux méthodes par programmation dynamiques stochastiques qui utilisent une discrétisation faite a priori.La résolution des problèmes d'optimisation stochastique nécessite deux étapes : une étape d'approximation et une étape d'optimisation. Les deux premiers chapitres de ce manuscrit seront consacrées a la partie optimisation. Nous traiterons dans les chapitres qui suivront de l'approximation des problèmes d'optimisation dans l'incertain. Nous commencerons, dans ce manuscrit, (chapitre I) par présenter les problèmes qui seront abordés ; nous nous attarderons surtout sur la représentation de la structure d'information d'un probléme d'optimisation stochastique. Deux principales représentations se dégagent : une représentation algébrique et une représentation fonctionnelle. A partir de la nature de cette structure d'information, nous ferons la typologie des problémes d'optimisation stochastique : boucle ouverte, boucle fermée, information statique ou information dynamique. Le deuxième chapitre (chapitre II) traitera des conditions d'optimalité pour les problèmes de commande optimale stochastique : à partir des représentations algébriques ou fonctionnelles de l'information, nous présenterons des conditions d'optimalité du type Karush-Kuhn-Tucker. Les conditions présentées dans le chapitre II comportent presque invariablement des opérateurs d'espérance conditionnelle. La résolution de ces problèmes impose alors d'approximer ces opérateurs. Nous commencerons dans le chapitre III par motiver notre approche avant de passer à une revue de la littérature des problèmes d'estimation de densité, densité conditionnelle et espérance conditionnelle. Dans le chapitre IV, nous présentons la méthode des élements finis particulaires qui consiste en l'approximation de la structure d'information par une restriction du feedback à une classe donnée a priori de fonctions de base. Différents résultats de convergence et d'erreur asymptotique seront donné. L'avant dernier chapitre (chapitre V) présentera un algorithme chaotique de gradient pour la résolution de problémes d'optimisation stochastique en boucle fermée. Un résultat de convergence, de vitesse ainsi qu'une application numérique seront donnés. Nous nous intéresserons dans le dernier chapitre (chapitre VI) aux aspects numérique de la résolution des problèmes de commande optimale stochastique à partir des difféerentes méthodes présentes dans les chapitres précedents. Nous présenterons diffèrents algorithmes et heuristiques pour résoudre un problème de gestion de production d'un barrage hydro-électrique.

National audience; Le chapitre propose une introduction au domaine de l'optimisation combinatoire multicritère. L'accent est mis sur la complexité de problèmes classiques ainsi que sur des techniques et approches pour l'approximation polynomiale.

Approximate Value Iteration (AVI) is a method for solving a large Markov Decision Problem by approximating the optimal value function with a sequence of value representations Vn processed by means of the iterations $V_{n+1} = \mathcal{AT}V_n$ where $\mathcal{T}$ is the so-called Bellman operator and $\mathcal{A}$, an approximation operator, which may be implemented by a Supervised Learning (SL) algorithm. Previous results relate the asymptotic performance of AVI to the $L\infty$-norm of the approximation errors induced by the SL algorithm. Unfortunately, the SL algorithm usually perform a minimization problem in $L_p$-norms $(p \geq 1)$, rendering the $L\infty$ performance bounds inadequate. In this paper, we extend these performance bounds to weighted $L_p$-norms. This enables to relate the performance of AVI to the approximation power of the SL algorithm, which guarantees the tightness and pratical interest of these bounds. We illustrate the tightness of the bounds on an optimal replacement problem.; L'algorithme d'itérations sur les valeurs avec approximations (IVA) permet de résoudre des problèmes de décision markoviens en grande dimension en approchant la fonction valeur optimale par une séquence de représentations $V_n$ calculées itérativement selon $V_{n+1} = \mathcal{AT}V_n$ où $\mathcal{T}$ est l'opérateur de Bellman et $\mathcal{A}$ un opérateur d'approximation, ce dernier pouvant s'implémenter selon un algorithme d'apprentissage supervisé (AS). Les résultats usuels établissent des bornes sur la performance de IVA en fonction de la norme $L\infty$ des erreurs d'approximation induites par l'algorithme d'AS. Cependant, un algorithme d'AS résout généralement un problème de régression en minimisation une norme $L_p (p\geq 1)$, rendant les majorations d'erreur en norme $L\infty$ inadéquates. Dans cet article, nous étendons ces résultats de majoration à des normes $L_p$ pondérées. Ceci permet d'exprimer les performances de l'algorithme IVA en fonction de la puissance d'approximation de l'algorithme d'AS, ce qui garantit la finesse et l'intérêt applicatif de ces bornes. Nous illustrons numériquement la qualité des majorations obtenues pour un problème de remplacement optimal.