×

Surrogate-based promising area search for Lipschitz continuous simulation optimization. (English) Zbl 1448.90006

Summary: We propose an adaptive search algorithm for solving simulation optimization problems with Lipschitz continuous objective functions. The method combines the strength of several popular strategies in simulation optimization. It employs the shrinking ball method to estimate the performance of sampled solutions and uses the performance estimates to fit a surrogate model that iteratively approximates the response surface of the objective function. The search for improved solutions at each iteration is then based on sampling from a promising region (a subset of the decision space) adaptively constructed to contain the point that optimizes the surrogate model. Under appropriate conditions, we show that the algorithm converges to the set of local optimal solutions with probability one. A computational study is also carried out to illustrate the algorithm and to compare its performance with some of the existing procedures.

MSC:

90-10 Mathematical modeling or simulation for problems pertaining to operations research and mathematical programming

Software:

COMPASS; EGO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alrefaei MH, Andradóttir S (1999) A simulated annealing algorithm with constant temperature for discrete stochastic optimization. Management Sci. 45(5):748-764.Link, Google Scholar · Zbl 1231.90315
[2] Andradóttir S (2014) A review of random search methods. Fu MC, ed. Handbook of Simulation Optimization (Springer, New York), 277-292.Google Scholar
[3] Andradóttir S, Prudius AA (2010) Adaptive random search for continuous simulation optimization. Naval Res. Logist. 57(6):583-604.Crossref, Google Scholar · Zbl 1198.90303 · doi:10.1002/nav.20422
[4] Baumert S, Smith RL (2002) Pure random search for noisy objective functions. University of Michigan Technical Report, Ann Arbor.Google Scholar
[5] Bishop CM (1995) Neural Networks for Pattern Recognition (Oxford University Press, New York).Google Scholar
[6] Chang KH, Hong LJ, Wan H (2013) Stochastic trust-region response-surface method (strong): A new response-surface framework for simulation optimization. INFORMS J. Comput. 25(2):230-243.Link, Google Scholar
[7] Chen R, Menickelly M, Scheinberg K (2017) Stochastic optimization using a trust-region method and random models. Math. Programming 169(2):447-487.Crossref, Google Scholar · Zbl 1401.90136 · doi:10.1007/s10107-017-1141-8
[8] Deng G, Ferris MC (2009) Variable-number sample-path optimization. Math. Programming 117(1-2):81-109.Crossref, Google Scholar · Zbl 1165.90013 · doi:10.1007/s10107-007-0164-y
[9] Fan Q, Hu J (2016) Simulation optimization via promising region search and surrogate model approximation. Roeder TMK, Frazier PI, Szechtman R, Zhou E, eds. Proc. 2016 Winter Simulation Conf. (IEEE Press, Piscataway, NJ), 649-658.Google Scholar
[10] Fu MC, Healy KJ (1992) Simulation optimization of (s, S) inventory systems. Swain JJ, Goldsman D, Crain RC, Wilson JR, eds. Proc. 1992 Winter Simulation Conf. (IEEE Press, Piscataway, NJ),506-514.Google Scholar
[11] Gutmann HM (2001) A radial basis function method for global optimization. J. Global Optim. 19(3):201-227.Crossref, Google Scholar · Zbl 0972.90055 · doi:10.1023/A:1011255519438
[12] Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301):13-30.Crossref, Google Scholar · Zbl 0127.10602 · doi:10.1080/01621459.1963.10500830
[13] Hong LJ, Nelson BL (2006) Discrete optimization via simulation using compass. Oper. Res. 54(1):115-129.Link, Google Scholar · Zbl 1167.90630
[14] Hong LJ, Nelson BL (2007) A framework for locally convergent random-search algorithms for discrete optimization via simulation. ACM Trans. Model. Comput. Simul. 17(4):Article 19.Crossref, Google Scholar · Zbl 1390.90337 · doi:10.1145/1276927.1276932
[15] Hu J (2015) Model-based stochastic search methods. Fu MC, ed. Handbook of Simulation Optimization (Springer, New York),319-340.Crossref, Google Scholar · doi:10.1007/978-1-4939-1384-8_12
[16] Hu J, Fu MC, Marcus SI (2008) A model reference adaptive search method for stochastic global optimization. Commun. Inform. Systems 8(3):245-276.Crossref, Google Scholar · Zbl 1189.90108 · doi:10.4310/CIS.2008.v8.n3.a4
[17] Huang D, Allen T, Notz W, Zeng N (2006) Global optimization of stochastic black-box systems via sequential kriging meta-models. J. Global Optim. 34(3):441-466.Crossref, Google Scholar · Zbl 1098.90097 · doi:10.1007/s10898-005-2454-3
[18] Jones D, Schonlau M, Welch W (1998) Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4):455-492.Crossref, Google Scholar · Zbl 0917.90270 · doi:10.1023/A:1008306431147
[19] Kiatsupaibul S, Smith RL, Zabinsky ZB (2018) Single observation adaptive search for continuous simulation optimization. Oper. Res. Forthcoming.Link, Google Scholar · Zbl 1456.90113
[20] Kiefer J, Wolfowitz J (1952) Stochastic estimation of the maximum of a regression function. Ann. Math. Statist. 23(3):462-466.Crossref, Google Scholar · Zbl 0049.36601 · doi:10.1214/aoms/1177729392
[21] Kim S, Pasupathy R, Henderson SG (2015) A guide to sample average approximation. Fu MC, ed. Handbook of Simulation Optimization (Springer, New York), 207-243.Crossref, Google Scholar · doi:10.1007/978-1-4939-1384-8_8
[22] Kleijnen JPC (2015) Model-based stochastic search methods. Fu MC, ed. Handbook of Simulation Optimization (Springer, New York), 81-104.Google Scholar
[23] Kleywegt A, Shapiro A, Homem-De-MelloHu T (2001) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479-502.Crossref, Google Scholar · Zbl 0991.90090 · doi:10.1137/S1052623499363220
[24] Larson J, Billups SC (2016) Stochastic derivative-free optimization using a trust region framework. Comput. Optim. Appl. 64(3):619-645.Crossref, Google Scholar · Zbl 1381.90098 · doi:10.1007/s10589-016-9827-z
[25] Müller J (2017) SOCEMO: Surrogate optimization of computationally expensive multiobjective problems. INFORMS J. Comput. 29(4):581-596.Link, Google Scholar · Zbl 1528.90248
[26] Nakayama H, Arakawa M, Sasaki R (2002) Simulation-based optimization using computational intelligence. Optim. Engrg. 3(2):201-214.Crossref, Google Scholar · Zbl 1053.68078 · doi:10.1023/A:1020971504868
[27] Regis R, Shoemaker C (2007) Improved strategies for radial basis function methods for global optimization. J. Global Optim. 37(1):113-135.Crossref, Google Scholar · Zbl 1149.90120 · doi:10.1007/s10898-006-9040-1
[28] Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400-407.Crossref, Google Scholar · Zbl 0054.05901 · doi:10.1214/aoms/1177729586
[29] Robinson SM (1996) Analysis of sample-path optimization. Math. Oper. Res. 21(3):513-528.Link, Google Scholar · Zbl 0868.90087
[30] Rubinstein RY, Kroese DP (2004) The Cross Entropy Method: A Unified Approach To Combinatorial Optimization, Monte-Carlo Simulation and Machine Learning (Springer-Verlag, Secaucus NJ).Crossref, Google Scholar · Zbl 1140.90005 · doi:10.1007/978-1-4757-4321-0
[31] Shi L, Ólafsson S (2000) Nested partitions method for stochastic optimization. Methodology Comput. Appl. Probab. 2(3):271-291.Crossref, Google Scholar · Zbl 0968.90054 · doi:10.1023/A:1010081212560
[32] Shiryaev AN (1996) Probability, Second Ed. (Springer-Verlag, New York).Crossref, Google Scholar · doi:10.1007/978-1-4757-2539-1
[33] Smith RL (1984) Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32(6):1296-1308.Link, Google Scholar · Zbl 0552.65004
[34] Sóbester A, Leary S, Keane A (2005) On the design of optimization strategies based on global response surface approximation model. J. Global Optim. 33(1):31-59.Crossref, Google Scholar · Zbl 1137.90743 · doi:10.1007/s10898-004-6733-1
[35] Spall JC (1992) Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans. Automatic Control 37(3):332-341.Crossref, Google Scholar · Zbl 0745.60110 · doi:10.1109/9.119632
[36] Spall JC (2003) Introduction to Stochastic Search and Optimization (John Wiley & Sons, Springer, Hoboken, NJ).Crossref, Google Scholar · Zbl 1088.90002 · doi:10.1002/0471722138
[37] Xu J, Nelson BL, Hong JL (2010) Industrial strength compass: A comprehensive algorithm and software for optimization via simulation. ACM Trans. Model. Comput. Simul. 20(1):Article 3.Crossref, Google Scholar · Zbl 1386.65034 · doi:10.1145/1667072.1667075
[38] Yan D, Mukai H (1992) Stochastic discrete optimization. SIAM J. Control Optim. 30(3):594-612.Crossref, Google Scholar · Zbl 0764.90066 · doi:10.1137/0330034
[39] Zabinsky ZB (2015) Stochastic adaptive search methods: Theory and implementation. Fu MC, · doi:10.1007/978-1-4939-1384-8_11
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.