The online and data stream models of computation have recently attracted considerable research attention due to many real-world applications in various areas such as data mining, machine learning, distributed computing, and robotics. In both these models, input items arrive one at a time, and the algorithms must decide based on the partial data received so far, without any secure information about the data that will arrive in the future. In this thesis, we investigate efficient algorithms for a number of fundamental geometric optimization problems in the online and data stream models. The problems studied in this thesis can be divided into two major categories: geometric clustering and computing various extent measures of a set of points. In the online setting, we show that the basic unit clustering problem admits non-trivial algorithms even in the simplest one-dimensional case: we show that the naive upper bounds on the competitive ratio of algorithms for this problem can be beaten using randomization. In the data stream model, we propose a new streaming algorithm for maintaining "core-sets" of a set of points in fixed dimensions, and also, introduce a new simple framework for transforming a class of offline algorithms to their equivalents in the data stream model. These results together lead to improved streaming approximation algorithms for a wide variety of geometric optimization problems in fixed dimensions, including diameter, width, k-center, smallest enclosing ball, minimum-volume bounding box, minimum enclosing cylinder, minimum-width enclosing spherical shell/annulus, etc. In high-dimensional data streams, where the dimension is not a constant, we propose a simple streaming algorithm for the minimum enclosing ball (the 1-center) problem with an improved approximation factor.

Self-adaptive and self-managing systems optimize their own behaviour according to high-level objectives and constraints. One way for human administrators to effectively specify goals for such optimization problems is using policies. Over the past decade, researchers produced various approaches, models and techniques for policy specification in different areas including distributed systems, communication networks, web services, autonomic computing, and cloud computing. Research challenges range from characterizing policies for ease of specification in particular application domains to categorizing policies for achieving good solution qualities for particular algorithmic techniques. The contributions of this thesis are threefold. Firstly, we give a mathematical formulation for each of the three policy types, action, goal and utility function policies, introduced in the policy framework by Kephart and Walsh. In particular, we introduce a first precise characterization of goal policies for optimization problems. Secondly, this thesis introduces a mathematical framework that adds structure to the underlying optimization problem for different types of policies. Structure is added either to the objective function or the constraints of the optimization problem. These mathematical structures, imposed on the underlying problem, progressively increase the quality of the solutions obtained when using the greedy optimization technique. Thirdly, we show the applicability of our framework through case studies by analyzing several optimization problems encountered in self-adaptive and self-managing systems, such as resource allocation, quality of service management, and Service Level Agreement (SLA) profit optimization to provide quality guarantees for their solutions. Our approach combines the algorithmic results by Edmonds, Fisher et al., and Mestre, and the policy framework of Kephart and Walsh. Our characterization and approach will help designers of self-adaptive and self-managing systems formulate optimization problems, decide on algorithmic strategies based on policy requirements, and reason about solution qualities. / Graduate / 0984

Den här rapporten undersöker egenskaper hos en algoritm som är baserad på Learning Backtracking Search Optimization Algorithm (LBSA) som introducerades av Chen et. al. (2017). Undersökningen genomfördes genom att tillämpa algoritmen på Sudokuproblemet och jämföra lösningsgraden och diversiteten i den sista populationen med en algoritm som är baserad på Hybrid Genetic Algorithm (HGA) som introducerades av Deng och Li (2011). Resultaten visar att implementationen av den LBSA-baserade algoritmen har en lägre lösningsgrad än den HGA-baserade algoritmen för alla genomförda experiment, men att algoritmen håller en högre diversitet i den sista populationen för tre av de fem gjorda experimenten. Slutsatsen är att den LBSA-baserade algoritmen inte är lämplig för att lösa Sudokuproblemet på grund av en låg lösningsgrad och att implementationen har en hög komplexitet. / This report examines the properties of an algorithm based on the Learning Backtracking Optimization Algorithm (LBSA) introduced by Chen et. al. (2017). The examination was performed by applying the algorithm on the Sudoku problem and then comparing the solution rate and the diversity in the final population with an algorithm based on the Hybrid Genetic Algorithm introduced by Deng and Li (2011). The results show the implementation of the LBSA based algorithm have a lower solution rate than the HGA based algorithm for all executed experiments. But the LBSA based algorithm manage to keep a higher diversity in the final population in three of the five performed experiments. The conclusion is that the LBSA based algorithm is not suitable for solving the Sudoku problem since the algorithm has a lower solution rate and the implementation have a high complexity.

