Spelling suggestions: "subject:"opérateur"" "subject:"opérateurs""
251 |
Simulation temps-réel embarquée de systèmes électriques au moyen de FPGA / FPGA-based Embedded real time simulation of electrical systemsDagbagi, Mohamed 08 October 2015 (has links)
L'objectif de ce travail de thèse est de développer une bibliothèque de modules IPs (Intellectual Properties) de simulateurs temps réel embarqués qui simulent différents éléments d'un système électrique. Ces modules ont été conçus pour être utiliser non seulement pour une validation HIL (Hardware-In-the-Loop) des commandes numériques mais aussi pour des applications de commande embarquées, où le module IP de simulateur et le contrôleur sont tous les deux implémentés et exécutés dans la même cible FPGA. Cette nouvelle classe de simulateurs temps réel devrait être de plus en plus incluse dans la prochaine génération de contrôleurs numériques. En effet, ces modules IPs de simulateurs temps réel embarqués peuvent être avantageusement intégrés dans les contrôleurs numériques pour assurer des fonctions comme l'observation, l'estimation, le diagnostic où la surveillance de la santé. Inversement aux cas de HIL, le principal défi lors de la conception de tels simulateurs est de faire face à leur complexité ayant à l'esprit que, dans le cas des systèmes embarqués, les ressources matérielles disponibles sont limitées en raison du coût. En outre, ce problème est renforcé par la nécessité des pas de simulation très petit. Ceci est généralement le cas lors de la simulation des convertisseurs de puissance.Pour développer ces modules IPs, des lignes directrices dédiés de conception ont été proposées pour être suivies pour gérer la complexité de ces simulateurs (solveur de modèle, solveur numérique, pas de simulation, conditionnement de données) tout en tenant compte des contraintes temporelles et matérielles/coût (temps de calcul limité, ressources matérielles limitées ...).Les modules IPs de simulateurs à développer ont été organisés en deux catégories principales: ceux qui sont consacrées aux éléments électromagnétiques d'un système électrique, et ceux dédiés à ses éléments commutés.La première catégorie regroupe les éléments où les phénomènes électriques, magnétiques sont modélisés en plus de phénomènes mécaniques (pour les parties mécaniques) et des phénomènes potentiellement thermiques. Trois cas sont traités: le simulateur temps réel embarqué d'une machine synchrone triphasée, celui d'une machine asynchrone triphasée et celui d'un alternateur synchrone à trois étages. En plus de cela, les avantages de l'utilisation de la transformation delta pour améliorer la stabilité du solveur numérique lorsque un petit pas de calcul et le codage virgule fixe (avec une précision de données limitée) sont utilisés, ont été étudiés.La deuxième catégorie concerne des éléments commutés tels que les convertisseurs de puissance où les événements de commutation sont considérés. Là encore, plusieurs topologies de convertisseurs ont été étudiées: un redresseur simple alternance, un hacheur série, un hacheur réversible en courant, un hacheur quatre quadrant, un onduleur monophasé, un onduleur triphasé, un redresseur à diodes triphasé et un redresseur MLI triphasé. Pour tous ces modules IPs de simulateurs, l'approche de modélisation ADC (Associated Discrete Circuit) est adoptée.Le module IP de simulateur temps réel embarqué du redresseur MLI a été appliqué dans un contexte d'une application embarquée. Cette dernière consiste en une commande tolérante aux défauts d'un convertisseur de tension coté réseau. Ainsi, ce module IP est associé à celui d'un simulateur temps réel d'un filtre RL triphasé et les deux sont embarqués dans le dispositif de commande du redresseur pour estimer les courants de lignes. Ces courants sont injectés dans le dispositif de commande dans le cas d'un défaut de capteur de courant. La capacité de cet estimateur de garantir la continuité de service en cas de défauts est validée par des tests HIL et expérimentalement. / The aim of this thesis work is to develop an IP-Library of FPGA-based embedded real-time simulator IPs (Intellectual Properties) that simulate different elements of an electrical system. These IPs have been designed to be used not only for Hardware-In-the-Loop (HIL) testing of digital controllers but also for low cost embedded control applications, where the simulator IP and the controller are both implemented and run altogether in the same FPGA device. This emerging class of real-time simulators is expected to be more and more included in the next generation of digital controllers. Indeed, such embedded real-time simulator IPs can be advantageously embedded within digital controllers to ensure functions like observation, estimation, diagnostic or health-monitoring. Conversely to the HIL case, the main challenge when designing such simulator IPs is to cope with their complexity having in mind that, in the case of embedded systems, the available hardware resources are limited due to the cost. Furthermore, this challenge is strengthened by the need of very short simulation time-steps which is typically the case when simulating power converters.To develop these IPs, dedicated design guidelines have been proposed to be followed to manage the complexity of these simulator IPs (model solver, numerical solver, time-step, data conditioning) with regards to the timing and the area/cost constraints (computation time limit, limited hardware resources …).The simulators IPs to be developed have been organized into two main categories: those dedicated to electromagnetic elements of an electrical system and those dedicated to their switching elements.The first category gathers elements where electric, magnetic phenomena are modelized in addition to mechanical phenomena (for moving systems) and potentially thermal phenomena. Three cases are dealt with: the embedded real-time simulator of a three-phase synchronous machine, the one of a three-phase induction machine and the one of a brushless synchronous generator. Also, the advantages of using delta transformation to improve the stability of the numerical solver when short simulation time-step and fixed-point (with limited data precision) are used, have been studied.The second category concerns switching elements such as power converters where switching events are considered. Here again, several converter topologies have been studied: a half-wave rectifier, a buck DC-DC converter, a bidirectional buck DC-DC converter, a H-bridge DC-DC converter, a single-phase H-bridge DC-AC converter, a three-phase voltage source inverter, a three-phase diode rectifier and a three-phase PWM rectifier. For all these IPs, the Associated Discrete Circuit (ADC) modeling approach is adopted.The embedded real-time simulator IP of the three-phase PWM rectifier has been applied in the context of an embedded application. The latter consists of a fault-tolerant control of a grid-connected voltage source rectifier. Thus, this simulator IP is associated with the one of a three-phase RL-filter and are both implemented within the rectifier controller to estimate the grid currents. These currents are injected in the controller in the case of a current sensor fault. The ability of this estimator to guarantee the service continuity in the case of faults is validated through HIL tests and experiments.
|
252 |
Comportement en temps long des solutions de quelques équations de Hamilton-Jacobi du premier et second ordre, locales et non-locales, dans des cas non-périodiques / Long time behavior of solutions of some first and second order, local and nonlocal Hamilton-Jacobi equations in non-periodic settingsNguyen, Thi Tuyen 01 December 2016 (has links)
La motivation principale de cette thèse est l'étude du comportement en temps grand des solutions non-bornées d'équations de Hamilton-Jacobi visqueuses dans RN en présence d'un terme d'Ornstein-Uhlenbeck. Nous considérons la même question dans le cas d'une équation de Hamilton-Jacobi du premier ordre. Dans le premier cas, qui constitue le cœur de la thèse, nous généralisons les résultats de Fujita, Ishii et Loreti (2006) dans plusieurs directions. La première est de considérer des opérateurs de diffusion plus généraux en remplaçant le Laplacien par une matrice de diffusion quelconque. Nous considérons ensuite des opérateurs non-locaux intégro-différentiels de type Laplacien fractionnaire. Le second type d'extension concerne le Hamiltonien qui peut dépendre de x et est seulement supposé sous-linéaire par rapport au gradient. / The main aim of this thesis is to study large time behavior of unbounded solutions of viscous Hamilton-Jacobi equations in RN in presence of an Ornstein-Uhlenbeck drift. We also consider the same issue for a first order Hamilton-Jacobi equation. In the first case, which is the core of the thesis, we generalize the results obtained by Fujita, Ishii and Loreti (2006) in several directions. The first one is to consider more general operators. We first replace the Laplacian by a general diffusion matrix and then consider a non-local integro-differential operator of fractional Laplacian type. The second kind of extension is to deal with more general Hamiltonians which are merely sublinear.
|
253 |
Développements autour de la méthode d'interactions de configurations en champ moyen / Development over the mean-field interaction configuration methodIlmane, Amine 10 December 2015 (has links)
Dans cette thèse ont été développés de nouveaux outils de calcul théorique de spectres moléculaires rovibrationnels qui permettent de mieux traiter les états vibrationnels très excités ainsi que les mouvements de grandes amplitudes avec la méthode d’interactions de configurations en champ moyen. Dans un premier temps, nous avons discuté la question du choix des bases modales et les différents compromis à trouver afin de pallier aux défauts possibles des surfaces d'énergie potentielle. Dans ce cadre nous avons également développé un critère de sélection visant à améliorer la qualité des fonctions d'ondes rovibrationnelles de base. Ces approches ont été appliquées avec succès à la molécule de méthane CH4.Dans un second temps, nous avons implémenté un algorithme de calcul formel des opérateurs d'énergie cinétique en coordonnées quelconques qui permet d'avoir des expressions exactes ainsi que leurs développements en série de Taylor ou Fourier, qui exploite au mieux les potentialités du logiciel MATHEMATICA et a permis d'obtenir des hamiltoniens rovibrationnels en coordonnées de valence de façon particulièrement efficace. Enfin, nous avons généralisé la méthode d’interactions de configurations en champ moyen en ajoutant de façon perturbative un champ effectif d'ordre deux. Nous avons appliqué cette généralisation à la molécule de péroxyde d'hydrogène HOOH, ce qui a permis de montrer son intérêt tant pour l'amélioration des niveaux d'énergie que des fonctions d'onde associées, lorsqu'on a affaire à des groupes de degrés de liberté bien séparés énergétiquement. / In this thesis we developed new theoretical tools for molecular rovibrational spectra for a better description of the excited vibrational states and movements with large amplitudes using mean field configuration interaction method. First, we discussed the choice of modal basis and different trade-off to overcome the possible shortcomings of potential energy surfaces. In this context we have also developed selection criteria to improve the quality of rovibrational wave functions. These approaches have been successfully applied to the methane molecule (CH4). Secondly, we have implemented a formal algorithm for calculating the kinetic energy operators in arbitrary coordinates that allows the derivation of exact expressions and their Taylor and Fourier series, using, in a very efficient way, the capabilities of the software MATHEMATICA which yield to the derivation of rovibrational Hamiltonians in valence coordinated. Finally, we have generalized the mean-field configuration interaction method by adding perturbatively a second order effective field. We applied this generalization to the hydrogen peroxide molecule (HOOH), which has shown an improvement for both energy levels and the associated wave functions, when dealing with groups of degrees of freedom that are energetically well separated.
|
254 |
Méthode du gradient topologique pour la détection de contours et de structures fines en imagerie / Topological gradient method applied to the detection of edges and fine structures in imagingDrogoul, Audric 08 October 2014 (has links)
Cette thèse porte sur la méthode du gradient topologique appliquée au traitement d'images. Principalement, on s'intéresse à la détection d'objets assimilés, soit à des contours si l'intensité de l'image à travers la structure comporte un saut, soit à une structure fine (filaments et points en 2D) s'il n'y a pas de saut à travers la structure. On commence par généraliser la méthode du gradient topologique déjà utilisée en détection de contours pour des images dégradées par du bruit gaussien, à des modèles non linéaires adaptés à des images contaminées par un processus poissonnien ou du bruit de speckle et par différents types de flous. On présente également un modèle de restauration par diffusion anisotrope utilisant le gradient topologique pour un domaine fissuré. Un autre modèle basé sur une EDP elliptique linéaire utilisant un opérateur anisotrope préservant les contours est proposé. Ensuite, on présente et étudie un modèle de détection de structures fines utilisant la méthode du gradient topologique. Ce modèle repose sur l'étude de la sensibilité topologique d'une fonction coût utilisant les dérivées secondes d'une régularisation de l'image solution d'une EDP d'ordre 4 de type Kirchhoff. En particulier on explicite les gradients topologiques pour des domaines 2D fissurés ou perforés, et des domaines 3D fissurés. Plusieurs applications pour des images 2D et 3D, floutées et contaminées par du bruit gaussien, montrent la robustesse et la rapidité de la méthode. Enfin on généralise notre approche pour la détection de contours et de structures fines par l'étude de la sensibilité topologique d'une fonction coût utilisant les dérivées m−ième d'une régularisation de l'image dégradée, solution d'une EDP d'ordre 2m. / This thesis deals with the topological gradient method applied in imaging. Particularly, we are interested in object detection. Objects can be assimilated either to edges if the intensity across the structure has a jump, or to fine structures (filaments and points in 2D) if there is no jump of intensity across the structure. We generalize the topological gradient method already used in edge detection for images contaminated by Gaussian noise, to quasi-linear models adapted to Poissonian or speckled images possibly blurred. As a by-product, a restoration model based on an anisotropic diffusion using the topological gradient is presented. We also present a model based on an elliptical linear PDE using an anisotropic differential operator preserving edges. After that, we study a variational model based on the topological gradient to detect fine structures. It consists in the study of the topological sensitivity of a cost function involving second order derivatives of a regularized version of the image solution of a PDE of Kirchhoff type. We compute the topological gradients associated to perforated and cracked 2D domains and to cracked 3D domains. Many applications performed on 2D and 3D blurred and Gaussian noisy images, show the robustness and the fastness of the method. An anisotropic restoration model preserving filaments in 2D is also given. Finally, we generalize our approach by the study of the topological sensitivity of a cost function involving the m − th derivatives of a regularization of the image solution of a 2m order PDE.
|
255 |
Étude de problèmes différentiels elliptiques et paraboliques sur un graphe / A qtudy of elliptic and parabolic differential problems on graphsVasseur, Baptiste 06 February 2014 (has links)
Après une présentation des notations usuelles de la théorie des graphes, on étudie l'ensemble des fonctions harmoniques sur les graphes, c'est à dire des fonctions dont le laplacien est nul. Ces fonctions forment un espace vectoriel et sur un graphe uniformément localement fini, on montre que cet espace vectoriel est soit de dimension un, soit de dimension infinie. Lorsque le graphe comporte une infinité de cycles, ce résultat tombe en défaut et on exhibe des exemples qui montrent qu'il existe un graphe sur lequel les harmoniques forment un espace vectoriel de dimension n, pour tout n. Un exemple de graphe périodique est également traité. Ensuite, toujours pour le laplacien, on étudie plus précisément sur les arbres uniformément localement finis les valeurs propres dont l'espace propre est de dimension infini. Dans ce cas, il est montré que l'espace propre contient un sous-espace isomorphe à l'ensemble des suites réelles bornées. Une inégalité concernant le spectre est donnée dans le cas spécial où les arêtes sont de longueur un. Des exemples montrent que ces inclusions sont optimales. Dans le chapitre suivant, on étudie le comportement asymptotique des valeurs propres pour des opérateurs elliptiques d'ordre 2 quelconques sous des conditions de Kirchhoff dynamiques. Après réécriture du problème sous la forme d'un opérateur de Sturm-Liouville, on écrit le problème de façon matricielle. Puis on trouve une équation caractéristique dont les zéros correspondent aux valeurs propres. On en déduit une formule pour l'asymptotique des valeurs propres. Dans le dernier chapitre, on étudie la stabilité de solutions stationnaires pour certains problèmes de réaction-diffusion où le terme de non linéarité est polynomial. / After a quick presentation of usual notations for the graph theory, we study the set of harmonic functions on graphs, that is, the functions whose laplacian is zero. These functions form a vectorial space. On a uniformly locally finite tree, we shaw that this space has dimension one or infinity. When the graph has an infinite number of cycles, this result change and we describe some examples showing that there exists a graph on which the harmonic functions form a vectorial space of dimension n, for all n. We also treat the case of a particular periodic graph. Then, we study more precisely the eigenvalues of infinite dimension. In this case, the eigenspace contains a subspace isomorphic to the set of bounded sequences. An inequality concerning the spectral is given when edges length is equal to one. Examples show that these inclusions are optimal. We also study the asymptotic behavior of eigenvalues for elliptic operators under dynamical Kirchhoff node conditions. We write the problem as a Sturm-Liouville operator and we transform it in a matrix problem. Then we find a characteristic equation whose zeroes correspond to eigenvalues. We deduce a formula for the asymptotic behavior. In the last chapter, we study the stability of stationary solutions for some reaction-diffusion problem whose the non-linear term is polynomial.
|
256 |
Quelques asymptotiques spectrales pour le Laplacien de Dirichlet : triangles, cônes et couches coniques / A few spectral asymptotics for the Dirichlet Laplacian : triangles, cones and conical layersOurmières-Bonafos, Thomas 01 October 2014 (has links)
Cette thèse est consacrée à l'étude du spectre de l'opérateur de Laplace avec conditions de Dirichlet dans différents domaines du plan ou de l'espace. Dans un premier temps on s'intéresse à des triangles asymptotiquement plats et des cônes de petite ouverture. Ces problèmes admettent une reformulation semi-classique et nous donnons des développements asymptotiques à tout ordre des premières valeurs et fonctions propres. Ce type de résultat est déjà connu pour des domaines minces à profil régulier. Pour les triangles et les cônes, on prouve que le problème admet maintenant deux échelles. Dans un second temps, on étudie une famille de couches coniques indexées par leur ouverture. Là encore, on s'intéresse à la limite semi-classique quand l'ouverture tend vers zéro: on donne un développement asymptotique à deux termes des premières valeurs propres et on démontre un résultat de localisation des fonctions propres associées. Nous donnons également, à ouverture fixée, un équivalent du nombre de valeurs propres sous le seuil du spectre essentiel. / This thesis deals with the spectrum of the Dirichlet Laplacian in various two or three dimensional domains. First, we consider asymptotically flat triangles and cones with small aperture. These problems admit a semi-classical formulation and we provide asymptotic expansions at any order for the first eigenvalues and the associated eigenfunctions. These type of results is already known for thin domains with smooth profiles. For triangles and cones, we show that the problem admits now two different scales. Second, we study a family of conical layers parametrized by their aperture. Again, we consider the semi-classical limit when the aperture tends to zero: We provide a two-term asymptotics of the first eigenvalues and we prove a localization result about the associated eigenfunctions. We also estimate, for each chosen aperture, the number of eigenvalues below the threshold of the essential spectrum.
|
257 |
Le problème de Steklov paramétrique et ses applicationsSt-Amant, Simon 04 1900 (has links)
Ce mémoire contient deux articles que j’ai rédigés au cours de ma maîtrise. Le premier
chapitre sert d’introduction à ces articles. Plusieurs concepts de géométrie spectrale y sont
présentés dans le contexte du problème de Steklov, en plus des résultats principaux des
chapitres subséquents.
Le second chapitre porte sur le problème de Steklov paramétrique sur des surfaces lisses.
Un développement asymptotique complet des valeurs propres du problème est obtenu à l’aide
de méthodes pseudodifférentielles. Celui-ci généralise l’asymptotique spectrale déjà connue
du problème de Steklov classique. Nous en déduisons de nouveaux invariants géométriques
déterminés par le spectre.
Le troisième chapitre porte sur le problème de ballottement sur des prismes à base triangulaire. Le but est de comprendre comment les angles du prisme affectent le deuxième
terme du développement asymptotique de la fonction de compte des valeurs propres. En
construisant des quasimodes, nous obtenons une expression de ce terme que nous conjecturons comme étant la bonne pour les vraies valeurs propres. Cette conjecture est alors
supportée par des expériences numériques. / This thesis contains two articles that I wrote during my M.Sc. studies. The first chapter
serves as an introduction to both articles. Some concepts of spectral geometry in the context
of the Steklov problem are presented, as well as the main results of the subsequent chapters.
The second chapter concerns the parametric Steklov problem on smooth surfaces. We
obtain a complete asymptotic expansion of the eigenvalues of the problem by using pseudodifferential techniques. This generalizes the already known spectral asymptotics of the
classical Steklov problem. We deduce new geometric invariants determined by the spectrum.
The third chapter concerns the sloshing problem on triangular prisms. The goal is to
understand how the angles in the prism affect the second term in the asymptotic expansion
of the eigenvalue counting function. By constructing quasimodes, we obtain an expression
for this term that we conjecture as being correct for the true eigenvalues. This conjecture is
then supported by numerical experiments.
|
258 |
Generalization bounds for random samples in Hilbert spaces / Estimation statistique dans les espaces de HilbertGiulini, Ilaria 24 September 2015 (has links)
Ce travail de thèse porte sur l'obtention de bornes de généralisation pour des échantillons statistiques à valeur dans des espaces de Hilbert définis par des noyaux reproduisants. L'approche consiste à obtenir des bornes non asymptotiques indépendantes de la dimension dans des espaces de dimension finie, en utilisant des inégalités PAC-Bayesiennes liées à une perturbation Gaussienne du paramètre et à les étendre ensuite aux espaces de Hilbert séparables. On se pose dans un premier temps la question de l'estimation de l'opérateur de Gram à partir d'un échantillon i. i. d. par un estimateur robuste et on propose des bornes uniformes, sous des hypothèses faibles de moments. Ces résultats permettent de caractériser l'analyse en composantes principales indépendamment de la dimension et d'en proposer des variantes robustes. On propose ensuite un nouvel algorithme de clustering spectral. Au lieu de ne garder que la projection sur les premiers vecteurs propres, on calcule une itérée du Laplacian normalisé. Cette itération, justifiée par l'analyse du clustering en termes de chaînes de Markov, opère comme une version régularisée de la projection sur les premiers vecteurs propres et permet d'obtenir un algorithme dans lequel le nombre de clusters est déterminé automatiquement. On présente des bornes non asymptotiques concernant la convergence de cet algorithme, lorsque les points à classer forment un échantillon i. i. d. d'une loi à support compact dans un espace de Hilbert. Ces bornes sont déduites des bornes obtenues pour l'estimation d'un opérateur de Gram dans un espace de Hilbert. On termine par un aperçu de l'intérêt du clustering spectral dans le cadre de l'analyse d'images. / This thesis focuses on obtaining generalization bounds for random samples in reproducing kernel Hilbert spaces. The approach consists in first obtaining non-asymptotic dimension-free bounds in finite-dimensional spaces using some PAC-Bayesian inequalities related to Gaussian perturbations and then in generalizing the results in a separable Hilbert space. We first investigate the question of estimating the Gram operator by a robust estimator from an i. i. d. sample and we present uniform bounds that hold under weak moment assumptions. These results allow us to qualify principal component analysis independently of the dimension of the ambient space and to propose stable versions of it. In the last part of the thesis we present a new algorithm for spectral clustering. It consists in replacing the projection on the eigenvectors associated with the largest eigenvalues of the Laplacian matrix by a power of the normalized Laplacian. This iteration, justified by the analysis of clustering in terms of Markov chains, performs a smooth truncation. We prove nonasymptotic bounds for the convergence of our spectral clustering algorithm applied to a random sample of points in a Hilbert space that are deduced from the bounds for the Gram operator in a Hilbert space. Experiments are done in the context of image analysis.
|
259 |
Nonlinear and Hybrid Feedbacks with Continuous-Time Linear Systems / Rétroactions non linéaires et hybrides avec systèmes linéaires à temps continuCocetti, Matteo 21 May 2019 (has links)
Dans cette thèse, nous étudions la rétroaction de systèmes linéaires invariants dans le temps reliés entre eux par trois blocs non linéaires spécifiques : un opérateur de lecture/arrêt, un mécanisme de réinitialisation de commutation et une zone morte adaptative. Cette configuration ressemble au problème de Lure étudié dans le cadre de stabilité absolue, mais les types de non-linéarités considérés ici ne satisfont pas (en général) une condition sectorielle. Ces blocs non linéaires donnent lieu à toute une série de phénomènes intéressants, tels que des ensembles compacts d’équilibres, des ensembles hybrides oméga-limites et des contraintes d’état. Tout au long de la thèse, nous utilisons le formalisme des systèmes hybrides pour décrire ces phénomènes et analyser ces boucles. Nous obtenons des conditions de stabilité très précises qui peuvent être formulées sous forme d’inégalités matricielles linéaires, donc vérifiables avec des solveurs numériques efficaces. Enfin, nous appliquons les résultats théoriques à deux applications automobiles. / In this thesis we study linear time-invariant systems feedback interconnected with three specific nonlinear blocks; a play/stop operator, a switching-reset mechanism, and an adaptive dead-zone. This setup resembles the Lure problem studied in the absolute stability framework, but the types of nonlinearities considered here do not satisfy (in general) a sector condition. These nonlinear blocks give rise to a whole range of interesting phenomena, such as compact sets of equilibria, hybrid omega-limit sets, and state constraints. Throughout the thesis, we use the hybrid systems formalism to describe these phenomena and to analyze these loops. We obtain sharp stability conditions that can be formulated as linear matrix inequalities, thus verifiable with numerically efficient solvers. Finally, we apply the theoretical findings to two automotive applications.
|
260 |
Nonlinear Perron-Frobenius theory and mean-payoff zero-sum stochastic games / Théorie de Perron-Frobenius non-linéaire et jeux stochastiques à somme nulle avec paiement moyenHochart, Antoine 14 November 2016 (has links)
Les jeux stochastiques à somme nulle possèdent une structure récursive qui s'exprime dans leur opérateur de programmation dynamique, appelé opérateur de Shapley. Ce dernier permet d'étudier le comportement asymptotique de la moyenne des paiements par unité de temps. En particulier, le paiement moyen existe et ne dépend pas de l'état initial si l'équation ergodique - une équation non-linéaire aux valeurs propres faisant intervenir l'opérateur de Shapley - admet une solution. Comprendre sous quelles conditions cette équation admet une solution est un problème central de la théorie de Perron-Frobenius non-linéaire, et constitue le principal thème d'étude de cette thèse. Diverses classes connues d'opérateur de Shapley peuvent être caractérisées par des propriétés basées entièrement sur la relation d'ordre ou la structure métrique de l'espace. Nous étendons tout d'abord cette caractérisation aux opérateurs de Shapley "sans paiements", qui proviennent de jeux sans paiements instantanés. Pour cela, nous établissons une expression sous forme minimax des fonctions homogènes de degré un et non-expansives par rapport à une norme faible de Minkowski. Nous nous intéressons ensuite au problème de savoir si l'équation ergodique a une solution pour toute perturbation additive des paiements, problème qui étend la notion d'ergodicité des chaînes de Markov. Quand les paiements sont bornés, cette propriété d'"ergodicité" est caractérisée par l'unicité, à une constante additive près, du point fixe d'un opérateur de Shapley sans paiement. Nous donnons une solution combinatoire s'exprimant au moyen d'hypergraphes à ce problème, ainsi qu'à des problèmes voisins d'existence de points fixes. Puis, nous en déduisons des résultats de complexité. En utilisant la théorie des opérateurs accrétifs, nous généralisons ensuite la condition d'hypergraphes à tous types d'opérateurs de Shapley, y compris ceux provenant de jeux dont les paiements ne sont pas bornés. Dans un troisième temps, nous considérons le problème de l'unicité, à une constante additive près, du vecteur propre. Nous montrons d'abord que l'unicité a lieu pour une perturbation générique des paiements. Puis, dans le cadre des jeux à information parfaite avec un nombre fini d'actions, nous précisons la nature géométrique de l'ensemble des perturbations où se produit l'unicité. Nous en déduisons un schéma de perturbations qui permet de résoudre les instances dégénérées pour l'itération sur les politiques. / Zero-sum stochastic games have a recursive structure encompassed in their dynamic programming operator, so-called Shapley operator. The latter is a useful tool to study the asymptotic behavior of the average payoff per time unit. Particularly, the mean payoff exists and is independent of the initial state as soon as the ergodic equation - a nonlinear eigenvalue equation involving the Shapley operator - has a solution. The solvability of the latter equation in finite dimension is a central question in nonlinear Perron-Frobenius theory, and the main focus of the present thesis. Several known classes of Shapley operators can be characterized by properties based entirely on the order structure or the metric structure of the space. We first extend this characterization to "payment-free" Shapley operators, that is, operators arising from games without stage payments. This is derived from a general minimax formula for functions homogeneous of degree one and nonexpansive with respect to a given weak Minkowski norm. Next, we address the problem of the solvability of the ergodic equation for all additive perturbations of the payment function. This problem extends the notion of ergodicity for finite Markov chains. With bounded payment function, this "ergodicity" property is characterized by the uniqueness, up to the addition by a constant, of the fixed point of a payment-free Shapley operator. We give a combinatorial solution in terms of hypergraphs to this problem, as well as other related problems of fixed-point existence, and we infer complexity results. Then, we use the theory of accretive operators to generalize the hypergraph condition to all Shapley operators, including ones for which the payment function is not bounded. Finally, we consider the problem of uniqueness, up to the addition by a constant, of the nonlinear eigenvector. We first show that uniqueness holds for a generic additive perturbation of the payments. Then, in the framework of perfect information and finite action spaces, we provide an additional geometric description of the perturbations for which uniqueness occurs. As an application, we obtain a perturbation scheme allowing one to solve degenerate instances of stochastic games by policy iteration.
|
Page generated in 0.0702 seconds