*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Efficient Computation in Stochastic Optimization and Simulation: Dynamic Programs, Risk Quantification, and Risk Optimization
Advisor: Prof. Enlu Zhou
Committee members:
Prof. Sigrun Andradottir
Prof. Hayriye Ayhan
Prof. Shijie Deng
Prof. Henry Lam (Department of Industrial and Operations Engineering, University of Michigan)
Date/time: Tuesday July 19th, 2016, at 9:00 AM
Location: Groseclose 226A
Summary:
Stochastic optimization and simulation are two of the most fundamental research areas in Operations Research. In this thesis, we develop efficient computational approaches for three important topics in the realm of stochastic optimization and simulation.
First, for general dynamic programs, we propose a regression approach to solve the information relaxation dual problems by exploring the structure of the function space of dual penalties. Compared with most of the existing approaches, the proposed one is more efficient since it circumvents the issue of nested simulation in approximating the so-called optimal dual penalty. The resulted approximations maintain to be feasible dual penalties, and thus yield valid dual bounds on the optimal value function. We further apply the proposed framework to a high-dimensional dynamic trading problem to demonstrate its effectiveness and efficiency in solving the duals of complex dynamic programs.
Second, for general stochastic simulation, we study the risk quantification of mean response under input uncertainty, which, to the best of our knowledge, has been rarely systematically studied in the literature. We develop nested Monte Carlo estimators for risk measures such as Value-at-Risk (VaR) and Conditional Value-at-Risk (CVaR) of mean response under input certainty. We show that they are strongly consistent and asymptotic normally distributed, and thus yield asymptotically valid confidence intervals. We further study the associated budget allocation problem for efficient simulation of the proposed nested risk estimators.
Last, for general loss distributions, we study the extension of the recently proposed model-based approach, namely the gradient-based adaptive stochastic search (GASS), to the optimization of risk measures such as VaR and CVaR. This problem is usually difficult, because 1) the loss function might lack structural properties such as convexity or differentiability since it is often generated via black-box simulation of a stochastic system; 2) evaluation of VaR or CVaR for a general loss distribution often requires rare-event simulation, which is computationally expensive. Instead of optimizing VaR or CVaR at target risk level directly, we incorporate an adaptive adjustment scheme on the risk level, by initializing the algorithm at a small risk level and adaptively increasing it until the simultaneous achievement of target risk level and convergence of the algorithm. This enables us to adaptively reduce the number of samples needed to estimate the risk measures at each iteration, and thus improving the overall efficiency.
