No description available.

<p> Given a point p and d + 1 sets (i.e., colours) of points in dimension d, the Colourful Feasibility Problem is to decide whether there are d + 1 points of different colours containing p in their convex hull; and if yes, find such a point set. The monochrome version of this problem, expressing p as a linear combination of d + 1 points in a set S, can be solved using traditional linear optimization algorithms. The Colourful Feasibility Problem was presented by Bárány and Onn in 1997, and it is still not known if a polynomial-time algorithm exists. The case where we have d colours in dimension d and no restriction on the size of the sets has been shown to be strongly NP-complete through a reduction of 3-SAT. We define the core of a configuration to be the intersection of the convex hulls of each colour. We start from the important subcase that we call Colourful Core Feasibility Problem where we have d + 1 points of each colour, and p in the core. By Bárány's 1982 Colourful Caratheodory Theorem, a solution is guaranteed to exist, and the problem is to exhibit one. This problem is described by Bárány and Onn as "an outstanding problem on the border line between tractable and intractable problems". Besides applications to combinatorics, The Colourful Feasibility Problem models a situation where we want to select a set of points that is both diverse and representative.</p> <p> While we have not found out whether the Colourful Core Feasibility Problem can be solved in polynomial time, our contributions are on both the theoretical and practical performance of algorithms to solve the Colourful Feasibility Problem. The algorithms proposed by Bárány and Onn are essentially geometric, and the complexity guarantees depend crucially on having p inside the core. We consider modifications of these algorithms which update multiple colours at each stage, as well a greedy heuristic where we choose the adjacent simplex of maximum volume in each iteration and a random sampling approach. Our test suite includes unstructured random problems, ill-conditioned problems, problems with a restricted number of solutions and infeasible problems. We conclude that the most robust and nearly fastest algorithm for the Colourful Core Feasibility Problem is the multi-update variant which yields substantial gains over the original ones. Alternative approaches based on nondefinite quadratic optimization problem and positive semidefinite relaxation, and a combinatorial algorithm not depending on having p in the core are also introduced. Finally, we give the first upper bound for the minimal number of colourful simplices containing a core point and the first improvement of the lower bound since Bárány's result in 1982.</p> / Thesis / Master of Science (MSc)

No presente trabalho consideramos homeomorfismos do círculo sem pontos periódicos e com o mesmo número finito de pontos críticos todos de tipo non-flat. Provamos que se existe uma conjugação topológica entre dois destes mapas que leva ponto crítico em ponto crítico, sem necessidade de preservar criticalidades, então dita conjugação é uma transformação quase-simétrica com distorção quase-simétrica local uniformemente limitada. Estes resultados são válidos para qualquer número de rotação irracional e são independentes da natureza das criticalidades dos pontos críticos, de modo que nossos resultados são válidos para toda criticalidade real. / In this work we consider circle homeomorphisms without periodic points and with finite number of critical points all of them being non-flat. We prove that if there exists a topological conjugacy between two of those maps which sends critical point into critical point, which not necessarily preserve criticalities, then this conjugacy is a quasi-symmetric map with quasi-symmetric distortion universally bounded. All these results are valid for any irrational rotation number and are independent of the nature of the criticalities, therefore our results are valid for all real criticalities.

No presente trabalho consideramos homeomorfismos do círculo sem pontos periódicos e com o mesmo número finito de pontos críticos todos de tipo non-flat. Provamos que se existe uma conjugação topológica entre dois destes mapas que leva ponto crítico em ponto crítico, sem necessidade de preservar criticalidades, então dita conjugação é uma transformação quase-simétrica com distorção quase-simétrica local uniformemente limitada. Estes resultados são válidos para qualquer número de rotação irracional e são independentes da natureza das criticalidades dos pontos críticos, de modo que nossos resultados são válidos para toda criticalidade real. / In this work we consider circle homeomorphisms without periodic points and with finite number of critical points all of them being non-flat. We prove that if there exists a topological conjugacy between two of those maps which sends critical point into critical point, which not necessarily preserve criticalities, then this conjugacy is a quasi-symmetric map with quasi-symmetric distortion universally bounded. All these results are valid for any irrational rotation number and are independent of the nature of the criticalities, therefore our results are valid for all real criticalities.

