Mathematics
Permanent URI for this communityhttp://hdl.handle.net/1903/2261
Browse
7 results
Search Results
Item Global Optimization of Finite Mixture Models(2007-05-31) Heath, Jeffrey Wells; Fu, Michael; Jank, Wolfgang; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The Expectation-Maximization (EM) algorithm is a popular and convenient tool for the estimation of Gaussian mixture models and its natural extension, model-based clustering. However, while the algorithm is convenient to implement and numerically very stable, it only produces solutions that are locally optimal. Thus, EM may not achieve the globally optimal solution in Gaussian mixture analysis problems, which can have a large number of local optima. This dissertation introduces several new algorithms designed to produce globally optimal solutions for Gaussian mixture models. The building blocks for these algorithms are methods from the operations research literature, namely the Cross-Entropy (CE) method and Model Reference Adaptive Search (MRAS). The new algorithms we propose must efficiently simulate positive definite covariance matrices of the Gaussian mixture components. We propose several new solutions to this problem. One solution is to blend the updating procedure of CE and MRAS with the principles of Expectation-Maximization updating for the covariance matrices, leading to two new algorithms, CE-EM and MRAS-EM. We also propose two additional algorithms, CE-CD and MRAS-CD, which rely on the Cholesky decomposition to construct the random covariance matrices. Numerical experiments illustrate the effectiveness of the proposed algorithms in finding global optima where the classical EM fails to do so. We find that although a single run of the new algorithms may be slower than EM, they have the potential of producing significantly better global solutions to the model-based clustering problem. We also show that the global optimum matters in the sense that it significantly improves the clustering task. Furthermore, we provide a a theoretical proof of global convergence to the optimal solution of the likelihood function of Gaussian mixtures for one of the algorithms, namely MRAS-CD. This offers support that the algorithm is not merely an ad-hoc heuristic, but is systematically designed to produce global solutions to Gaussian mixture models. Finally, we investigate the fitness landscape of Gaussian mixture models and give evidence for why this is a difficult global optimization problem. We discuss different metrics that can be used to evaluate the difficulty of global optimization problems, and then apply them to the context of Gaussian mixture models.Item Extending the Levy Processes to Multiasset Products Pricing(2006-11-27) Xia, Qing; Madan, Dilip B.; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Levy processes have gained great success in pricing single asset options. In this thesis, we introduce a methodology enabling us to extend the single asset pricing technique based on Levy processes to multiasset cases. In our method, we assume the log-return of each asset as a linear sum of independent factors. These factors are driven by the Levy processes, and the specific Levy process we are studying in this thesis is the Variance Gamma (VG) process. We recover these factors by a signal processing technique called independent component analysis (ICA), from which we get the physical measure (P measure). To price the contingent claims, we still need the risk-neutral measure (Q measure). We bridge the gap between physical measure and risk-neutral measure by introducing the transformation of measure between the P measure and the Q measure. We next write each asset as the linear sum of factors under risk-neutral measure. Thus, we may calibrate the measure change parameters simultaneously through individual listed option data. With the measure change parameters (from P measure to Q measure) being recovered, we're able to price multiasset products by doing Monte Carlo simulation. In this thesis, we also explore the possibility of extending Levy processes to multiasset product pricing by applying the copula method. Generally speaking, the copula method enables us to introduce the dependence structure for arbitrary marginal distributions. The probabilistic interpretation of copulas is that we may apply the copula method to write the multivariate distributions for any marginal distributions. We consider examples from two different copula families - the elliptical copula family and Archimedean copula family. We studied Gaussian and Clayton one factor copulas as the examples from these two classes. We calibrated the correlation parameters for both methods and found them inconsistent across different strikes and maturities. And like the volatility smile and skew in the Black-Scholes model, we call it the skew and smile effect of correlation for one factor copula method.Item Weakly Compressible Navier-Stokes Approximation of Gas Dynamics(2006-08-07) Jiang, Ning; Levermore, Charles David; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation addresses mathematical issues regarding weakly compressible approximations of gas dynamics that arise both in fluid dynamical and in kinetic settings. These approximations are derived in regimes in which (1) transport coefficients (viscosity and thermal conductivity) are small and (2) the gas is near an absolute equilibrium --- a spatially uniform, stationary state. When we consider regimes in which both the transport scales and $\mathrm{Re}$ vanish, we derive the {\em weakly compressible Stokes approximation} --- a {\em linear} system. When we consider regimes in which the transport scales vanish while $\mathrm{Re}$ maintains order unity, we derive the {\em weakly compressible Navier-Stokes approximation}---a {\em quadratic} system. Each of these weakly compressible approximations govern both the acoustic and the incompressible modes of the gas. In the fluid dynamical setting, our derivations begin with the fully compressible Navier-Stokes system. We show that the structure of the weakly compressible Navier-Stokes system ensures that it has global weak solutions, thereby extending the Leray theory for the incompressible Navier-Stokes system. Indeed, we show that this is the case in a general setting of hyperbolic-parabolic systems that possess an entropy under a structure condition (which is satisfied by the compressible Navier-Stokes system.) Moreover, we obtain a regularity result for the acoustic modes for the weakly compressible Navier-Stokes system. In the kinetic setting, our derivations begin with the Boltzmann equation. Our work extends earlier derivations of the incompressible Navier-Stokes system by the inclusion of the acoustic modes. We study the validity of these approximations in the setting of the DiPerna-Lions global solutions. Assuming that DiPerna-Lions solutions satisfy the local conservation law of energy, we use a relative entropy method to justify the weakly compressible Stokes approximation which unifies the Acoustic-Stokes limits result of Golse-Levermore, and to justify the weakly compressible Navier-Stokes approximation modulo further assumptions about passing to the limit in certain relative entropy dissipation terms. This last result extends the result of Golse-Levermore--Saint-Raymond for the incompressible Navier-Stokes system.Item The Performance of Multivariate Quality-Control Charts for Autocorrelated Bivariate Data(2006-06-02) Wu, Chen-Hsiang; Zantek, Paul; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)To monitor the mass production process, several quality control charts are constructed. Two of the most recognized schemes are the multivariate exponentially weighted moving average (MEWMA) and multivariate cumulative sum (MCUSUM) schemes. Originally, we assume that the observations from the production process are independent. However, sometimes the observations are autocorrelated. In this article, a vector autoregressive model VAR (m) is applied. Here we want to study the impact of autocorrelations on both schemes. We also want to know about which scheme is more efficient when the observations are autocorrelated.Item TRAVELING WAVE SOLUTIONS FOR A COMBUSTION MODEL(2005-05-04) Davis, Brian M; Trivisa, Konstantina; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)From the compressible Navier-Stokes equations for a reacting mixture, we reduce the system to obtain a one-dimensional 2-species polytropic gas combustion model. We examine the equilibria and determine their stability as well as identify the conditions that provide for the existence and uniqueness of a traveling wave/shock layer solution.Item discrete optimization models in data visualization(2004-11-12) Abbiw-Jackson, Roselyn Mansa; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Data visualization techniques have become important tools for analyzing large multidimensional data sets and providing insights with respect to scientific, economic, and engineering applications. Typically, these visualization applications are modeled and solved using nonlinear optimization techniques. In this dissertation, we propose a discretization of the data visualization problem that allows us to formulate it as a quadratic assignment problem. This formulation is computationally difficult to solve optimally using an exact approach. Consequently, we investigate the use of local search techniques, mathematical programming, and genetic algorithms for the data visualization problem. The space in which the data points are to be embedded can be discretized using an n x n lattice. Conducting a search on this n x n lattice is computationally ineffective. Consequently, we propose a divide-and-conquer approach that refines the lattice at each step. We show that this approach is much faster than conducting a search of the entire n x n lattice and, in general, it generates higher quality solutions. We envision two uses of our divide-and-conquer heuristics: (1) as stand-alone approaches for data visualization and (2) to provide good approximate starting solutions for a nonlinear algorithm.Item EXPRESSING PREFERENCES WITH PRICE-VECTOR AGENTS IN COMBINATORIAL AUCTIONS(2004-08-12) Day, Robert Warren; Raghavan, Subramanian; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this work, we investigate two combinatorial auction formats in which each bidding bidder may be represented by a collection of unit-demand or price-vector agents. In the first model, bidder preferences are aggregated in a Bid Table, through which a bidder in a combinatorial auction may express several forms of subadditive preferences. We show that the gross substitutes property holds for this model, and design a large-scale combinatorial auction using bid tables as a demand revelation stage, determining linear price signals for later stages. The constraints of this model coincide naturally with the restrictions of recently proposed FAA landing-slot auctions, and we provide a slot auction design based on this model. In a second model, we explore the more complex behavior possible when each bidder's collection of price-vector agents coordinate based on a bidder-specified ordering of the auction items. With this coordination each bidder is able to convey a rich set of preferences, including the ability to express both superadditive and subadditive bundle synergies (i.e., substitutes and complements). The instructions for this collection of agents are tabulated in a lower-triangular Matrix Bid, and we compare the use of matrix bids to other compact techniques for writing down a wide variety of bidding information. We show that the winner determination problem for this Matrix Bid Auction is NP-hard, provide results from a series of computational experiments, and develop IP techniques for improving run time. In addition to the results on price-vector agents, bid tables, and matrix bidding, we present a new technique for achieving bidder-Pareto-optimal core outcomes in a sealed-bid combinatorial auction. The key idea of this iterative procedure is the formulation of the separation problem for core constraints at an arbitrary point in winner payment space.