This thesis focuses on optimization on a generic objective function based on reflected Brownian motion (RBM). We investigate in several approaches including the partial differential equation approach where we write our objective function in terms of a Hamilton-Jacobi-Bellman equation using the dynamic programming principle and the gradient descent approach where we use two different gradient estimators. We provide extensive numerical results with the gradient descent approach and we discuss the difficulties and future study opportunities for this problem.

<p>Games on graphs have become an indispensable tool in modern computer science. They provide powerful and expressive models for numerous phenomena and are extensively used in computer- aided verification, automata theory, logic, complexity theory, computational biology, etc.</p><p>The infinite games on finite graphs we study in this thesis have their primary applications in verification, but are also of fundamental importance from the complexity-theoretic point of view. They include parity, mean payoff, and simple stochastic games.</p><p>We focus on solving graph games by using iterative strategy improvement and methods from linear programming and combinatorial optimization. To this end we consider old strategy evaluation functions, construct new ones, and show how all of them, due to their structural similarities, fit into a unifying combinatorial framework. This allows us to employ randomized optimization methods from combinatorial linear programming to solve the games in expected subexponential time.</p><p>We introduce and study the concept of a controlled optimization problem, capturing the essential features of many graph games, and provide sufficent conditions for solvability of such problems in expected subexponential time.</p><p>The discrete strategy evaluation function for mean payoff games we derive from the new controlled longest-shortest path problem, leads to improvement algorithms that are considerably more efficient than the previously known ones, and also improves the efficiency of algorithms for parity games.</p><p>We also define the controlled linear programming problem, and show how the games are translated into this setting. Subclasses of the problem, more general than the games considered, are shown to belong to NP intersection coNP, or even to be solvable by subexponential algorithms.</p><p>Finally, we take the first steps in investigating the fixed-parameter complexity of parity, Rabin, Streett, and Muller games.</p>

<p>In 1989 Jun Kigami made an analytic construction of a Laplacian on the Sierpiński gasket, a construction that he extended to post critically finite fractals. Since then, this field has evolved into a proper theory of analysis on fractals. The new results obtained in this thesis are all in the setting of Kigami's theory. They are presented in three papers.</p><p>Strichartz recently showed that there are first order linear differential equations, based on the Laplacian, that are not solvable on the Sierpiński gasket. In the first paper we give a characterization on the polynomial p so that the differential equation p(Δ)u=f is solvable on any open subset of the Sierpiński gasket for any f continuous on that subset. For general p we find the open subsets on which p(Δ)u=f is solvable for any continuous f.</p><p>In the second paper we describe the infinitesimal geometric behavior of a large class of smooth functions on the Sierpiński gasket in terms of the limit distribution of their local eccentricity, a generalized direction of gradient. The distribution of eccentricities is codified as an infinite dimensional perturbation problem for a suitable iterated function system, which has the limit distribution as an invariant measure. We extend results for harmonic functions found by Öberg, Strichartz and Yingst to larger classes of functions.</p><p>In the third paper we define and study intrinsic first order derivatives on post critically finite fractals and prove differentiability almost everywhere for certain classes of fractals and functions. We apply our results to extend the geography is destiny principle, and also obtain results on the pointwise behavior of local eccentricities. Our main tool is the Furstenberg-Kesten theory of products of random matrices.</p>

Unbounded domains often appear in engineering applications, such as acoustic or elastic wave radiation from a body immersed in an infinite medium. To simulate the unboundedness of the domain special boundary conditions have to be imposed: the Sommerfeld radiation condition. In the present work we focused on steady-state wave propagation. The objective of this research is to obtain accurate prediction of phenomena occurring in exterior acoustics and elastodynamics and ensure the quality of the solutions even for high wavenumbers. To achieve this aim, we develop higher-order domain-based schemes: Spectral Element Method (SEM) coupled to Dirichlet-to-Neumann (DtN ), Perfectly Matched Layer (PML) and Infinite Element (IEM) methods. Spectral elements combine the rapid convergence rates of spectral methods with the geometric flexibility of the classical finite element methods. The interpolation is based on Chebyshev and Legendre polynomials. This work presents an implementation of these techniques and their validation exploiting some benchmark problems. A detailed comparison between the DtN, PML and IEM is made in terms of accuracy and convergence, conditioning and computational cost.