In this paper I investigate properties of square complex matrices of the form Ak, where A is also a complex matrix, and k is a nonnegative integer. I look at several ways of representing Ak. In particular, I present an identity expressing the kth power of the Schur form T of A in terms of the elements of T, which can be used together with the Schur decomposition to provide an expression of Ak. I also explain bounds on the norm of Ak, including some based on the element-based expression of Tk. Finally, I provide a detailed exposition of the most current form of the Kreiss Matrix Theorem.

Power networks are sophisticated dynamical systems whose stable operation is essential to modern society. We study the swing equation for networks and its linearization (LSEN) as a tool for modeling power systems. Nowadays, phasor measurement units (PMUs) are used across power networks to measure the magnitude and phase angle of electric signals. Given the abundant data that PMUs can produce, we study applications of the dynamic mode decomposition (DMD) and Loewner framework to power systems. The matrices that define the LSEN model have a particular structure that is not recovered by DMD. We thus propose a novel variant of DMD, called structure-preserving DMD (SPDMD), that imposes the LSEN structure upon the recovered system. Since the solution of the LSEN can potentially exhibit interesting transient dynamics, we study the transient growth for the exponential matrix related to the LSEN. We follow Godunov's approach to get upper bounds for the transient growth and also analyze the relationship of such bounds with classical bounds based on the spectrum, numerical range, and pseudospectra. We show how Godunov's bounds can be optimized to bound the solution operator at a given time. The Loewner framework provides a tool for identifying a dynamical system from tangential measurements. The singular values of Loewner matrices guide the discovery of the true order of the underlying system. However, these singular values can exhibit rapid decay when the interpolation points are far from the poles of the system. We establish a range of bounds for this decay of singular values and apply this analysis to power systems. / Doctor of Philosophy / Power networks are sophisticated dynamical systems whose stable operation is essential to modern society. We study a mathematical model called the LSEN to understand and recover the dynamics of power networks. The LSEN model defines some matrices that have special structures dictated by the application. We propose a novel method to recover matrices with this desired structure from data. We also study some properties of the solution of the LSEN model related to the exponential of a matrix, connecting classical results with the particular approach that we follow. In the system identification context, we also study bounds on the singular values of Loewner matrices to understand the interplay between the data (measurements of the system) and mathematical artifacts (poles of the system).

This dissertation examines the writings of

Instrumental variables have been used for a long time in the econometrics literature for the identification of the causal effect of one random variable, B, on another, C, in the presence of unobserved confounders. In the classical continuous linear model, the causal effect can be point identified by studying the regression of C on A and B on A, where A is the instrument. An instrument is an instance of a supplementary variable which is not of interest in itself but aids identification of causal effects. The method of instrumental variables is extended here to generalised linear models, for which only bounds on the causal effect can be computed. For the discrete instrumental variable model, bounds have been derived in the literature for the causal effect of B on C in terms of the joint distribution of (A,B,C). Using an approach based on convex polytopes, bounds are computed here in terms of the pairwise (A,B) and (A,C) distributions, in direct analogy to the classic use but without the linearity assumption. The bounding technique is also adapted to instrumental models with stronger and weaker assumptions. The computation produces constraints which can be used to invalidate the model. In the literature, constraints of this type are usually tested by checking whether the relative frequencies satisfy them. This is unsatisfactory from a statistical point of view as it ignores the sampling uncertainty of the data. Given the constraints for a model, a proper likelihood analysis is conducted to develop a significance test for the validity of the instrumental model and a bootstrap algorithm for computing confidence intervals for the causal effect. Applications are presented to illustrate the methods and the advantage of a rigorous statistical approach. The use of covariates and intermediate variables for improving the efficiency of causal estimators is also discussed.