Many real world problems in science and engineering can be treated as optimization problems with multiple objectives or criteria. The demand for fast and robust stochastic algorithms to cater to the optimization needs is very high. When the cost function for the problem is nonlinear and non-differentiable, direct search approaches are the methods of choice. Many such approaches use the greedy criterion, which is based on accepting the new parameter vector only if it reduces the value of the cost function. This could result in fast convergence, but also in misconvergence where it could lead the vectors to get trapped in local minima. Inherently, parallel search techniques have more exploratory power. These techniques discourage premature convergence and consequently, there are some candidate solution vectors which do not converge to the global minimum solution at any point of time. Rather, they constantly explore the whole search space for other possible solutions. In this thesis, we concentrate on benchmarking three popular algorithms: Real-valued Genetic Algorithm (RGA), Particle Swarm Optimization (PSO), and Differential Evolution (DE). The DE algorithm is found to out-perform the other algorithms in fast convergence and in attaining low-cost function values. The DE algorithm is selected and used to build a model for forecasting auroral oval boundaries during a solar storm event. This is compared against an established model by Feldstein and Starkov. As an extended study, the ability of the DE is further put into test in another example of a nonlinear system study, by using it to study and design phase-locked loop circuits. In particular, the algorithm is used to obtain circuit parameters when frequency steps are applied at the input at particular instances.

No description available.

This is a project with the ambition of demonstrating the possibilities and applications of the quantum approximation optimization algorithm (QAOA). Throughout the paper discussions on the theoretical background and fundamentals of the algorithm will be done by examining the relevant nomenclature. Then a set of possible application problems will be considered where it will be discussed why this specific algorithm is of interest for each individual problem. In the fourth section these problems will concretely be tested via simulations of the QAOA and lastly an analysis of the outcomes will be done.

Submitted by Jean Medeiros (jeanletras@uepb.edu.br) on 2016-09-08T13:54:27Z No. of bitstreams: 1 PDF - Alex Fernandes Mendes.pdf: 2731212 bytes, checksum: 53473c1efa5b616abee7ccdd6fc9236d (MD5) / Approved for entry into archive by Secta BC (secta.csu.bc@uepb.edu.br) on 2016-09-09T18:51:21Z (GMT) No. of bitstreams: 1 PDF - Alex Fernandes Mendes.pdf: 2731212 bytes, checksum: 53473c1efa5b616abee7ccdd6fc9236d (MD5) / Made available in DSpace on 2016-09-09T18:55:06Z (GMT). No. of bitstreams: 1 PDF - Alex Fernandes Mendes.pdf: 2731212 bytes, checksum: 53473c1efa5b616abee7ccdd6fc9236d (MD5) Previous issue date: 2015-12-14 / In this work discuss optimization problems involving polynomial functions of de- gree greater than or equal to 2, where use the rate of variation to obtain the extremes, that can bemaximum orminimum. The proposal is to insert in high school the derived as rate of variation and from there to solve optimization problems, without defining the derivative formally. The problems proposed in this work meets the dynamic in the classroom, concrete problems, with some occurrence in our daily lives, may also include the areas of economics, engineering and physics. / No presente trabalho abordaremos problemas de otimização envolvendo funções polinomiais de grau maior ou igual a 2, onde utilizamos a taxa de variação na obtenção de extremos, que podem ser máximos ou mínimos relativos. A proposta é inserir no ensino médio a derivada como taxa de variação e a partir daí resolver problemas de otimização, sem definir a derivada de maneira formal. Os problemas propostos neste trabalho atende à dinâmica de sala de aula, sendo problemas concretos,com certa ocorrência no nosso cotidiano, podendo ainda abranger as áreas de economia, engenharia e física.