Résumé: Cette dissertation s’intéresse aux méthodes numériques dans le domaine de l’acoustique. Les propriétés acoustiques d’un produit sont devenues une part intégrante de la conception. En effet, de nos jours le bruit est perçu comme une nuisance par le consommateur et constitue un critère de vente. Il y a de plus des normes à respecter. Les méthodes numériques permettent de prédire la propagation sonore et constitue dès lors un outil de conception incontournable pour réduire le temps et les coûts de développement d’un produit. Cette dissertation considère la propagation d’ondes acoustiques dans le domaine fréquentiel en tenant compte de la présence d’un écoulement. Nous pouvons citer comme application industrielle, le rayonnement d’une nacelle de réacteur d’avion. Le but de la thèse est de proposer une nouvelle méthode et démontrer ses performances par rapport aux méthodes actuellement utilisées (i.e. la méthode des éléments finis). L’originalité du travail consiste à étendre la méthode de partition de l’unité polynomiale dans le cadre de la propagation acoustique convectée, pour des domaines extérieurs. La simulation acoustique dans des domaines de dimensions infinies est réalisée dans ce travail à l’aide d’un couplage entre éléments finis et éléments infinis. La dissertation présente la formulation de la méthode pour des applications axisymétriques et tridimensionnelles et vérifie la méthode en comparant les résultats numériques obtenus avec des solutions analytiques pour des applications académiques (i.e. propagation dans un conduit, rayonnement d’un multipole, bruit émis par la vibration d’un piston rigide, etc.). Les performances de la méthode sont ensuite analysées. Des courbes de convergences illustrent à une fréquence donnée, la précision de la méthode en fonction du nombre d’inconnues. Tandis que des courbes de performances présentent le temps de calcul nécessaire pour obtenir une solution d’une précision donnée en fonction de la fréquence d’excitation. Ces études de performances montrent l’intérêt de la méthode présentée. Le rayonnement d’un réacteur d’avion a été abordé dans le but de vérifier la méthode sur une application de type industriel. Les résultats illustrent la propagation pour une nacelle axisymétrique en tenant compte de l’écoulement et la présence de matériau absorbant dans la nacelle et compare les résultats obtenus avec la méthode proposée et ceux obtenus avec la méthode des éléments finis. Les performances de la méthode de la partition de l’unité dans le cadre de la propagation convectée en domaines infinis sont présentées pour des applications académiques et de type industriel. Le travail effectué illustre l’intérêt d’utiliser des fonctions polynomiales d’ordre élevé ainsi que les avantages à enrichir l’approximation localement afin d’améliorer la solution sans devoir créer un maillage plus fin. Summary: Environmental considerations are important in the design of many engineering systems and components. In particular, the environmental impact of noise is important over a very broad range of engineering applications and is increasingly perceived and regulated as an issue of occupational safety or health, or more simply as a public nuisance. The acoustic quality is then considered as a criterion in the product design process. Numerical prediction techniques allow to simulate vibro-acoustic responses. The use of such techniques reduces the development time and cost. This dissertation focuses on acoustic convected radiation in outer domains such as it is the case for turbofan radiation. In the current thesis the mapped infinite partition of unity method is implemented within a coupled finite and infinite element model. This method allows to enrich the approximation with polynomial functions. We present axisymmetric and three-dimensional formulations, verify and analyse the performance of the method. The verification compares computed results with the proposed method and analytical solutions for academic applications (i.e. duct propagation, multipole radiation, noise radiated by a vibrating rigid piston, etc.) . Performance analyses are performed with convergence curves plotting, for a given frequency, the accuracy of the computed solution with respect to the number of degrees of freedom or with performance curves, plotting the CPU time required to solve the application within a given accuracy, with respect to the excitation frequency. These performance analyses illustrate the interest of the mapped infinite partition of unity method. We compute the radiation of an axisymmetric turbofan (convected radiation and acoustic treatments). The aim is to verify the method on an industrial application. We illustrate the radiation and compare the mapped infinite partition of unity results with finite element computations. The dissertation presents the mapped partition of unity method as a computationally efficient method and illustrates its performances for academic as well as industrial applications. We suggest to use the method with high order polynomials and take the advantage of the method which allows to locally enrich the approximation. This last point improves the accuracy of the solution and prevent from creating a finer mesh.

