條件期望值之模擬最佳化演算架構

A Framework for Conditional-Expectation-based Simulation Optimization

楊士逸(Shih-I Yang)

指導教授 ： 張國浩

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

摘要

條件期望值(Conditional Expectation)源於財務金融領域之條件風險值(Conditional Value at Risk)，為一個被廣泛使用的風險管理指標。本研究欲求解其無限制式之最佳化問題，改善其估計方法以提升計算效率，並拓展其應用層面。本論文以SNM (Stochastic Nelder-Mead Simplex Method)演算法為基礎，提出一個名為SNM-CE (Stochastic Nelder-Mead Simplex Method for Conditional Expectation)之無微分最佳化演算法。因條件期望值具有隨機性，故需利用隨機模擬以進行估計，本研究基於重要性抽樣(Importance Sampling)與最佳資源分配法(Optimal Computing Budget Allocation, OCBA)，在較少之模擬資源下達到一定之估計精確度，且經由修正問題模型之定義與流程，使得上述方法更適合融入本演算架構，提升演算效率。針對SNM演算法本身，本研究進行細部流程上之修正，並提出新的適應性隨機搜尋法(Adaptive Random Search)，以提升此演算法之效率。本研究之數值實驗也顯示本演算架構之實用及有效性，值得後續深入研究。

關鍵字

SNM-CE ； 條件期望值 ； 重要性抽樣 ； 最佳資源分配法 ； 適應性隨機搜尋 ； 模擬最佳化 ； 無微分最佳化演算法

並列摘要

Conditional Expectation(CE) origins from the term “Conditional Value at Risk” in the financial field, which is one of the widely used risk measurement in the practice of risk management. Consider the unconstrained optimization problem of CE, this research aims to improve the computational efficiency with a different estimation method and expand the area of its application. We propose a gradient free optimization method, called Stochastic Nelder-Mead Simplex Method for Conditional Expectation, which is based on the Stochastic Nelder-Mead Simplex Method, to solve the optimization problem of CE. Because of the randomness and complexities, Monte Carlo simulation is applied to estimate the conditional expectation. We use Importance Sampling as variance reduction technique and Optimal Computing Budget Allocation to utilize the simulation resources more efficiently. By revising the problem definition and process of the model, we integrate these above methods into the proposed framework to increase the computational efficiency. As for the original SNM algorithm, this research not only makes revisions on the process details, but also develop a new Adaptive Random Search method to improve the computational efficiency. In the end, a series of numerical experiments was conducted to verify the performance and applicability in real problem. The results show the efficiency and efficacy of our proposed method, which is worth for further investigation.

並列關鍵字

Stochastic Nelder-Mead Simplex method ； Conditional Expectation ； Importance Sampling ； Optimal Computing Budget Allocation ； Adaptive Random Search ； Simulation Optimization

參考文獻

1. Ait-Alla, A., Teucke, .M, Lütjen, M., Beheshti-Kashi, S. and Reza Karimi, H. (2014). Robust Production Planning in Fashion Apparel Industry under Demand Uncertainty via Conditional Value at Risk. Mathematical Problems in Engineering, volume 2014.

2. Alem, D., Clark, A., Moreno, A. (2016). Stochastic network models for logistics planning in disaster relief. European Journal of Operational Research, vol. 255, pp. 187–206.

3. Alexander, S., Coleman, T. F., and Li, Y. (2006). Minimizing CVaR and VaR for a portfolio of derivatives. Journal of Banking and Finance, vol. 30, pp. 583–605.

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

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