Note:

No description available.

A Markov Decision Process (MDP) is a model employed to describe problems in which a decision must be made at each one of several stages, while receiving feedback from the environment. This type of model has been extensively studied in the operations research community and fundamental algorithms have been developed to solve associated problems. However, these algorithms are quite inefficient for very large problems, leading to a need for alternatives; since MDP problems are provably hard on compressed representations, one becomes content even with algorithms which may perform well at least on specific classes of problems. The class of problems we deal with in this thesis allows succinct representations for the MDP as a dynamic Bayes network, and for its solution as a weighted combination of basis functions. We develop novel algorithms for producing, improving, and calculating the error of approximate solutions for MDPs using a compressed representation. Specifically, we develop an efficient branch-and-bound algorithm for computing the Bellman error of the compact approximate solution regardless of its provenance. We introduce an efficient direct linear programming algorithm which, using incremental constraints generation, achieves run times significantly smaller than existing approximate algorithms without much loss of accuracy. We also show a novel direct linear programming algorithm which, instead of employing constraints generation, transforms the exponentially many constraints into a compact form more amenable for tractable solutions. In spite of its perceived importance, the efficient optimization of the Bellman error towards an approximate MDP solution has eluded current algorithms; to this end we propose a novel branch-and-bound approximate policy iteration algorithm which makes direct use of our branch-and-bound method for computing the Bellman error. We further investigate another procedure for obtaining an approximate solution based on the dual of the direct, approximate linear programming formulation for solving MDPs. To address both the loss of accuracy resulting from the direct, approximate linear program solution and the question of where basis functions come from we also develop a principled system able not only to produce the initial set of basis functions, but also able to augment it with new basis functions automatically generated such that the approximation error decreases according to the user's requirements and time limitations.

A Markov Decision Process (MDP) is a model employed to describe problems in which a decision must be made at each one of several stages, while receiving feedback from the environment. This type of model has been extensively studied in the operations research community and fundamental algorithms have been developed to solve associated problems. However, these algorithms are quite inefficient for very large problems, leading to a need for alternatives; since MDP problems are provably hard on compressed representations, one becomes content even with algorithms which may perform well at least on specific classes of problems. The class of problems we deal with in this thesis allows succinct representations for the MDP as a dynamic Bayes network, and for its solution as a weighted combination of basis functions. We develop novel algorithms for producing, improving, and calculating the error of approximate solutions for MDPs using a compressed representation. Specifically, we develop an efficient branch-and-bound algorithm for computing the Bellman error of the compact approximate solution regardless of its provenance. We introduce an efficient direct linear programming algorithm which, using incremental constraints generation, achieves run times significantly smaller than existing approximate algorithms without much loss of accuracy. We also show a novel direct linear programming algorithm which, instead of employing constraints generation, transforms the exponentially many constraints into a compact form more amenable for tractable solutions. In spite of its perceived importance, the efficient optimization of the Bellman error towards an approximate MDP solution has eluded current algorithms; to this end we propose a novel branch-and-bound approximate policy iteration algorithm which makes direct use of our branch-and-bound method for computing the Bellman error. We further investigate another procedure for obtaining an approximate solution based on the dual of the direct, approximate linear programming formulation for solving MDPs. To address both the loss of accuracy resulting from the direct, approximate linear program solution and the question of where basis functions come from we also develop a principled system able not only to produce the initial set of basis functions, but also able to augment it with new basis functions automatically generated such that the approximation error decreases according to the user's requirements and time limitations.

The quadratic assignment problem (QAP) is known to be one of the most computationally difficult combinatorial problems. Optimally solvable instances of the QAP remain of size n ≤ 40 with heuristics used to solve instances in the range 40 ≤ n ≤ 256. In this thesis we develop a local optimization algorithm called GradSwaps (GS). GS uses the first-order Taylor approximation (FOA) to efficiently determine improving swaps in the solution. We use GS to locally optimize instances of the QAP of size 1000 ≤ n ≤ 70000 where the data matrices are given in factored form, enabling efficient computations. We give theoretical background and justification for using the FOA and bound the error inherent in the approximation. A strategy for extending GS to larger scale QAPs using blocks of indices is described in detail. Three novel large-scale applications of the QAP are developed. First, a strategy for data visualization using an extreme learning machine (ELM) where the quality of the visualization is measured in the original data space instead of the projected space. Second, a version of the traveling salesperson problem (TSP) with the squared Euclidean distance metric; this distance metric allows the factorization of the data matrix, a key component for using GS. Third, a method for generating random data with designated distribution and correlation to an accuracy surpassing traditional techniques.