A discrete event system is a system whose state space is given by a discrete set and whose state transition mechanism is event-driven i.e., its state evolution depends only on the occurrence of discrete events over the time. These systems are used in many fields of application (telecommunication networks, aeronautics, aerospace,...). The validity of these systems is then an important issue and to ensure it we can use supervisory control methods. These methods consist in imposing a given specification on a system by means of a controller which runs in parallel with the original system and which restricts its behavior. In this thesis, we develop supervisory control methods where the system can have an infinite state space and the controller has a partial observation of the system (this implies that the controller must define its control policy from an imperfect knowledge of the system). Unfortunately, this problem is generally undecidable. To overcome this negative result, we use abstract interpretation techniques which ensure the termination of our algorithms by overapproximating, however, some computations. The aim of this thesis is to provide the most complete contribution it is possible to bring to this topic. Hence, we consider more and more realistic problems. More precisely, we start our work by considering a centralized framework (i.e., the system is controlled by a single controller) and by synthesizing memoryless controllers (i.e., controllers that define their control policy from the current observation received from the system). Next, to obtain better solutions, we consider the synthesis of controllers that record a part or the whole of the execution of the system and use this information to define the control policy. Unfortunately, these methods cannot be used to control an interesting class of systems: the distributed systems. We have then defined methods that allow to control distributed systems with synchronous communications (decentralized and modular methods) and with asynchronous communications (distributed method). Moreover, we have implemented some of our algorithms to experimentally evaluate the quality of the synthesized controllers. / Un système à événements discrets est un système dont l'espace d'états est un ensemble discret et dont l'évolution de l'état courant dépend de l'occurrence d'événements discrets à travers le temps. Ces systèmes sont présents dans de nombreux domaines critiques tels les réseaux de communications, l'aéronautique, l'aérospatiale... La validité de ces systèmes est dès lors une question importante et une manière de l'assurer est d'utiliser des méthodes de contrôle supervisé. Ces méthodes associent au système un dispositif, appelé contrôleur, qui s'exécute en parrallèle et qui restreint le comportement du système de manière à empêcher qu'un comportement erroné ne se produise. Dans cette thèse, on s'intéresse au développement de méthodes de contrôle supervisé où le système peut avoir un espace d'états infini et où les contrôleurs ne sont pas toujours capables d'observer parfaitement le système; ce qui implique qu'ils doivent définir leur politique de contrôle à partir d'une connaissance imparfaite du système. Malheureusement, ce problème est généralement indécidable. Pour surmonter cette difficulté, nous utilisons alors des techniques d'interprétation abstraite qui assurent la terminaison de nos algorithmes au prix de certaines sur-approximations dans les calculs. Le but de notre thèse est de fournir la contribution la plus complète possible dans ce domaine et nous considèrons pour cela des problèmes de plus en plus réalistes. Plus précisement, nous avons commencé notre travail en définissant une méthode centralisée où le système est contrôlé par un seul contrôleur qui définit sa politique de contrôle à partir de la dernière information reçue du système. Ensuite, pour obtenir de meilleures solutions, nous avons défini des contrôleurs qui retiennent une partie ou la totalité de l'exécution du système et qui définissent leur politique de contrôle à partir de cette information. Malheureusement, ces méthodes ne peuvent pas être utilisées pour contrôler une classe intéressante de systèmes: les sytèmes distribués. Nous avons alors défini des méthodes permettant de contrôler des systèmes distribués dont les communications sont synchrones (méthodes décentralisées et modulaires) et asynchrones (méthodes distribuées). De plus, nous avons implémenté certains de nos algorithmes pour évaluer expérimentalement la qualité des contrôleurs qu'ils synthétisent.

