×

Sequential selection with unknown correlation structures. (English) Zbl 1329.62474

Summary: We create the first computationally tractable Bayesian statistical model for learning unknown correlation structures in fully sequential simulation selection. Correlations represent similarities or differences between various design alternatives and can be exploited to extract much more information from each individual simulation. However, in most applications, the correlation structure is unknown, thus creating the additional challenge of simultaneously learning unknown mean performance values and unknown correlations. Based on our new statistical model, we derive a Bayesian procedure that seeks to optimize the expected opportunity cost of the final selection based on the value of information, thus anticipating future changes to our beliefs about the correlations. Our approach outperforms existing methods for known correlation structures in numerical experiments, including one motivated by the problem of optimal wind farm placement, where real data are used to calibrate the simulation model.

MSC:

62P20 Applications of statistics to economics
62L05 Sequential statistical design
62F15 Bayesian inference
91B06 Decision theory

Software:

EGO

References:

[1] Arlotto A, Gans N, Chick S (2010) Optimal employee retention when inferring unknown learning curves. Johansson B, Jain S, Montoya-Torres J, Hugan J, Yücesan E, eds. Proc. 2010 Winter Simulation Conf. (IEEE, Piscataway, NJ), 1178-1188. CrossRef
[2] Bechhofer RE (1954) A single-sample multiple decision procedure for ranking means of normal populations with known variances. Ann. Math. Statist. 25(1):16-39. CrossRef · Zbl 0055.13003
[3] Bechhofer RE, Santner TJ, Goldsman DM (1995) Design and Analysis of Experiments for Statistical Selection, Screening and Multiple Comparisons (John Wiley & Sons, New York).
[4] Biller B, Corlu CG (2011) Accounting for parameter uncertainty in large-scale stochastic simulations with correlated inputs. Oper. Res. 59(3):661-673. Abstract, · Zbl 1342.62098
[5] Çinlar E (2011) Probability and Stochastics (Springer, New York). CrossRef
[6] Chen C-H, Lee LH (2011) Stochastic Simulation Optimization: An Optimal Computing Budget Allocation, System Engineering and Operations Research, Vol. 1 (World Scientific, Singapore).
[7] Chen C-H, He D, Fu MC, Lee LH (2008) Efficient simulation budget allocation for selecting an optimal subset. INFORMS J. Comput. 20(4):579-595. Abstract,
[8] Cheng RCH, Currie CSM (2004) Optimization by simulation metamodelling methods. Ingalls RG, Rossetti MD, Smith JS, Peters BA, eds. Proc. 2004 Winter Simulation Conf. (IEEE, Piscataway, NJ), 485-490. CrossRef
[9] Chick SE (2006) Subjective probability and Bayesian methodology. Henderson SG, Nelson BL, eds. Handbooks of Operations Research and Management Science, Vol. 13. Simulation (North-Holland Publishing, Amsterdam), 225-258.
[10] Chick SE, Inoue K (2001a) New procedures to select the best simulated system using common random numbers. Management Sci. 47(8): 1133-1149. Abstract,
[11] Chick SE, Inoue K (2001b) New two-stage and sequential procedures for selecting the best simulated system. Oper. Res. 49(5):732-743. Abstract,
[12] Chick SE, Branke J, Schmidt C (2010) Sequential sampling to myopically maximize the expected value of information. INFORMS J. Comput. 22(1):71-80. Abstract, · Zbl 1243.62005
[13] Cosgrove BA, Lohmann D, Mitchell KE, Houser PR, Wood EF, Schaake JC, Robock A (2003) Real-time and retrospective forcing in the North American land data assimilation system (NLDAS) project. J. Geophysical Res. 108(D22):8842-8853. CrossRef
[14] DeGroot MH (2004) Optimal Statistical Decisions, Wiley Classics Library (John Wiley & Sons, Hoboken, NJ). CrossRef
[15] Dominici F, Parmigiani G, Clyde M (2000) Conjugate analysis of multivariate normal data with incomplete observations. Canadian J. Statist. 28(3):533-550. CrossRef · Zbl 0958.62028
[16] Engelbert HJ, Shiryaev AN (1980) On absolute continuity and singularity of probability measures. Banach Center Publications 6:121-132.
[17] Francis P, Smilowitz K, Tzur M (2006) The period vehicle routing problem with service choice. Transportation Sci. 40(4):439-454. Abstract,
[18] Frazier PI, Powell WB, Dayanik S (2009) The knowledge-gradient policy for correlated normal rewards. INFORMS J. Comput. 21(4):599-613. Abstract, · Zbl 1243.91014
[19] Frazier PI, Xie J, Chick SE (2011) Value of information methods for pairwise sampling with correlations. Jain S, Creasey RR, Himmelspach J, White KP, Fu M, eds. Proc. 2011 Winter Simulation Conf. (IEEE, Piscataway, NJ), 3974-3986. CrossRef
[20] Fu MC, Hu J-Q, Chen C-H, Xiong X (2007) Simulation allocation for determining the best design in the presence of correlated sampling. INFORMS J. Comput. 19(1):101-111. Abstract, · Zbl 1241.62006
[21] Golub GH, Van Loan CF (1996) Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences (Johns Hopkins University Press, Baltimore).
[22] Gupta AK, Nagar DK (2000) Matrix Variate Distributions (Chapman & Hall, Boca Raton, FL).
[23] Gupta SS, Miescke KJ (1996) Bayesian look ahead one-stage sampling allocations for selection of the best population. J. Statist. Planning Inference 54(2):229-244. CrossRef · Zbl 0854.62018
[24] He D, Chick SE, Chen CH (2007) Opportunity cost and OCBA selection procedures in ordinal optimization for a fixed number of alternative systems. IEEE Trans. Systems, Man, Cybernetics C37(5):951-961. CrossRef
[25] He D, Lee LH, Chen CH, Fu MC, Wasserkrug S (2010) Simulation optimization using the cross-entropy method with optimal computing budget allocation. ACM Trans. Modeling Comput. Simulation 20(1): 4:1-4:22. CrossRef
[26] Hong LJ (2006) Fully sequential indifference-zone selection procedures with variance-dependent sampling. Naval Res. Logist. 53(5):464-476. CrossRef · Zbl 1127.62066
[27] Hong LJ, Nelson BL (2009) A brief introduction to optimization via simulation. Rosetti MD, Hill RR, Johansson B, Dunkin A, Ingalls RG, eds. Proc. 2009 Winter Simulation Conf. (IEEE, Piscataway, NJ), 75-85. CrossRef
[28] Huang D, Allen TT, Notz WI, Zeng N (2006) Global optimization of stochastic black-box systems via sequential Kriging meta-models. J. Global Optim. 34(3):441-466. CrossRef · Zbl 1098.90097
[29] Jones DR, Schonlau M, Welch WJ (1998) Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4):455-492. CrossRef · Zbl 0917.90270
[30] Kadane J, Trader R (1988) A Bayesian treatment of multivariate normal data with observations missing at random. Statist. Decision Theory Related Topics 4(1):225-234. CrossRef · Zbl 0664.62026
[31] Kim J-Y (2002) Limited information likelihood and Bayesian analysis. J. Econometrics 107(1):175-193. CrossRef · Zbl 1030.62016
[32] Kim S-H (2013) Statistical ranking and selection. Gass SI, Fu MC, eds. Encyclopedia of Operations Research and Management Science (Springer, New York), 1459-1469. CrossRef
[33] Kim S-H, Nelson BL (2001) A fully sequential procedure for indifference-zone selection in simulation. ACM Trans. Modeling Comput. Simulation 11(3):251-273. CrossRef · Zbl 1490.62207
[34] Kim S-H, Nelson BL (2006a) On the asymptotic validity of fully sequential selection procedures for steady-state simulation. Oper. Res. 54(3): 475-488. Abstract, · Zbl 1167.90450
[35] Kim S-H, Nelson BL (2006b) Selecting the best system. Henderson SG, Nelson BL, eds. Handbooks of Operations Research and Management Science, Vol. 13. Simulation (North-Holland Publishing, Amsterdam), 501-534.
[36] Kim S-H, Nelson BL (2007) Recent advances in ranking and selection. Henderson SG, Biller B, Hsieh M-H, Shortle J, Tew JD, Barton RR, eds. Proc. 2007 Winter Simulation Conf. (IEEE, Piscataway, NJ), 162-172.
[37] Kotz S, Nadarajah S (2004) Multivariate t Distributions and Their Applications (Cambridge University Press, New York). CrossRef
[38] Marmidis G, Lazarou S, Pyrgioti E (2008) Optimal placement of wind turbines in a wind park using Monte Carlo simulation. Renewable Energy 33(7):1455-1460. CrossRef
[39] Nelson BL, Matejcik FJ (1995) Using common random numbers for indifference-zone selection and multiple comparisons in simulation. Management Sci. 41(12):1935-1945. Abstract, · Zbl 0853.65149
[40] Pati D, Bhattacharya A, Pillai NS, Dunson D (2014) Posterior contraction in sparse Bayesian factor models for massive covariance matrices. Ann. Statist. 42(3):1102-1130. CrossRef · Zbl 1305.62124
[41] Powell WB, Ryzhov IO (2012) Optimal Learning (John Wiley & Sons, Hoboken, NJ). CrossRef
[42] Qu H, Ryzhov IO, Fu MC (2012) Ranking and selection with unknown correlation structures. Laroque C, Himmelspach J, Pasupathy R, Rose O, Uhrmacher AM, eds. Proc. 2012 Winter Simulation Conf. (IEEE, Piscataway, NJ), 144-155. CrossRef
[43] Triantafyllopoulos K (2008) Missing observation analysis for matrix-variate time series data. Statist. Probab. Lett. 78(16):2647-2653. CrossRef · Zbl 1147.62370
[44] Yang WN, Nelson BL (1991) Using common random numbers and control variates in multiple-comparison procedures. Oper. Res. 39(4): 583-591. Abstract, · Zbl 0737.65117
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.