Mathematics
Permanent URI for this communityhttp://hdl.handle.net/1903/2261
Browse
4 results
Search Results
Item Working in Reverse: Advancing Inverse Optimization in the Fields of Equilibrium and Infrastructure Modeling(2022) Allen, Stephanie Ann; Gabriel, Steven A; Dickerson, John P; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Transportation and infrastructure modeling allows us to pursue societal aims such as improved disaster management, traffic flow, and water allocation. Equilibrium programming enables us to represent the entities involved in these applications such that we can learn more about their dynamics. These entities include transportation users and market players. However, determining the parameters in these models can be a difficult task because the entities involved in these equilibrium processes may not be able to articulate or to disclose the parameterizations that motivate them. The field of inverse optimization (IO) offers a potential solution to this problem by taking observed equilibria to these systems and using them to parameterize equilibrium models. In this dissertation, we explore the use of inverse optimization to parameterize multiple new or understudied subclasses of equilibrium problems as well as expand inverse optimization's application to new infrastructure domains. In the first project of our dissertation, our contribution to the literature is to propose that IO can be used to parameterize cost functions in multi-stage stochastic programs for disaster management and can be used in disaster support systems. We demonstrate in most of our experiments that using IO to obtain the hidden cost parameters for travel on a road network changes the protection decisions made on that road network when compared to utilizing the mean of the parameter range for the hidden parameters (also referred to as ``uniform cost''). The protection decisions made under the IO cost parameterizations versus the true cost parameterizations are similar for most of the experiments, thus lending credibility to the IO parameterizations. In the second project of our dissertation, we extend a well-known framework in the IO community to the case of jointly convex generalized Nash equilibrium problems (GNEPs). We demonstrate the utility of this framework in a multi-player transportation game in which we vary the number of players, the capacity level, and the network topology in the experiments as well as run experiments assuming the same costs among players and different costs among players. Our promising results provide evidence that our work could be used to regulate traffic flow toward aims such as reduction of emissions. In the final project of our dissertation, we explore the general parameterization of the constant vector in linear complementarity problems (LCPs), which are mathematical expressions that can represent optimization, game theory, and market models (Gabriel et al., 2012). Unlike the limited previous work on inverse optimization for LCPs, we characterize theoretical considerations regarding the inverse optimization problem for LCPs, prove that a previously proposed IO solution model can be dramatically simplified, and handle the case of multiple solution data points for the IO LCP problem. Additionally, we use our knowledge regarding LCPs and IO in a water market allocation case study, which is an application not previously explored in the IO literature, and we find that charging an additional tax on the upstream players enables the market to reach a system optimal. In sum, this dissertation contributes to the inverse optimization literature by expanding its reach in the equilibrium problem domain and by reaching new infrastructure applications.Item MULTI-AGENT UNMANNED UNDERWATER VEHICLE VALIDATION VIA ROLLING-HORIZON ROBUST GAMES(2019) Quigley, Kevin J; Gabriel, Steven A.; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Autonomy in unmanned underwater vehicle (UUV) navigation is critical for most applications due to inability of human operators to control, monitor or intervene in underwater environments. To ensure safe autonomous navigation, verification and validation (V&V) procedures are needed for various applications. This thesis proposes a game theory-based benchmark validation technique for trajectory optimization for non-cooperative UUVs. A quadratically constrained nonlinear program formulation is presented, and a "perfect-information reality" validation framework is derived by finding a Nash equilibrium to various two-player pursuit-evasion games (PEG). A Karush-Kuhn-Tucker (KKT) point to such a game represents a best-case local optimum, given perfect information available to non-cooperative agents. Rolling-horizon foresight with robust obstacles are incorporated to demonstrate incomplete information and stochastic environmental conditions. A MATLAB-GAMS interface is developed to model the rolling-horizon game, and is solved via a mixed complementarity problem (MCP), and illustrative examples show how equilibrium trajectories can serve as benchmarks for more practical real-time path planners.Item HYBRID ROUTING MODELS UTILIZING TRUCKS OR SHIPS TO LAUNCH DRONES(2018) Poikonen, Stefan Allan; Golden, Bruce L; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Technological advances for unmanned aerial vehicles, commonly referred to as drones, have opened the door to a number of new and interesting applications in areas including military, healthcare, communications, cinematography, emergency response, and logistics. However, limitations due to battery capacity, maximum take-off weight, finite range of wireless communications, and legal regulations have restricted the effective operational range of drones in many practical applications. Several hybrid operational models involving one or more drones launching from a larger vehicle, which may be a ship, truck, or airplane, have emerged to help mitigate these range limitations. In particular, the drones utilize the larger vehicle as both a mobile depot and a recharging or refueling platform. In this dissertation, we describe routing models that leverage the tandem of one or more drones with a larger vehicle. In these models, there is generally a set of targets that should be visited in an efficient (usually time-minimizing) manner. By using multiple vehicles, these targets may be visited in parallel thereby reducing the total time to visit all targets. The vehicle routing problem with drones (VRPD) and traveling salesman problem with a drone (TSP-D) consider hybrid truck-and-drone models of delivery, where the goal is to minimize the time required to deliver a set of packages to their respective customers and return the truck(s) and drone(s) to the origin depot. In both problems, the drone can carry one homogeneous package at a time. Theoretical analysis, exact solution methods, heuristic solution methods, and computational results are presented. In the mothership and drone routing problem (MDRP), we consider the case where the larger launch vehicle is free to move in Euclidean space (the open seas) and launch a drone to visit one target location at a time, before returning to the ship to pick up new cargo or refuel. The mothership and high capacity drone routing problem (MDRP-HC) is a generalization of the mothership and drone routing problem, which allows the drone to visit multiple targets consecutively before returning to the ship. MDRP and MDRP-HC contain elements of both combinatorial optimization and continuous optimization. In the multi-visit drone routing problem (MVDRP), a drone can visit multiple targets consecutively before returning to the truck, subject to energy constraints that take into account the weight of packages carried by the drone.Item Geometric Structures and Optimization on Spaces of Finite Frames(2011) Strawn, Nathaniel; Benedetto, John J; Balan, Radu V; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)A finite (μ, Ѕ)-frame variety consists of the real or complex matrices F = [f1 … fn] with frame operator FF* = S, and which also satisfies ||fi|| = μi for all i = 1,...,N. Here, S is a fixed Hermitian positive definite matrix and μ = [μ1...μN] is a fixed list of lengths. These spaces generalize the well-known spaces of finite unit-norm tight frames. We explore the local geometry of these spaces and develop geometric optimization algorithms based on the resulting insights. We study the local geometric structure of the (μ, Ѕ)-frame varieties by viewing them as intersections of generalized tori (the length constraints) with distorted Stiefel manifolds (the frame operator constraint). Exploiting this perspective, we characterize the nonsingular points of these varieties by determining where this intersection is transversal in a Hilbert-Schmidt sphere. A corollary of this characterization is a characterization of the tangent spaces of (μ, Ѕ)-frame varieties, which is in turn leveraged to validate explicit local coordinate systems. Explict bases for the tangent spaces are also constructed. Geometric optimization over a (μ, Ѕ)-frame variety is performed by combining knowledge of the tangent spaces with geometric optimization of the frame operator distance over a product of spheres. Given a differentiable objective function, we project the full gradient onto the tangent space and then minimize the frame operator distance to obtain an approximate gradient descent algorithm. To partially validate this procedure, we demonstrate that the induced flow converges locally. Using Sherman-Morrision type formulas, we also describe a technique for constructing points on these varieties that can be used to initialize the optimization procedure. Finally, we apply the approximate gradient descent procedure to numerically construct equiangular tight frames, Grassmannian frames, and Welch bound equality sequences with low mutual coherence.