We develop novel numerical methods for optimization problems subject to constraints given by nonlinear hyperbolic systems of conservation and balance laws in one space dimension. These types of control problems arise in a variety of applications, in which inverse problems for the corresponding initial value problems are to be solved. The optimization method can be seen as a block Gauss-Seidel iteration. The optimization requires one to numerically solve the hyperbolic system forward in time and the corresponding linear adjoint system backward in time. We test the optimization method on a number of control problems constrained by nonlinear hyperbolic systems of PDEs with both smooth and discontinuous prescribed terminal states. The theoretical foundation of the introduced scheme is provided in the case of scalar hyperbolic conservation laws on an unbounded domain with a strictly convex flux. In addition, we empirically demonstrate that using a higher-order temporal discretization helps to substantially improve both the efficiency and accuracy of the overall numerical method. / acase@tulane.edu

The 20th century saw the first revolution of quantum mechanics, setting the rules for our understanding of light, matter, and their interaction. The 21st century is focused on using these quantum mechanical laws to develop technologies which allows us to solve challenging practical problems. One of the directions is the use quantum devices which promise to surpass the best computers and best known classical algorithms for solving certain tasks. Crucial to the design of realistic devices and technologies is to account for the open nature of quantum systems and to cope with their interactions with the environment. In the first part of this dissertation, we show how to tackle classical optimization problems of interest in the physical sciences within one of these quantum computing paradigms, known as quantum annealing (QA). We present the largest implementation of QA on a biophysical problem (six different experiments with up to 81 superconducting quantum bits). Although the cases presented here can be solved on a classical computer, we present the first implementation of lattice protein folding on a quantum device under the Miyazawa-Jernigan model. This is the first step towards studying optimization problems in biophysics and statistical mechanics using quantum devices. In the second part of this dissertation, we focus on the problem of excitonic energy transfer. We provide an intuitive platform for engineering exciton transfer dynamics and we show that careful consideration of the properties of the environment leads to opportunities to engineer the transfer of an exciton. Since excitons in nanostructures are proposed for use in quantum information processing and artificial photosynthetic designs, our approach paves the way for engineering a wide range of desired exciton dy- namics. Finally, we develop the theory for a two-dimensional electronic spectroscopic technique based on fluorescence (2DFS) and challenge previous theoretical results claiming its equivalence to the two-dimensional photon echo (2DPE) technique which is based on polarization. Experimental realization of this technique confirms our the- oretical predictions. The new technique is more sensitive than 2DPE as a tool for conformational determination of excitonically coupled chromophores and o↵ers the possibility of applying two-dimensional electronic spectroscopy to single-molecules.

Understanding transcriptional regulation quantitatively is a crucial step towards uncovering and ultimately utilizing the regulatory semantics encoded in the genome. Transcription of a gene is induced by the binding of site-specific transcription factors (TFs) to so-called cis-regulatory-modules (CRMs). The frequency and duration of the binding events are influenced by the concentrations of the TFs, the binding affinities and location of the transcription factor binding sites (TFBSs) in the CRM as well as the properties of the TFs themselves (e.g. effectiveness, competitive interaction with other TFs). Modeling these interactions using a mathematical approach, based on sound biochemical and thermodynamic foundations, enables the understanding and quantitative prediction of transcriptional output of a target gene. In the thesis I introduce the developed framework for modeling, visualizing, and predicting the regulation of the transcription rate of a target gene. Given the concentrations of a set of TFs, the TFBSs in a regulatory DNA region, and the transcription rate of the target gene, the method will optimize its parameters to generate a predictive model that incorporates the regulatory mechanism of the observed gene. I demonstrate the generalization ability of the model by subjecting it to standard machine learning and hypothesis testing procedures. Furthermore, I demonstrate the potential of the approach by training the method on a gene in D. melanogaster and predicting the output of the homologous genes in 12 other Drosophila species where the regulatory sequence has evolved substantially but the regulatory mechanism was conserved. Finally, I investigate the proposed role-switching behaviour of TFs regulating the development of D. melanogaster, which suggests that SUMOylation is the biological mechanism facilitating the switch.