Discrete conditional-expectation-based simulation optimization: Methodology and applications

Conditional value at risk (CVaR), which in essence is conditional expectation (CE), is a widely used risk measure commonly applied by financial engineers. This paper generalizes the concept of CE to the expected value of a loss function given that its value falls in between the α- and β-quantiles of the output distribution of a simulation model. We present a simulation optimization framework capable of efficiently estimating and optimizing this CE-based problem over a discrete feasible region. In order to allow our algorithm to be applicable to a wide range of problems including those of the black-box variety, we propose a gradient- and convexity assumption-free methodology known as Adaptive Particle and Hyperball Search for Conditional Expectation (APHS-CE). Besides applying the newly-developed Adaptive Particle Search to explore the whole feasible region globally, APHS-CE also dynamically and iteratively defines hyperball-based neighborhoods and exploits the most promising region locally through Latin Hyperball Sampling to speed up and facilitate the convergence to the global optimum. Convergence of the algorithm to the global optimal solution(s) is proved. Moreover, in order to enhance the algorithm efficiency, the variance reduction method of Importance Sampling in conjunction with a mechanism, called SOCBA-1, which is based on Optimal Computing Budget Allocation (OCBA) but tailored to fit the CE-based problems, are both applied. Numerical and empirical studies were conducted to evaluate the efficiency and efficacy of the proposed framework. Results show that the performance is promising and the framework is worth further investigation.