Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006. / Includes bibliographical references (leaves 73-75). / In this thesis, we use a semidefinite relaxation based branch-and-bound method to solve nonconvex quadratic programming problems. Firstly, we show an interval branch-and-bound method to calculate the bounds for the minimum of bounded polynomials. Then we demonstrate four SDP relaxation methods to solve nonconvex Box constrained Quadratic Programming (BoxQP) problems and the comparison of the four methods. For some lower dimensional problems, SDP relaxation methods can achieve tight bounds for the BoxQP problem; whereas for higher dimensional cases (more than 20 dimensions), the bounds achieved by the four Semidefinite programming (SDP) relaxation methods are always loose. To achieve tight bounds for higher dimensional BoxQP problems, we combine the branch-and-bound method and SDP relaxation method to develop an SDP relaxation based branch-and-bound (SDPBB) method. We introduce a sensitivity analysis method for the branching process of SDPBB. This sensitivity analysis method can improve the convergence speed significantly. / (cont.) Compared to the interval branch-and-bound method and the global optimization software BARON, SDPBB can achieve better bounds and is also much more efficient. Additionally, we have developed a multisection algorithm for SDPBB and the multisection algorithm has been parallelized using Message Passing Interface (MPI). By parallelizing the program, we can significantly improve the speed of solving higher dimensional BoxQP problems. / by Sha Hu. / S.M.

Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2019 / Cataloged from PDF version of thesis. / Includes bibliographical references. / Machine-Learning Interatomic Force-Fields have shown great promise in increasing time- and length-scales in atomistic simulations while retaining the high accuracy of the reference calculations that they are trained on. Most proposed models aim to learn the potential energy surface of a system of atoms as a function of atomic coordinates and species and obtain the forces acting on the atoms as the negative of the gradient of the global energy with respect to the atomic positions. For the time evolution of an atomistic system in molecular dynamics, however, only atomic forces are required. This thesis examines the construction of a direct approach for learning atomic forces, thereby bypassing the need for learning an energy-based model. Predicting atomic forces directly requires the careful consideration of incorporating the symmetries of 3D space into the model. The construction of an efficient, direct, and symmetry-preserving deep learning model that can predict atomic forces in a fully end-to-end fashion is shown. The model's accuracy, its computational efficiency for training as well as its computational efficiency at time of prediction are evaluated. Finally, the approach is used in the simulation of different small organic molecules and the resulting Molecular Dynamics simulations are analyzed. / by Simon Lutz Batzner. / S.M. / S.M. Massachusetts Institute of Technology, Computation for Design and Optimization Program

Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2018 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 67-68). / The traditional supply chain performance depends on the efficiency of mass production, the availability of productive low cost labor and the geometry and materials of the products. Additive manufacturing, on the other hand, bypasses all these constraints and reduces the number of stages in the supply chain by allowing local production of low volume parts of greater complexity. We develop an approach for assessing the total cost when additive manufacturing is integrated into the service-parts supply chain given a set of inputs that characterize the supply chain. Specifically, we present several simulation and optimization models to help companies decide the end-of-life strategy of low volume service parts. Through sensitivity analysis, we identify regions of parameters where additive manufacturing is preferred. Moreover, we find that service parts with high lost sales unit cost and low fixed and variable additive manufacturing costs are the most suitable for additive manufacturing. / by Yijin Wei. / S.M. / S.M. Massachusetts Institute of Technology, Computation for Design and Optimization Program

Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2018 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 73-77). / A modern city generates a large volume of digital information, especially in the form of unstructured image and video data. Recent advancements in deep learning techniques have enabled effective learning and estimation of high-level attributes and meaningful features from large digital datasets of images and videos. In my thesis, I explore the potential of applying deep learning to image and video data to quantify urban tree cover and street parking utilization. Large-scale and accurate quantification of urban tree cover is important towards informing government agencies in their public greenery efforts, and useful for modelling and analyzing city ecology and urban heat island effects. We apply state-of-the-art deep learning models, and compare their performance to a previously established benchmark of an unsupervised method. / Our training procedure for deep learning models is novel; we utilize the abundance of openly available and similarly labelled street-level image datasets to pre-train our model. We then perform additional training on a small training dataset consisting of GSV images. We also employ a recently developed method called gradient-weighted class activation map (Grad-CAM) to interpret the features learned by the end-to-end model. The results demonstrate that deep learning models are highly accurate, can be interpretable, and can also be efficient in terms of data-labelling effort and computational resources. Accurate parking quantification would inform developers and municipalities in space allocation and design, while real-time measurements would provide drivers and parking enforcement with information that saves time and resources. We propose an accurate and real-time video system for future Internet of Things (IoT) and smart cities applications. / Using recent developments in deep convolutional neural networks (DCNNs) and a novel intelligent vehicle tracking filter, the proposed system combines information across multiple image frames in a video sequence to remove noise introduced by occlusions and detection failures. We demonstrate that the proposed system achieves higher accuracy than pure image-based instance segmentation, and is comparable in performance to industry benchmark systems that utilize more expensive sensors such as radar. Furthermore, the proposed system can be easily configured for deployment in different parking scenarios, and can provide spatial information beyond traditional binary occupancy statistics. / by Bill Yang Cai. / S.M. / S.M. Massachusetts Institute of Technology, Computation for Design and Optimization Program

Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2018 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 89-92). / Cities are home to more than half of the world population today and urbanization is one of this century's biggest drivers of global economic growth. The dynamics of the urban environment is thus an important question to investigate. In this thesis, techniques from statistical modeling, machine learning, data mining and econometrics are utilized to study digital traces of people's everyday lives. In particular, we investigated how people influence the economic growth of cities, as well as how the urban environment affect the decisions made by people. Focusing on the role of cities as centers of consumption, we found that a gravity model based on the availability of a large and diverse pool of amenities accurately explained human flows observed from credit card records. Investigation of the consumption patterns of individuals in Istanbul, Beijing and various metropolitan areas in the United States revealed a positive relationship between the diversity of urban amenities consumed and the city's economic growth. Taking the perspective of cities as hubs for information exchange, we modeled the interactions between individuals in the cities of Beijing and Istanbul using records of their home and work locations and demonstrated how cities which facilitate the mixing of diverse human capital are crucial to the flow of new ideas across communities and their productivity. This contributes to the body of evidence which supports the notion that efficient information exchange is the key factor that drives innovation. To investigate how urban environments shape people's decisions, we study the social influence city dwellers have on each other and showed how face-to-face interaction and information exchange across different residential communities can shape their behavior and increase the similarity of their financial habits and political views in Istanbul. / by Shi Kai Chong. / S.M. / S.M. Massachusetts Institute of Technology, Computation for Design and Optimization Program