<p>In this thesis, we give two constructions for Riemannian metrics on Seiberg-Witten moduli spaces. Both these constructions are naturally induced from the L2-metric on the configuration space. The construction of the so called quotient L2-metric is very similar to the one construction of an L2-metric on Yang-Mills moduli spaces as given by Groisser and Parker. To construct a Riemannian metric on the total space of the Seiberg-Witten bundle in a similar way, we define the reduced gauge group as a subgroup of the gauge group. We show, that the quotient of the premoduli space by the reduced gauge group is isomorphic as a U(1)-bundle to the quotient of the premoduli space by the based gauge group. The total space of this new representation of the Seiberg-Witten bundle carries a natural quotient L2-metric, and the bundle projection is a Riemannian submersion with respect to these metrics. We compute explicit formulae for the sectional curvature of the moduli space in terms of Green operators of the elliptic complex associated with a monopole. Further, we construct a Riemannian metric on the cobordism between moduli spaces for different perturbations. The second construction of a Riemannian metric on the moduli space uses a canonical global gauge fixing, which represents the total space of the Seiberg-Witten bundle as a finite dimensional submanifold of the configuration space.</p> <p>We consider the Seiberg-Witten moduli space on a simply connected K&auml;uhler surface. We show that the moduli space (when nonempty) is a complex projective space, if the perturbation does not admit reducible monpoles, and that the moduli space consists of a single point otherwise. The Seiberg-Witten bundle can then be identified with the Hopf fibration. On the complex projective plane with a special Spin-C structure, our Riemannian metrics on the moduli space are Fubini-Study metrics. Correspondingly, the metrics on the total space of the Seiberg-Witten bundle are Berger metrics. We show that the diameter of the moduli space shrinks to 0 when the perturbation approaches the wall of reducible perturbations. Finally we show, that the quotient L2-metric on the Seiberg-Witten moduli space on a K&auml;hler surface is a K&auml;hler metric.</p> / <p>In dieser Dissertationsschrift geben wir zwei Konstruktionen Riemannscher Metriken auf Seiberg-Witten-Modulr&auml;umen an. Beide Metriken werden in nat&uuml;rlicher Weise durch die L2-Metrik des Konfiguartionsraumes induziert. Die Konstruktion der sogenannten Quotienten-L2-Metrik entspricht der durch Groisser und Parker angegebenen Konstruktion einer L2-Metrik auf Yang-Mills-Modulr&auml;umen. Zur Konstruktion einer Quotienten-Metrik auf dem Totalraum des Seiberg-Witten-B&uuml;ndels f&uuml;hren wir die sogenannte reduzierte Eichgruppe ein. Wir zeigen, dass der Quotient des Pr&auml;modulraumes nach der reduzierten Eichgruppe als U(1)-B&uuml;ndel isomorph ist zu dem Quotienten nach der basierten Eichgruppe. Dadurch tr&auml;gt der Totalraum des Seiberg-Witten B&uuml;ndels eine nat&uuml;rliche Quotienten-L2-Metrik, bzgl. derer die B&uuml;ndelprojektion eine Riemannsche Submersion ist. Wir berechnen explizite Formeln f&uuml;r die Schnittr&uuml;mmung des Modulraumes in Ausdr&uuml;cken der Green-Operatoren des zu einem Monopol geh&ouml;rigen elliptischen Komplexes. Ferner konstruieren wir eine Riemannsche Metrik auf dem Kobordismus zwischen Modulr&auml;umen zu verschiedenen St&ouml;rungen. Die zweite Konstruktion einer Riemannschen Metrik auf Seiberg-Witten-Modulr&auml;umen benutzt eine kanonische globale Eichfixierung, verm&ouml;ge derer der Totalraum des Seiberg-Witten-B&uuml;ndels als endlich-dimensionale Untermannigfaltigkeit des Konfigurationsraumes dargestellt werden kann.</p> <p>Wir betrachten speziell die Seiberg-Witten-Modulr&auml;ume auf einfach zusammenh&auml;ngenden K&auml;hler-Mannigfaltigkeiten. Wir zeigen, dass der Seiberg-Witten-Modulraum (falls nicht-leer) im irreduziblen Fall ein komplex projektiver Raum its und im reduziblen Fall aus einem einzelnen Punkt besteht. Das Seiberg-Witten-B&uuml;ndel l&auml;&szlig;t sich mit der Hopf-Faserung identifizieren. Die L2-Metrik des Modulraumes auf der komplex projektiven Fl&auml;che CP2 (mit einer speziellen Spin-C-Struktur) ist die Fubini-Study-Metrik; entsprechend sind die Metriken auf dem Totalraum Berger-Metriken. Wir zeigen, dass der Durchmesser des Modulraumes gegen 0 konvergiert, wenn die St&ouml;rung sich dem reduziblen Fall n&auml;hert. Schlie&szlig;lich zeigen wir, dass die Quotienten-L2-Metrik auf dem Seiberg-Witten-Modulraum einer K&auml;hlerfl&auml;che eine K&auml;hler-Metrik ist.</p>

