Efficient computation in stochastic optimization and simulation: Dynamic programs, risk quantification, and risk optimization

Stochastic optimization and simulation;Dynamic programs;Dual problems;Regression;Risk quantification;Input uncertainty;Budget allocation;Risk optimization;Model-based;Adaptive risk level

Zhu, Helin ; Zhou, Enlu Industrial and Systems Engineering Andradottir, Sigrun Ayhan, Hayriye Deng, Shijie Lam, Henry ; Zhou, Enlu

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Stochastic optimization and simulation;    Dynamic programs;    Dual problems;    Regression;    Risk quantification;    Input uncertainty;    Budget allocation;    Risk optimization;    Model-based;    Adaptive risk level;   

Others  :  https://smartech.gatech.edu/bitstream/1853/55639/1/ZHU-DISSERTATION-2016.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

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 asymptotically 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.