In this dissertation we analyse the dark matter substructure dynamics within a series of high-resolution cosmological galaxy clusters simulations generated with the N-body code MLAPM. Two new halo finding algorithms were designed to aid in this analysis. The first of these was the 'MLAPM-halo-nder' (MHF), built upon the adaptive grid structure of MLAPM. The second was the 'MLAPM-halo-tracker' (MHT), an extension of MHF which allowed the tracking of orbital characteristics of gravitationally bound objects through any given cosmological N-body-simulation. Using these codes we followed the time evolution of hundreds of satellite galaxies within the simulated clusters. These clusters were chosen to sample a variety of formation histories, ages, and triaxialities; despite their obvious differences, we and striking similarities within the associated substructure populations. Namely, the radial distribution of these substructure satellites follows a 'universal' radial distribution irrespective of the host halo's environment and formation history. Further, this universal substructure profile is anti-biased with respect to the underlying dark matter profile. All satellite orbits follow nearly the same eccentricity distribution with a correlation between eccentricity and pericentre. The destruction rate of the substructure population is nearly independent of the mass, age, and triaxiality of the host halo. There are, however, subtle differences in the velocity anisotropy of the satellite distribution. We nd that the local velocity bias at all radii is greater than unity for all halos and this increases as we move closer to the halo centre, where it varies from 1.1 to 1.4. For the global velocity bias we nd a small but slightly positive bias, although when we restrict the global velocity bias calculation to satellites that have had at least one orbit, the bias is essentially removed. Following this general analysis we focused on three specific questions regarding the evolution of substructures within dark matter halos. Observations of the Virgo and Coma clusters have shown that their galaxies align with the principal axis of the cluster. Further, a recent statistical analysis of some 300 Abell clusters conrm this alignment, linking it to the dynamical state of the cluster. Within our simulations the apocentres of the satellite orbits are preferentially found within a cone of opening angle 40 degrees around the major axis of the host halo, in accordance with the observed anisotropy found in galaxy clusters. We do, however, note that a link to the dynamical age of the cluster is not well established. Further analysis connects this distribution to the infall pattern of satellites along the filaments, rather than some 'dynamical selection' during their life within the host's virial radius. We then focused our attention on the outskirts of clusters investigating the socalled 'backsplash population', i.e. satellite galaxies that once were inside the virial radius of the host but now reside beyond it. We and that this population is significant in number and needs to be appreciated when interpreting empirical galaxy morphology-environmental relationships and decoupling the degeneracy between nature and nurture. Specifically, we and that approximately half of the galaxies with current clustercentric distance in the interval 1- 2 virial radii of the host are backsplash galaxies which once penetrated deep into the cluster potential, with 90% of these entering to within 50% of the virial radius. These galaxies have undergone significant tidal disruption, losing on average 40% of their mass. This results in a mass function for the backsplash population different to those galaxies infalling for the first time. We further show that these two populations are kinematically distinct and should be observable spectroscopically. Finally we present a detailed study of the real and integrals-of-motion space distributions of a disrupting satellite obtained from one of our self-consistent highresolution cosmological simulations. The satellite has been re-simulated using various analytical halo potentials and we and that its debris appears as a coherent structure in integrals-of-motion space in all models ('live' and analytical potential) although the distribution is significantly smeared for the live host halo. The primary mechanism for the dispersion is the mass growth of the host. However, when quantitatively comparing the effects of 'live' and time-varying host potentials we conclude that not all of the dispersion can be accounted for by the steady growth of the host's mass. We ascribe the remaining differences to additional effects in the 'live' halo such as non-sphericity of the host and interactions with other satellites, which have not been modelled analytically.

