Theses and Dissertations from UMD

Permanent URI for this communityhttp://hdl.handle.net/1903/2

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Subject: search.filters.subject.Global Optimization

Search Results

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Stochastic Systems with Cumulative Prospect Theory
    (2013) Lin, Kun; Marcus, Steven I.; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Stochastic control problems arise in many fields. Traditionally, the most widely used class of performance criteria in stochastic control problems is risk-neutral. More recent attempts at introducing risk-sensitivity into stochastic control problems include the application of utility functions. The decision theory community has long debated the merits of using expected utility for modeling human behaviors, as exemplified by the Allais paradox. Substantiated by strong experimental evidence, Cumulative Prospect Theory (CPT) based performance measures have been proposed as alternatives to expected utility based performance measures for evaluating human-centric systems. Our goal is to study stochastic control problems using performance measures derived from the cumulative prospect theory. The first part of this thesis solves the problem of evaluating Markov decision processes (MDPs) using CPT-based performance measures. A well-known method of solving MDPs is dynamic programming, which has traditionally been applied with an expected utility criterion. When the performance measure is CPT-inspired, several complications arise. Firstly, when solving a problem via dynamic programming, it is important that the performance criterion has a recursive structure, which is not true for all CPT-based criteria. Secondly, we need to prove the traditional optimality criteria for the updated problems (i.e., MDPs with CPT-based performance criteria). The theorems stated in this part of the thesis answer the question: what are the conditions required on a CPT-inspired criterion such that the corresponding MDP is solvable via dynamic programming? The second part of this thesis deals with stochastic global optimization problems. Using ideas from the cumulative prospect theory, we are able to introduce a novel model-based randomized optimization algorithm: Cumulative Weighting Optimization (CWO). The key contributions of our research are: 1) proving the convergence of the algorithm to an optimal solution given a mild assumption on the initial condition; 2) showing that the well-known cross-entropy optimization algorithm is a special case of CWO-based algorithms. To the best knowledge of the author, there is no previous convergence proof for the cross-entropy method. In practice, numerical experiments have demonstrated that a CWO-based algorithm can find a better solution than the cross-entropy method. Finally, in the future, we would like to apply some of the ideas from cumulative prospect theory to games. In this thesis, we present a numerical example where cumulative prospect theory has an unexpected effect on the equilibrium points of the classic prisoner's dilemma game.
  • Thumbnail Image
    Item
    Simulation-based Methods for Stochastic Control and Global Optimization
    (2011) Wang, Yongqiang; Marcus, Steven I; Fu, Michael C; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Ideas of stochastic control have found applications in a variety of areas. A subclass of the problems with parameterized policies (including some stochastic impulse control problems) has received significant attention recently because of emerging applications in the areas of engineering, management, and mathematical finance. However, explicit solutions for this type of stochastic control problems only exist for some special cases, and effective numerical methods are relatively rare. Deriving efficient stochastic derivative estimators for payoff functions with discontinuities arising in many problems of practical interest is very challenging. Global optimization problems are extremely hard to solve due to the typical multimodal properties of objective functions. With the increasing availability of computing power and memory, there is a rapid development in the merging of simulation and optimization techniques. Developing new and efficient simulation-based optimization algorithms for solving stochastic control and global optimization problems is the primary goal of this thesis. First we develop a new simulation-based optimization algorithm to solve a stochastic control problem with a parameterized policy that arises in the setting of dynamic pricing and inventory control. We consider a joint dynamic pricing and inventory control problem with continuous stochastic demand and model the problem as a stochastic control problem. An explicit solution is given when a special demand model is considered. For general demand models with a parameterized policy, we develop a new simulation-based method to solve this stochastic control problem. We prove the convergence of the algorithm and show the effectiveness of the algorithm by numerical experiments. In the second part of this thesis, we focus on the problem of estimating the derivatives for a class of discontinuous payoff functions, for which existing methods are either not valid or not efficient. We derive a new unbiased stochastic derivative estimator for performance functions containing indicator functions. One important feature of this new estimator is that it can be computed from a single sample path or simulation, whereas existing estimators in the literature require additional simulations. Finally we propose a new framework for solving global optimization problems by establishing a connection with evolutionary games, and show that a particular equilibrium set of the evolutionary game is asymptotically stable. Based on this connection, we propose a Model-based Evolutionary Optimization (MEO) algorithm, which uses probabilistic models to generate new candidate solutions and uses dynamics from evolutionary game theory to govern the evolution of the probabilistic models. MEO gives new insight into the mechanism of model updating in model-based global optimization algorithms from the perspective of evolutionary game theory. Furthermore, it opens the door to developing new algorithms by using various learning algorithms and analysis techniques from evolutionary game theory.
  • Thumbnail Image
    Item
    Particle Filtering for Stochastic Control and Global Optimization
    (2009) Zhou, Enlu; Marcus, Steven I.; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This thesis explores new algorithms and results in stochastic control and global optimization through the use of particle filtering. Stochastic control and global optimization are two areas that have many applications but are often difficult to solve. In stochastic control, an important class of problems, namely, partially observable Markov decision processes (POMDPs), provides an ideal paradigm to model discrete-time sequential decision making under uncertainty and partial observation. However, POMDPs usually do not admit analytical solutions, and are computationally very expensive to solve most of the time. While many efficient numerical algorithms have been developed for finite-state POMDPs, there are only a few proposed for continuous-state POMDPs, and even more sparse are relevant analytical results regarding convergence and error bounds. From the modeling viewpoint, many application problems are modeled more naturally by continuous-state POMDPs rather than finite-state POMDPs. Therefore, one part of the thesis is devoted to developing a new efficient algorithm for continuous-state POMDPs and studying the performance of the algorithm both analytically and numerically. Based on the idea of density projection with particle filtering, the proposed algorithm reduces the infinite-dimensional problem to a finite-low-dimensional one, and also has the flexibility and scalability for better approximation if given more computational power. Error bounds are proved for the algorithm, and numerical experiments are carried out on an inventory control problem. In global optimization, many problems are very difficult to solve due to the presence of multiple local optima or badly scaled objective functions. Many approximate solutions methods have been developed and studied. Among them, a recent class of simulation-based methods share the common characteristic of repeatedly drawing candidate solutions from an intermediate probability distribution and then updating the distribution using these candidate solutions, until the probability distribution becomes concentrated on the optimal solution. The efficiency and accuracy of these algorithms depend very much on the choice of the intermediate probability distributions and the updating schemes. Using a novel interpretation of particle filtering, these algorithms are unified under one framework, and hence, many new insights are revealed. By better understanding these existing algorithms, the framework also holds the promise for developing new improved algorithms. Some directions for new improved algorithms are proposed, and numerical experiments are carried out on a few benchmark problems.