In 1989 Jun Kigami made an analytic construction of a Laplacian on the Sierpiński gasket, a construction that he extended to post critically finite fractals. Since then, this field has evolved into a proper theory of analysis on fractals. The new results obtained in this thesis are all in the setting of Kigami's theory. They are presented in three papers. Strichartz recently showed that there are first order linear differential equations, based on the Laplacian, that are not solvable on the Sierpiński gasket. In the first paper we give a characterization on the polynomial p so that the differential equation p(Δ)u=f is solvable on any open subset of the Sierpiński gasket for any f continuous on that subset. For general p we find the open subsets on which p(Δ)u=f is solvable for any continuous f. In the second paper we describe the infinitesimal geometric behavior of a large class of smooth functions on the Sierpiński gasket in terms of the limit distribution of their local eccentricity, a generalized direction of gradient. The distribution of eccentricities is codified as an infinite dimensional perturbation problem for a suitable iterated function system, which has the limit distribution as an invariant measure. We extend results for harmonic functions found by Öberg, Strichartz and Yingst to larger classes of functions. In the third paper we define and study intrinsic first order derivatives on post critically finite fractals and prove differentiability almost everywhere for certain classes of fractals and functions. We apply our results to extend the geography is destiny principle, and also obtain results on the pointwise behavior of local eccentricities. Our main tool is the Furstenberg-Kesten theory of products of random matrices.