The vertebrate retina, which provides the visual input to the brain and its main interface with the outside world, is a very attractive model system for approaching the question of the information processing role of biological mechanisms of nerve cells. It is as yet impossible to provide a complete circuit diagram of the retina, but it is now possible to identify a few simple computations that the retina performs and to relate them to specific biophysical mechanisms and circuit elements. In this paper we consider three operations carried out by most retinae: amplification, temporal differentiation, and computation of the direction of motion of visual patterns.

One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. Soon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi <i>et. al. </i> [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. I begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. UPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.

Abstract The purpose of this study was to develop mathematical games to assist children in learning addition and subtraction computation. The investigator designed games and experimented through four extra lessons, then studied children¡¦s mathematical learning after the lessons. Participants of this study were second grade children from two elementary schools in Kaohsiung. The experimentation was divided into three phases: pilot phase, first edition phase, and, second edition phase. Data collection and administration included pre-test and post-test; questionnaire of children¡¦s attitude towards mathematics; questionnaire of children¡¦s attitude towards games; record sheets for loan of games; children¡¦s worksheets; learning diaries; researcher¡¦s observation notes; and, researcher¡¦s reflections on design of games. The researcher referred to the above data source, later, evaluated according to the results of experimentation, and completed final revisions. Data analyses and results were three: Design, implementation, and revision. Design. When designing a game, the materials followed that of children¡¦s real life experiences. The characteristics of the four games were: Cooperation, challenge, education, and, chance and luck. Implementation. Children changed from ¡§individual responsibility¡¨ to ¡§co-ordination and cooperation in group¡¨, from ¡§assurance¡¨ to ¡§lack of confidence¡¨, from ¡§marginal participation¡¨ to ¡§eager to play with laughter¡¨, and ¡§no control of shouting¡¨. From the data analyses, children performed well in cognition, attitude, and skills. Revision. The principles of modification were to evaluate games¡¦ strengths and weaknesses, and adjusting games design. The respective revisions were tutoring play, children as key persons, formulating regulations, and, enriching contents. The findings of this study suggested that children benefit from mathematical games and constitute mathematical learning in two-digit number computation. If instructors try hard to design games, be keen in administration, and adjusted games, children will learn through games and result more effective mathematics learning. Finally, it is concluded that the goal of enhancing mathematics learning through games-based instruction as feasible. Key word¡Gmathematics games, addition and subtraction computation

The word problem of a finitely generated group is commonly defined to be a formal language over a finite generating set. The class of finite groups has been characterised as the class of finitely generated groups that have word problem decidable by a finite state automaton. We give a natural generalisation of the notion of word problem from finitely generated groups to finitely generated semigroups by considering relations of strings. We characterise the class of finite semigroups by the class of finitely generated semigroups whose word problem is decidable by finite state automata. We then examine the class of semigroups with word problem decidable by asynchronous two tape finite state automata. Algebraic properties of semigroups in this class are considered, towards an algebraic characterisation. We take the next natural step to further extend the classes of semigroups under consideration to semigroups that have word problem decidable by a finite collection of asynchronous automata working independently. A central tool used in the derivation of structural results are so-called iteration lemmas. We define a hierarchy of the considered classes of semigroups and connect our original results with previous research.