目標式為條件期望值之模擬最佳化演算架構

An Optimization Framework for Conditional-Expectation-based Simulation Optimization

林星妤(Hsing-Yu Lin)

指導教授 ： 張國浩

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

摘要

條件風險值(Conditional Value at Risk)是一個被廣泛使用的風險管理指標，因此本研究將條件風險值一般化為條件期望值，希望改善其估計方法並處理其最佳化之問題。條件期望值之最佳化問題為非確定性問題，本篇論文提出稱為AGLS-CE (Adaptive Global and Local Search for Conditional Expectation)的無微分最佳化演算法，此方法以AGLS-QC (Adaptive Global and Local Search for Quantile-based Constraint problems)為基礎，在估計條件期望值階段因其具有隨機性與複雜性，我們利用隨機模擬來進行估計，並使用重要性抽樣(Importance Sampling)與最佳資源分配法(Optimal Computing Budget Allocation, OCBA)，在不降低精確性的前提下減少模擬所需的資源。在搜尋最佳解階段運用鄰近區域的概念(neighborhood)選定區域搜尋範圍，並於此區域利用本研究提出之拉丁超球體抽樣(Latin Hyperball Sampling)決定區域樣本點，而全域搜尋與區域搜尋的觀測點數量會隨著迭代而改變，最後判斷每一代之最佳解是否有鄰近點可以分享觀測值，再次提高估計的準確性。本研究的數值研究中也顯示此演算法可行且有效，值得深入研究。

關鍵字

AGLS-CE ； 條件風險值 ； 重要性抽樣 ； 最佳資源分配法 ； 拉丁超球體抽樣 ； 模擬最佳化 ； 無微分最佳化演算法

並列摘要

Conditional value at risk (CVaR) is one kind of widely used risk measurement in the practice risk management. This paper generalizes CVaR to conditional expectation and looks into its estimation and optimization. Owing to its randomness and complexities, Monte Carlo method is employed to estimate the conditional expectation. We also use Importance Sampling as variance reduction method and Optimal Computing Budget Allocation to make a more efficient use of simulation resources. The optimization problem of conditional expectation is not a deterministic problem. Therefore, we propose a new optimization framework, called Adaptive Global and Local Search for Conditional Expectation, which is a gradient-free method. This framework base on Adaptive Global and Local Search for Quantile-based Constraint problems, we implement the concept of neighborhood; use both local search and global search to find the optimal solution. The numbers of samples in both regions change by iterations. In addition, Latin Hyperball Sampling is used in the local search region to determine the sample points rather than random sampling. Last but not least, we employ Kolmogorov–Smirnov Test to determine whether the nearest point should share its observations to the optimal solution. In the end, a numerical study shows the efficiency and efficacy of our proposed method, which is worth doing further investigation.

並列關鍵字

Adaptive Global and Local Search for Conditional Expectation ； Conditional Value at Risk ； Importance Sampling ； Optimal Computing Budget Allocation ； Latin Hyperball Sampling ； Simulation Optimization

參考文獻

1. Andersson, F., Mausser, H., Rosen, D., and Uryasev, S. (2001). Credit risk optimization with conditional value at risk criterion. Mathematical Programming, vol. 89, no.2, pp. 273–291.

2. Andrade, F. A., Esat, I., & Badi, M. N. M. (2001). A new approach to time-domain vibration condition monitoring: gear tooth fatigue crack detection and identification by the Kolmogorov–Smirnov test. Journal of Sound and vibration, 240(5), 909-919.

3. Artzner, P., Delbaen, F., Eber, J. M., & Heath, D. (1999). Coherent measures of risk. Mathematical finance, vol. 9, no. 3, pp. 203–228.

4. Avramidis, A.N., and Wilson, J. R. (1998). Correlation-induction techniques for estimating quantiles in simulation experiments. Operations Research, vol. 46, no. 4, pp. 574–591.

5. Basova, H. G., Rockafellar, R. T., and Royset, J. O. (2011). A computational study of the buffered failure probability in reliability-based design optimization. in Proceedings of the 11th Conference on Application of Statistics and Probability in Civil Engineering.