abstract: Global optimization (programming) has been attracting the attention of researchers for almost a century. Since linear programming (LP) and mixed integer linear programming (MILP) had been well studied in early stages, MILP methods and software tools had improved in their efficiency in the past few years. They are now fast and robust even for problems with millions of variables. Therefore, it is desirable to use MILP software to solve mixed integer nonlinear programming (MINLP) problems. For an MINLP problem to be solved by an MILP solver, its nonlinear functions must be transformed to linear ones. The most common method to do the transformation is the piecewise linear approximation (PLA). This dissertation will summarize the types of optimization and the most important tools and methods, and will discuss in depth the PLA tool. PLA will be done using nonuniform partitioning of the domain of the variables involved in the function that will be approximated. Also partial PLA models that approximate only parts of a complicated optimization problem will be introduced. Computational experiments will be done and the results will show that nonuniform partitioning and partial PLA can be beneficial. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2020

This work focuses on the construction of functional representations in high-dimensional spaces.Attention is focused on the modeling of ignition phenomena using detailed kinetics, and on the ignition delay time as the primary quantity of interest (QoI). An iso-octane air mixture is first considered, using a detailed chemical mechanism with 3,811 elementary reactions. Uncertainty in all reaction rates is directly accounted for using associated uncertainty factors, assuming independent log-uniform priors. A Latin hypercube sample (LHS) of the ignition delay times was first generated, and the resulting database was then exploited to assess the possibility of constructing polynomial chaos (PC) representations in terms of the canonical random variables parametrizing the uncertain rates. We explored two avenues, namely sparse regression (SR) using LASSO, and a coordinate transform (CT) approach. Preconditioned variants of both approaches were also considered, namely using the logarithm of the ignition delay time as QoI. A global sensitivity analysis is performed using the representations constructed by SR and CT. Next, the tangent linear approximation is developed to estimate the sensitivity of the ignition delay time with respect to individual rate parameters in a detailed chemical mechanism. Attention is focused on a gas mixture reacting under adiabatic, constant-volume conditions. The approach is based on integrating the linearized system of equations governing the evolution of the partial derivatives of the state vector with respect to individual random variables, and a linearized approximation is developed to relate the ignition delay sensitivity to the scaled partial derivatives of temperature. In particular, the computations indicate that for detailed reaction mechanisms the TLA leads to robust local sensitivity predictions at a computational cost that is order-of-magnitude smaller than that incurred by finite-difference approaches based on one-at-a-time rate parameters perturbations. In the last part, we explore the potential of utilizing TLA-based sensitivities to identify active subspace and to construct suitable representations. Performance is assessed based contrasting experiences with CT-based machinery developed earlier.

