Adaptive sampling line search for local stochastic optimization with integer variables. (English) Zbl 1506.90181
Summary: We consider optimization problems with an objective function that is estimable using a Monte Carlo oracle, constraint functions that are known deterministically through a constraint-satisfaction oracle, and integer decision variables. Seeking an appropriately defined local minimum, we propose an iterative adaptive sampling algorithm that, during each iteration, performs a statistical local optimality test followed by a line search when the test detects a stochastic descent direction. We prove a number of results. First, the true function values at the iterates generated by the algorithm form an almost-supermartingale process, and the iterates are absorbed with probability one into the set of local minima in finite time. Second, such absorption happens exponentially fast in iteration number and in oracle calls. This result is analogous to non-standard rate guarantees in stochastic continuous optimization contexts that involve sharp minima. Third, the oracle complexity of the proposed algorithm increases linearly in the dimensionality of the local neighborhood. As a solver, primarily due to combining line searches that use common random numbers with statistical tests for local optimality, the proposed algorithm is effective on a variety of problems. We illustrate such performance using three problem suites, on problems ranging from 25 to 200 dimensions.
Keywords:
local stochastic optimization; simulation optimization; adaptive sampling; integer variablesReferences:
| [1] | Abhishek, K.; Leyffer, S.; Linderoth, J., A mixed-integer nonlinear program for the optimization of thermal insulation systems, Opt. Eng., 11, 2, 185-212 (2010) · Zbl 1273.80009 · doi:10.1007/s11081-010-9109-z |
| [2] | Abramson, M.; Audet, C.; Chrissis, J.; Walston, J., Mesh adaptive direct search algorithms for mixed variable optimization, Opt. Letters, 3, 1, 35-47 (2009) · Zbl 1154.90551 · doi:10.1007/s11590-008-0089-2 |
| [3] | Asmussen, S.; Glynn, PW, Stochastic Simulation: Algorithms and Analysis, Stochastic modeling and applied probability (2007), New York: Springer, New York · Zbl 1126.65001 · doi:10.1007/978-0-387-69033-9 |
| [4] | Audet, C.; Dennis, J. Jr, Pattern search algorithms for mixed variable programming, SIAM J. Opt., 11, 3, 573-594 (2000) · Zbl 1035.90048 · doi:10.1137/S1052623499352024 |
| [5] | Billingsley, P., Probability and Measure (1995), New York: Wiley, New York · Zbl 0822.60002 |
| [6] | Bonami, P.; Biegler, L.; Conn, A.; Cornuéjols, G.; Grossmann, I.; Laird, C.; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Opt., 5, 2, 186-204 (2008) · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011 |
| [7] | Bottou, L.; Curtis, FE; Nocedal, J., Optimization methods for large-scale machine learning, SIAM Rev., 60, 2, 223-311 (2018) · Zbl 1397.65085 · doi:10.1137/16M1080173 |
| [8] | Boyd, S.; Vandenberghe, L., Convex Optimization (2004), New York: Cambridge University Press, New York · Zbl 1058.90049 · doi:10.1017/CBO9780511804441 |
| [9] | Chen, CH; Lin, J.; Yücesan, E.; Chick, SE, Simulation budget allocation for further enhancing the efficiency of ordinal optimization, Dis. Event Dyn. Syst., 10, 3, 251-270 (2000) · Zbl 0970.90014 · doi:10.1023/A:1008349927281 |
| [10] | Eubank, S.; Guclu, H.; Kumar, VSA; Marathe, MV; Srinivasan, A.; Toroczkai, Z.; Wang, N., Modelling disease outbreaks in realistic urban social networks, Nature, 429, 180-184 (2004) · doi:10.1038/nature02541 |
| [11] | Gosavi, A.; Ozkaya, E.; Kahraman, AF, Simulation optimization for revenue management of airlines with cancellations and overbooking, OR Spect., 29, 1, 21-38 (2007) · Zbl 1144.90411 · doi:10.1007/s00291-005-0018-z |
| [12] | Hashemi, F., Ghosh, S., Pasupathy, R.: On adaptive sampling rules for stochastic recursions. In: A. Tolk, S.Y. Diallo, I.O. Ryzhov, L. Yilmaz, S. Buckley, J.A. Miller (eds.) Proceedings of the 2014 Winter Simulation Conference, pp. 3959-3970. IEEE, Piscataway, NJ (2014). doi:10.1109/WSC.2014.7020221 |
| [13] | Henderson, S.G., Pasupathy, R.: Simulation optimization library (2021). https://github.com/simopt-admin/simopt/wiki |
| [14] | Hong, LJ; Nelson, BL, Discrete optimization via simulation using COMPASS, Oper. Res., 54, 1, 115-129 (2006) · Zbl 1167.90630 · doi:10.1287/opre.1050.0237 |
| [15] | Hu, L.; Andradottir, S., An asymptotically optimal set approach for simulation optimization, INFORMS J. Comput. (2018) · Zbl 1528.90168 · doi:10.1287/ijoc.2018.0811 |
| [16] | Hunter, S.R., Nelson, B.L.: Parallel ranking and selection. In: A. Tolk, J. Fowler, G. Shao, E. Yücesan (eds.) Advances in Modeling and Simulation: Seminal Research from 50 Years of Winter Simulation Conferences, Simulation Foundations, Methods and Applications, chap. 12, pp. 249-275. Springer International, Switzerland (2017). doi:10.1007/978-3-319-64182-9 · Zbl 1375.00001 |
| [17] | Jalali, H.; Van Nieuwenhuyse, I., Simulation optimization in inventory replenishment: a classification, IIE Trans., 47, 11, 1217-1235 (2015) · doi:10.1080/0740817X.2015.1019162 |
| [18] | Johnson, NL; Kotz, S.; Balakrishnan, N., Continuous Multivariate Distributions (2000), New York: Wiley, New York · Zbl 0946.62001 |
| [19] | Karatzas, I.; Yor, M.; Embrechts, P., Modelling Extremal Events: for Insurance and Finance (1997), Berlin: Springer, Berlin · Zbl 0873.62116 |
| [20] | Kim, S., Pasupathy, R., Henderson, S.G.: A guide to SAA. In: M. Fu (ed.) Encyclopedia of Operations Research and Management Science, Hillier and Lieberman OR Series. Elsevier (2014) |
| [21] | Kim, SH; Nelson, BL; Henderson, SG; Nelson, BL, Selecting the best system, Simulation, Handbooks in Operations Research and Management Science, 501-534 (2006), Amsterdam: Elsevier, Amsterdam · Zbl 1170.90300 |
| [22] | Kleywegt, AJ; Shapiro, A.; Homem-de-Mello, T., The sample average approximation method for stochastic discrete optimization, SIAM J. Opt., 12, 479-502 (2001) · Zbl 0991.90090 · doi:10.1137/S1052623499363220 |
| [23] | Kushner, H.; Yin, GG, Stochastic approximation and recursive algorithms and applications, Stochastic Model. Appl. Prob. (2003) · Zbl 1026.62084 · doi:10.1007/b97441 |
| [24] | Lamiri, M.; Grimaud, F.; Xie, X., Optimization methods for a stochastic surgery planning problem, Int. J. Prod. Econ., 120, 2, 400-410 (2009) · doi:10.1016/j.ijpe.2008.11.021 |
| [25] | Law, AM, Simulation Modeling and Analysis (2015), New York: McGraw Hill Education, New York |
| [26] | Le Digabel, S., Wild, S.M.: A taxonomy of constraints in simulation-based optimization. arXiv (2015). arxiv:1505.07881 |
| [27] | Lee, S.; Nelson, BL, General-purpose ranking and selection for computer simulation, IIE Trans, 48, 6, 555-564 (2016) · doi:10.1080/0740817X.2015.1125043 |
| [28] | Li, P.; Abbas, M.; Pasupathy, R.; Head, L., Simulation-based optimization of maximum green setting under retrospective approximation framework, Transport. Res., 2192, 1-10 (2010) · doi:10.3141/2192-01 |
| [29] | Liuzzi, G.; Lucidi, S.; Rinaldi, F., Derivative-free methods for bound constrained mixed-integer optimization, Dis. Opt., 53, 2, 505-526 (2011) · Zbl 1257.90058 |
| [30] | Liuzzi, G.; Lucidi, S.; Rinaldi, F., Derivative-free methods for mixed-integer constrained optimization problems, J. Opt. Theory Appl., 164, 3, 933-965 (2015) · Zbl 1321.90087 · doi:10.1007/s10957-014-0617-4 |
| [31] | Lorenz, AJ; Chao, S.; Asoro, FG; Heffner, EL; Hayashi, T.; Iwata, H.; Smith, KP; Sorrells, ME; Jannink, JL; Sparks, DL, Genomic selection in plant breeding: Knowledge and prospects, Advances in Agronomy, 77-123 (2011), Elsevier, San Diego, CA: Academic Press, Elsevier, San Diego, CA |
| [32] | Mahajan, S.; van Ryzin, G., Stocking retail assortments under dynamic consumer substitution, Oper. Res., 49, 3, 334-351 (2001) · Zbl 1163.90339 · doi:10.1287/opre.49.3.334.11210 |
| [33] | Murota, K., Discrete convex analysis (2003), Philadelphia: SIAM, Philadelphia · Zbl 1029.90055 · doi:10.1137/1.9780898718508 |
| [34] | Nesterov, Y.: Introductory lectures on convex optimization: A basic course, Applied Optimization, vol. 87. Springer (2004). doi:10.1007/978-1-4419-8853-9 · Zbl 1086.90045 |
| [35] | Newton, D., Yousefian, F., Pasupathy, R.: Stochastic Gradient Descent: Recent Trends, chap. 9, pp. 193-220. INFORMS (2018). doi:10.1287/educ.2018.0191 |
| [36] | Nocedal, J.; Wright, SJ, Numerical Optimization (2006), New York: Springer Series in Operations Research and Financial Engineering. Springer, New York · Zbl 1104.65059 |
| [37] | Pasupathy, R., Ghosh, S.: Simulation optimization: a concise overview and implementation guide. In: H. Topaloglu (ed.) TutORials in Operations Research, chap. 7, pp. 122-150. INFORMS, Catonsville, MD (2013). doi:10.1287/educ.2013.0118 |
| [38] | Pasupathy, R., Henderson, S.G.: A testbed of simulation-optimization problems. In: L.F. Perrone, F.P. Wieland, J. Liu, B.G. Lawson, D.M. Nicol, R.M. Fujimoto (eds.) Proceedings of the 2006 Winter Simulation Conference, pp. 255-263. IEEE, Piscataway, NJ (2006). doi:10.1109/WSC.2006.323081 |
| [39] | Pasupathy, R., Henderson, S.G.: SimOpt: A library of simulation optimization problems. In: S. Jain, R.R. Creasey, J. Himmelspach, K.P. White, M. Fu (eds.) Proceedings of the 2011 Winter Simulation Conference, pp. 4075-4085. IEEE, Piscataway, NJ (2011). doi:10.1109/WSC.2011.6148097 |
| [40] | Pasupathy, R., Schmeiser, B.W.: Root finding via darts: Dynamic adaptive random target shooting. In: B. Johansson, S. Jain, J. Montoya-Torres, J. Hugan, E. Yücesan (eds.) Proceedings of the 2010 Winter Simulation Conference, pp. 1255-1262. Institute of Electrical and Electronics Engineers, Inc., Piscataway, NJ (2010). http://www.informs-sim.org/wsc10papers/115.pdf |
| [41] | Pasupathy, R.; Hunter, SR; Pujowidianto, NA; Lee, LH; Chen, C., Stochastically constrained ranking and selection via SCORE, ACM Trans.Model. Comput. Sim., 25, 1, 1-26 (2015) · Zbl 1371.65059 · doi:10.1145/2630066 |
| [42] | Pasupathy, R.; Glynn, PW; Ghosh, S.; Hashemi, F., On sampling rates in simulation-based recursions, SIAM J. Opt., 28, 1, 45-73 (2018) · Zbl 1380.93168 · doi:10.1137/140951679 |
| [43] | Robbins, H., Siegmund, D.: A convergence theorem for non negative almost super-martingales and some applications. In: J.S. Rustagi (ed.) Optimizing Methods in Statistics, pp. 233-257. Academic Press (1971). doi:10.1016/B978-0-12-604550-5.50015-8 · Zbl 0286.60025 |
| [44] | Salemi, PL; Song, E.; Nelson, BL; Staum, J., Gaussian Markov random fields for discrete optimization via simulation: Framework and algorithms, Oper. Res., 67, 1, 250-266 (2019) · Zbl 1455.90107 · doi:10.1287/opre.2018.1778 |
| [45] | Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on Stochastic Programming: Modeling and Theory (2009), Philadelphia, PA: MPS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 1183.90005 · doi:10.1137/1.9780898718751 |
| [46] | Shashaani, S.; Hashemi, FS; Pasupathy, R., ASTRO-DF: A class of adaptive sampling trust-region algorithms for derivative-free simulation optimization, SIAM J. Opt., 28, 4, 3145-3176 (2018) · Zbl 1403.90541 · doi:10.1137/15M1042425 |
| [47] | Shin, D.; Broadie, M.; Zeevi, A., Tractable sampling strategies for ordinal optimization, Oper. Res., 66, 6, 1693-1712 (2018) · Zbl 1467.62041 · doi:10.1287/opre.2018.1753 |
| [48] | Sun, L.; Hong, LJ; Hu, Z., Balancing exploitation and exploration in discrete optimization via simulation through a gaussian process-based search, Oper. Res., 62, 6, 1416-1438 (2014) · Zbl 1327.90120 · doi:10.1287/opre.2014.1315 |
| [49] | Vershynin, R., High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge Series in Statistical and Probabilistic Mathematics (2018), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 1430.60005 |
| [50] | Wang, H., Pasupathy, R., Schmeiser, B.W.: Integer-ordered simulation optimization using R-SPLINE: Retrospective Search using Piecewise-Linear Interpolation and Neighborhood Enumeration. ACM Transactions on Modeling and Computer Simulation 23(3), 17:1-17:24 (2013). doi:10.1145/2499913.2499916 · Zbl 1386.65167 |
| [51] | Williams, D., Probability with martingales (1991), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 0722.60001 · doi:10.1017/CBO9780511813658 |
| [52] | Xu, J.; Nelson, BL; Hong, LJ, Industrial Strength COMPASS: A comprehensive algorithm and software for optimization via simulation, ACM Trans.Model. Comput. Simul., 20, 1-29 (2010) · Zbl 1386.65034 · doi:10.1145/1667072.1667075 |
| [53] | Zhang, H., Zheng, Z., Lavaei, J.: Discrete convex simulation optimization (2020) |
| [54] | Zhang, H., Zheng, Z., Lavaei, J.: Stochastic localization methods for discrete convex simulation optimization (2020) |
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.