This thesis is divided into two parts. Part I deals with demand management. For goods with no substitutes, under supply constraints, fairness considerations introduce negative externalities and lead to a market failure. One example of such a good with no substitutes is water. In case of a market failure, it is necessary to design coordination mechanisms called contracts which provide the right incentives for coordination. As “repetition can yield coordination”, the aim in this part is to design price based dynamic demand management contracts which, under supply constraints, mitigate the market failure. In these contracts, we consider complete information settings; and use the status quo proposition as a fairness criterion for designing them. The contracts are designed as almost noncooperative dynamic games, within the agency theory framework, where the agent (the consumer) is induced to consume at a specified consumption level based on the incentive mechanism offered by the principal (the producer). These contracts use the solution concept of sub-game perfect Nash equilibrium (SPNE) to compute the price (mal-incentive) that acts as a credible threat for deviation from the specified consumption level. In these contracts, unlike the dynamic contracts with asymmetric information, the penalty for deviation is proportional to the amount of deviation. First, we consider a two-period demand management contract for a single consumer satisfying the status quo proposition. Under the assumption that the gain to the consumer and the loss to the producer by deviation is small, the contract is shown to be economically efficient. It is shown that, in the finite horizon, a fair demand management contract cannot be efficient. The demand management contract is homeomorphic to finite horizon alternating bargaining model. In the finite horizon alternating bargaining model, there is a unique SPNE, in which the player who offers last is always at an advantageous position. In the two-period contract, the assumption considered attenuates the last mover advantage and leads to the efficiency. We have shown that one possible way to achieve efficiency, without the assumption, is to make the agents uncertain about the period of interaction. This possibility can be included in an infinite horizon contract. Hence, next, we design an infinite horizon contract for a single consumer. It is proved that this contract is economically efficient and provides revenue sufficiency. The sensitivity analysis of the contract shows that the discounting rate measures the aversion to conservation characteristics of the consumer. The analysis of the contract shows that a sufficiently time-patient consumer is not penalized for the deviation, as the consumer himself is aware of conservation requirements. This result is similar to the results for the present-biased preferences in behavioral economics. Lastly, the infinite horizon contract is extended to two consumers case which internalizes the externality a consumer causes to another. In the two consumer case, consumers are strategically noninteracting; and it is shown that the producer acts as a budget balancer. These contracts are also shown to be economically efficient. The demand management contracts achieve both the procedural and end-state fairness. Also, the infinite horizon contracts are homeomorphic to infinite horizon alternating bargaining model. The efficiency of infinite horizon contracts is due to their homeomorphism with the alternating bargaining process as they exhaust all possible mutual gains from exchange. In the two-period model, the bargaining process is constrained and hence all possible mutual gains are not eliminated, leading to the inefficiency. In part II of the thesis, we discuss the notions of exchangeability in the Shapley value. The Shapley value is a probabilistic value for the transferable utility (TU) cooperative games, in which each player subjectively assigns probabilities to the events which define their positions in the game. In this part, the objective have been to explore the aspect of subjective probability which leads to the uniqueness of the Shapley value. This aspect of subjective probability is known as exchangeability. We derive the Shapley value using de Finetti’s theorem. We also show that, in the Shapley value, each player’s prospects of joining a t-player game as the last member of the game is a moment sequence of the uniquely determined uniform distribution. We stress on finite exchangeability; and deduce that, with finite exchangeability, the Shapley value is the only value in which the probability assignment is a unique mixture of independent and identical distributions. It is concluded that, in both the finite and infinite exchangeable cases, the uniqueness of probability assignment in the Shapley value is due to exchangeability and the mixing with the uniform distribution.

This dissertation investigates the learning scenarios where a high-dimensional parameter has to be estimated from a given sample of fixed size, often smaller than the dimension of the problem. The first part answers some open questions for the binary classification problem in the framework of active learning. Given a random couple (X,Y) with unknown distribution P, the goal of binary classification is to predict a label Y based on the observation X. Prediction rule is constructed from a sequence of observations sampled from P. The concept of active learning can be informally characterized as follows: on every iteration, the algorithm is allowed to request a label Y for any instance X which it considers to be the most informative. The contribution of this work consists of two parts: first, we provide the minimax lower bounds for the performance of active learning methods. Second, we propose an active learning algorithm which attains nearly optimal rates over a broad class of underlying distributions and is adaptive with respect to the unknown parameters of the problem. The second part of this thesis is related to sparse recovery in the framework of dictionary learning. Let (X,Y) be a random couple with unknown distribution P. Given a collection of functions H, the goal of dictionary learning is to construct a prediction rule for Y given by a linear combination of the elements of H. The problem is sparse if there exists a good prediction rule that depends on a small number of functions from H. We propose an estimator of the unknown optimal prediction rule based on penalized empirical risk minimization algorithm. We show that the proposed estimator is able to take advantage of the possible sparse structure of the problem by providing probabilistic bounds for its performance.