Esta dissertação busca avaliar o comportamento da renda mediana e da desigualdade de rendimentos tratando o problema de seleção, através de uma abordagem ainda não utilizada em estudos semelhantes no Brasil. A metodologia empregada busca tratar o problema de seleção utilizando apenas hipóteses fracas e pautadas em argumentos econômicos, estimando os menores intervalos possíveis para a distribuição de renda da população. Os resultados obtidos mostram que as medianas dos rendimentos potenciais em 2002 e 2004 eram inferiores aos de 1996. Adicionalmente, a desigualdade de renda potencial recuou no Brasil entre 1996 e 2006. / This dissertation aims to evaluate the median income and income inequality behavior treating the selection problem with an approach not yet used in similar studies in Brazil. The present methodology tries to address the selection problem using only weak assumptions based on economic arguments, estimating the smallest possible intervals for the population income distribution. The results show that the mean potential income of 2002 and 2004 was smaller than the one of 1996. Additionally, the potential income inequality in Brazil fell from 1996 to 2006.

Nous nous intéressons dans ce travail à la dynamique des opérateurs de Schrödinger unidimensionnels, discrets, associés à un potentiel sturmien quasi-périodique. Le résultat principal de cette thèse est une borne supérieure pour les exposants de transport qui mesurent la vitesse de propagation du système. Cette borne, valide pour presque tous les potentiels sturmiens, est sous balistique pour une force de couplage suffisante. La validité de la borne est couplée à une condition diophantienne liée au nombre irrationnel qui définit le potentiel. Cette condition est vraie presque sûrement. Nous exhibons par ailleurs un exemple d’irrationnel pour lequel une borne supérieure sous balistique est impossible indépendamment de la force de couplage. Nous faisons l’étude de la dimension fractale du spectre de l’opérateur qui minore sous certaines conditions les exposants de transport. Nous obtenons une nouvelle borne inférieure pour la dimension de boîte du spectre grâce aux propriétés connues sur la forme du pseudo spectre. Les restrictions pour obtenir une borne dynamique à partir de notre résultat sont d’avoir une condition initiale cyclique standard et que le potentiel soit associé à un irrationnel à densité bornée. Enfin dans la dernière partie de ce travail, nous démontrons que le spectre de l’opérateur associé au nombre d’argent ß = [2, 2, . . . ] possède une structure hyperbolique. L’expression du pseudo spectre peut être vu comme un système dynamique. Nous conjuguons ledit système à une dynamique symbolique abstraite selon la méthode dite des partitions de Markov. Le système se comporte comme un fer à cheval de Smale. Nous dérivons de l’hyperbolicité des propriétés pour les dimensions fractales du spectre. Dimensions dont l’attrait dynamique a été rappelé dans la partie précédente. Nous déduisons notamment l’égalité des dimensions de Hausdorff et de boîte pour cet opérateur. / In this thesis, we study the dynamics of discrete, one-dimensional, sturmian Schrödinger operators. The main result is a dynamical bound from above for transport exponents that valuate speed of the wavepacket spreading. This bound is true for almost every sturmian potential and is sub-ballistic for a coupling constant big enough. This bound is valid with respect to a diophantine condition on the irrational number that define the potential. This condition is true for almost every irrational numbers. We show an example of irrational number with ballistic motion at any coupling constant. We study the fractal dimension of the spectrum of these operators which can bound from below, under more restrictive assumptions, transport exponents.We get a new bound from below for the box dimension of the spectrum. Assumptions needed to use this bound on dynamical purpose are the initial condition to be cyclic and the potential associated to a bounded means irrational number. In the last part of the thesis, we show that the spectrum of the operator associated to the so-called silver mean ß = [2, 2, . . . ] has a hyperbolic structure. The spectrum can be express as the non wandering set of a dynamical system. Using Markov partition method, we conjugate its dynamics to a symbolic one. The dynamical system behave like a Smale horseshoe. We derive from hyperbolicity spectral information, especially on fractal dimension. For example, we get that Hausdorff and box dimensions coincide for this operator.