離散和連續條件期望值之模擬最佳化演算架構: 方法和應用

Discrete and Continuous Conditional Expectation-­based Simulation Optimization: Methodology and Applications

柯若博(Cuckler, Robert)

指導教授 ： 張國浩

國立清華大學/工學院/工業工程與工程管理學系/博士(2021年)

摘要

為了概括條件期望值（金融風險管理中使用最廣泛的度量之一）的適用性，這個研究開發了一對無梯度的黑盒隨機模擬演算法，用於基於條件期望值（CE）的模擬最佳化問題，一個用於連續解空間，另一個用於離散解空間。為了在連續解空間中最佳化基於CE的目標函數，提出了一種直接搜索最佳化方法，稱為SNM­CE；這種方法繼承了隨機Nelder­Mead(SNM)的基本搜索方法，但進一步結合了設計用於處理基於CE的目標函數問題的有效機制。對於離散解空間情況，本研究提出了一種稱為條件期望的自適應粒子和超球搜索(APHS­-CE)的方法；該框架的搜索方法旨在利用與粒子搜索優化(PSO)和拉丁Hyperball採樣相關的概念，但經過修改以適應基於CE的方法。此外，SNM­-CE和APHS-­CE都將CE的概念推廣到損失函數的預期值，因為它的值落在基礎損失分佈的α­和β­分位數之間。在這兩種方法中，假設潛在問題足夠複雜以至於沒有封閉形式的表達式可以表示目標函數，隨機模擬被應用於估計CE。此外，這兩種方法都應用重要性抽樣(IS)作為方差減少演算資源，結合基於最佳資源分配法(OCBA)的樣本量分配算法，確保高效使用模擬資源。結果表明，SNM-­CE和APHS-­CE都能強機率（w.p.1）收斂到真正的全局最優。進行了廣泛的數值研究和實證研究，以證明SNM­-CE和APHS-­CE在理論和實踐環境中的有效性、效率和可行性。

關鍵字

隨機模擬 ； 隨機最佳化 ； 條件期望值

並列摘要

In order to generalize the applicability of Conditional Value at Risk, one of the most widely used measurements used in financial risk management, the proposed research develops a pair of gradient-free, black box solu­tion methodologies for conditional expectation (CE)­-based simulation opti­mization problems, one for continuous solution space and the other for dis­crete solution space. To optimize CE­-based objective functions in contin­uous solution space, a direct search optimization method, called SNM-­CE is proposed; this methodology inherits the search framework of Stochas­tic Nelder ­Mead (SNM) Simplex Method but further incorporates effec­tive mechanisms designed for handling problems with CE­-based objective functions. For the discrete solution space case, this research proposes a methodology known as Adaptive Particle and Hyperball Search for Condi­tional Expectation (APHS­-CE); the search methodology for this framework intends to utilize concepts related to Particle Search Optimization (PSO) and Latin Hyperball sampling, but modified to fit into a CE-­based method­ology. Moreover, both SNM-­CE and APHS­-CE generalize the concept of CE to the expected value of a loss function given that its value falls in between the α- ­and β­-quantile of the underlying loss distribution. In both methodologies, as it is assumed that the underlying problem is complicated enough that no closed­ form expression can represent the objective func­tion, stochastic simulation is applied to estimate CE. Also, both method­ologies apply Importance Sampling (IS) as a variance reduction technique, which, combined with Optimal Computing Budget Allocation (OCBA)­-based sample size allocation algorithms, ensures that simulation resources are used with great efficiency. It is shown that both SNM­-CE and APHS-­CE can converge to the true global optimum with probability one (w.p.1). Extensive numerical experiments and a pair of empirical studies are con­ducted to demonstrate the effectiveness, efficiency and viability of both SNM­-CE and APHS­-CE in theoretical and practical settings.

並列關鍵字

simulation optimization ； particle swarm optimization ； conditional expectation ； direct search method ； op­timal computing budget allocation ； importance sampling ； Nelder Mead

參考文獻

1. H.­C. Jang, Y.­N. Lien, and T.­C. Tsai,“Rescue information system for earthquake disasters based on manet emergency communication platform,”in Proceedings of the 2009 international conference on wireless communications and mobile com­puting: connecting the world wirelessly, pp. 623–627, 2009.

2. S. Gonzalez, H. Jalali, and I. Van Nieuwenhuyse,“A multiobjective stochastic simulation optimization algorithm,”European Journal of Operational Research, vol. 284, no. 1, pp. 212–226, 2020.

3. Y. Qiu, H. Zhou, and Y.­Q. Wu,“An importance sampling method with applications to rare event probability,”in 2007 IEEE International Conference on Grey Systems and Intelligent Services, pp. 1381–1385, IEEE, 2007.

4. C.­J.Huang, K.­H.Chang, and J. Lin,“Optimal vehicle allocation for an automated materials handling system using simulation optimization,”Simulation Modelling Practice and Theory, vol. 52, pp. 40–51, 2015.

5. K.­H. Chang and R. Cuckler,“Applying simulation optimization for agile vehicle fleet sizing of automated material handling systems in semiconductor manufactur­ing,” Asia-­Pacific Journal of Operational Research, p. 2150018, 2021.