This dissertations represents a composite of three papers which have been submitted for publication: The first chapter deals with a non-convex knapsack which is inspired by a simplified political districting problem. We present and derive a constant time solution to the problem via a reduced-dimensional reformulation, the Karash-Kuhn-Tucker optimality conditions, and gradient descent. The second chapter covers a more complete form of the political districting problem. We attempt to overcome the non-convex objective function and combinatorially massive solution space through a variety of linearization techniques and cutting planes. Our focus on dual bounds is novel in the space. The final chapter develops a framework for identifying ideal mixed binary linear programs and applies it to several rectangle packing formulations. These include both existing and novel formulations for the underlying disjunctive program. Additionally, we investigate the poor performance of branch-and-cut on the example problems. / Doctor of Philosophy / This dissertation is made up of three papers dealing with two problems: Political Districting (the process of partitioning land into voting districts for United States Congressional Representatives) and Rectangle Packing (the process of fitting rectangular objects onto a floorspace in some efficient or optimal manner). Both problems receive thorough descriptions in their respective chapters. Rather than generating real, usable solutions, our focus for the districting problem is on producing upper bounds against which the myriad existing solutions can be compared. This is useful in evaluating whether or not said solutions fairly represent the voting populous of a state. The first chapter deals with the difficulty of political districting by reducing the space of solutions; rather than assigning discrete tracts of land to districts, we assign individual voters. We present two fast methods for solving this reduced problem and achieving viable upper bounds. The second chapter covers a more complete form of the political districting problem as we attempt to overcome the difficulty associated with the objective function rather than the solution space. We propose a variety of techniques for efficiently approximating said function within exiting optimization frameworks and perform a number of experiments to demonstrate their effectiveness. The final chapter shifts focus to the rectangle packing problem described above. This problem is most naturally given as a Disjunctive Program (an optimization problem which requires `or' statements to properly describe). The approximation schemes given in Chapter 2 can also be accurately described as disjunctive programs, so some of the same techniques apply. There exist several good methods for formulating this problem, but we seek to establish a theoretical aspect of these methods. We say that a model is Ideal if any integer requirements can be safely ignored without destroying the solution; Chapter 3 develops a framework for identifying ideal formulations and uses it to prove and correct the idealness of existing methods.

The Global System for Mobile (GSM) Communication is the most widely used cellular technology. The privacy has been protected using some version of stream ciphers until the 3rd Generation of GSM. KASUMI, a block cipher, has been chosen as a standard algorithm in order to be used in 3rd Generation. In this thesis, s-boxes of KASUMI, MISTY1 (former version of KASUMI) and RIJNDAEL (the Advanced Encryption Standard) are evaluated according to their linear approximation tables, XOR table distributions and satisfaction of the strict avalanche criterion (SAC). Then, the nonlinear part, FI function, of KASUMI and MISTY1 are investigated for SAC. A new FI function is defined by replacing both s-boxes of KASUMI by RIJNDAEL&rsquo / s s-box. Calling this new version KASUMI-R, it is found to have an FI function significantly better than others. Finally, the randomness characteristics of the overall KASUMI-R for different rounds are compared to those of MISTY1 and KASUMI, in terms of avalanche weight distribution (AWD) and some statistical tests. The overall performance of the three ciphers is found to be same, although there is a significant difference in their FI functions.

I here present a combined AVO analysis of P-P and P-S reflection data whose objective is to improve the identification of lithology by estimating the specific values of Poisson's ratio, [sigma], for each rock formation in a given geological model, rather than a contrast between formations. Limited knowledge on the elastic parameters of a given rock formation and difficulty regarding the availability and processing of P-S data constitute hindrances of lithology identification. Considering that ocean bottom seismology (OBS) has aided in solving the problem of P-S data availability, limited information on elastic parameters is still a challenge, and the focus of this thesis. The present analysis is based on Zoeppritz' solution for the P-P and P-S reflection coefficients, RPP and RPS, with a slight modification. We used the normalized P-S reflection coefficient; i.e., R'PS = RPS / sin [theta] for [theta] > 0, instead of RPS, where [theta] is the incident angle. By normalizing RPS, we avoid dealing with the absence of converted S-waves at small incident angles and enhance the similar linear behavior of the P-P and normalized P-S reflection coefficients at small angles of incidence. We have used the linearity of RPP and R'PS at angles smaller than 35 degrees to simultaneously estimate the average VP/VS ratio, the contrasts of P- and S-wave velocities, and the contrast of density. Using this information, we solve for Poisson's ratio of each formation, which may enable lithology discrimination. The feasibility of this analysis was demonstrated using nonlinear synthetic data (i.e., finite-difference data). The results in estimating Poisson's ratio yielded less than 5 percent error. We generalize this new combined P-P and P-S AVO analysis for dipping interfaces. Similarly to the nondipping interface case, our derivations show that the amplitude variation with offset (AVO) of P-P and P-S for a dipping interface can be cast into intercepts and gradients. However, these intercepts and gradients depend on the angle of the dipping interface. Therefore, we further generalize our analysis by including a migration step that allows us to find the dipping angle. Because seismic data is not available in terms of RPP and R'PS, this process includes recovery of reflection coefficients after migrating the data and correcting for geometrical spreading, as done by Ikelle et al. (1986 and 1988). The combination of all of these steps, namely geometrical-spreading correction, migration, and AVO analysis, is another novelty of this thesis, which leads to finding the specific values of Poisson's ratio of each rock formation directly from the seismic data.