Stochastic Localization Methods for Convex Discrete Optimization via Simulation

References

• Agarwal A, Foster DP, Hsu DJ, Kakade SM, Rakhlin A (2011) Stochastic convex optimization with bandit feedback. Adv. Neural Inform. Processing Systems, 1035–1043.Google Scholar
• Alman J, Williams VV (2021) A refined laser method and faster matrix multiplication. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 522–539.Google Scholar
• Altman E, Gaujal B, Hordijk A (2003) Discrete-Event Control of Stochastic Networks: Multimodularity and Regularity (Springer, New York).Crossref, Google Scholar
• 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, Google Scholar
• Bertsimas D, Vempala S (2004) Solving convex programs by random walks. J. ACM 51(4):540–556.Crossref, Google Scholar
• Burnetas AN, Katehakis MN (1996) Optimal adaptive policies for sequential allocation problems. Adv. Appl. Math. 17(2):122–142.Crossref, Google Scholar
• Chen L, Gupta A, Li J (2016) Pure exploration of multi-armed bandit under matroid constraints. Conf. Learn. Theory, 647–669.Google Scholar
• Chen X, Li M (2021) Discrete convex analysis and its applications in operations: A survey. Production Oper. Management 30(6):1904–1926.Crossref, Google Scholar
• Dyer M, Proll L (1977) Note-on the validity of marginal analysis for allocating servers in m/m/c queues. Management Sci. 23(9):1019–1022.Link, Google Scholar
• Eckman DJ, Henderson SG (2018) Fixed-confidence, fixed-tolerance guarantees for selection-of-the-best procedures. Working paper, School of Operations Research and Information Engineering, Cornell University, Ithaca, NY.Google Scholar
• Eckman DJ, Plumlee M, Nelson BL (2022) Plausible screening using functional properties for simulations with large solution spaces. Oper. Res. 70(6):3473–3489.Google Scholar
• Eckman DJ, Plumlee M, Nelson BL (2021) Flat chance! Using stochastic gradient estimators to assess plausible optimality for convex functions. 2021 Winter Simulation Conf. (IEEE, Piscataway, NJ), 1–18.Google Scholar
• Even-Dar E, Mannor S, Mansour Y (2002) PAC bounds for multi-armed bandit and Markov decision processes. Internat. Conf. Comput. Learn. Theory (Springer, New York), 255–270.Google Scholar
• Freund D, Henderson SG, Shmoys DB (2017) Minimizing multimodular functions and allocating capacity in bike-sharing systems. Internat. Conf. Integer Programming Combin. Optim. (Springer, New York), 186–198.Google Scholar
• Fujishige S (2005) Submodular Functions and Optimization (Elsevier, Amsterdam).Google Scholar
• Gong X, Chao X (2013) Optimal control policy for capacitated inventory systems with remanufacturing. Oper. Res. 61(3):603–611.Link, Google Scholar
• Günlük O (1999) A branch-and-cut algorithm for capacitated network design problems. Math. Programming 86(1):17–39.Crossref, Google Scholar
• Hong LJ, Nelson BL (2006) Discrete optimization via simulation using compass. Oper. Res. 54(1):115–129.Link, Google Scholar
• Hong LJ, Zhang X (2021) Surrogate-based simulation optimization. Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications, 287–311.Link, Google Scholar
• Hong LJ, Fan W, Luo J (2021) Review on ranking and selection: A new perspective. Front. Eng. Manag. 8(3):321–343. Google Scholar
• Hong LJ, Nelson BL, Xu J (2015) Discrete optimization via simulation. Fu MC, ed. Handbook of Simulation Optimization (Springer, New York), 9–44.Crossref, Google Scholar
• Huh WT, Janakiraman G (2010) On the optimal policy structure in serial inventory systems with lost sales. Oper. Res. 58(2):486–491.Link, Google Scholar
• Jamieson K, Malloy M, Nowak R, Bubeck S (2014) lil-UCB: An optimal exploration algorithm for multi-armed bandits. Conf. Learn. Theory, 423–439.Google Scholar
• Jian N, Freund D, Wiberg HM, Henderson SG (2016) Simulation optimization for a large-scale bike-sharing system. 2016 Winter Simulation Conf. (IEEE, Piscataway, NJ), 602–613.Google Scholar
• Jiang H (2021) Minimizing convex functions with integral minimizers. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 976–985.Google Scholar
• Jiang H, Lee YT, Song Z, Wong SCW (2020) An improved cutting plane method for convex optimization, convex-concave games, and its applications. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput., 944–953.Google Scholar
• Karnin Z, Koren T, Somekh O (2013) Almost optimal exploration in multi-armed bandits. Internat. Conf. Machine Learn., 1238–1246.Google Scholar
• Kaufmann E, Cappé O, Garivier A (2016) On the complexity of best-arm identification in multi-armed bandit models. J. Machine Learn. Res. 17(1):1–42.Google Scholar
• Lai TL, Robbins H (1985) Asymptotically efficient adaptive allocation rules. Adv. Appl. Math. 6(1):4–22.Crossref, Google Scholar
• Lee JCH, Valiant P (2022) Optimal sub-Gaussian mean estimation in R. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, Piscataway, NJ), 672–683.Google Scholar
• Lee YT, Sidford A, Wong SCW (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. 2015 IEEE 56th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 1049–1065.Google Scholar
• Lenstra AK, Lenstra HW, Lovász L (1982) Factoring polynomials with rational coefficients. Mathematische Annalen 261:515–534.Crossref, Google Scholar
• Liang T, Narayanan H, Rakhlin A (2014) On zeroth-order stochastic convex optimization via random walks. Preprint, submitted February 11, https://arxiv.org/abs/1402.2667.Google Scholar
• Lovász L (1983) Submodular functions and convexity. Mathematical Programming the State of the Art (Springer, New York), 235–257.Crossref, Google Scholar
• Luo J, Hong LJ, Nelson BL, Wu Y (2015) Fully sequential procedures for large-scale ranking-and-selection problems in parallel computing environments. Oper. Res. 63(5):1177–1194.Link, Google Scholar
• Ma S, Henderson SG (2017) An efficient fully sequential selection procedure guaranteeing probably approximately correct selection. 2017 Winter Simulation Conf. (IEEE, Piscataway, NJ), 2225–2236.Google Scholar
• Ma S, Henderson SG (2019) Predicting the simulation budget in ranking and selection procedures. ACM Trans. Model. Comput. Simulation 29(3):1–25.Crossref, Google Scholar
• Murota K (2003) Discrete Convex Analysis (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Nelson BL (2010) Optimization via simulation over discrete decision variables. Risk and Optimization in an Uncertain World (INFORMS, Catonsville, MD), 193–207.Link, Google Scholar
• Ni EC, Ciocan DF, Henderson SG, Hunter SR (2017) Efficient ranking and selection in high performance computing environments. Oper. Res. 65(3):821–836.Link, Google Scholar
• Pang Z, Chen FY, Feng Y (2012) A note on the structure of joint inventory-pricing control with leadtimes. Oper. Res. 60(3):581–587.Link, Google Scholar
• Ragavan PK, Hunter SR, Pasupathy R, Taaffe MR (2022) Adaptive sampling line search for local stochastic optimization with integer variables. Math. Programming 196(1–2):775–804.Crossref, Google Scholar
• Shaked M, Shanthikumar JG (1988) Stochastic convexity and its applications. Adv. Appl. Probab. 20(2):427–446.Crossref, Google Scholar
• Shi L, Olafsson S (2000) Nested partitions method for stochastic optimization. Methodology Comput. Appl. Probab. 2(3):271–291.Crossref, Google Scholar
• Singhvi D, Singhvi S, Frazier PI, Henderson SG, O’Mahony E, Shmoys DB, Woodard DB (2015) Predicting bike usage for New York City’s bike sharing system. AAAI Workshop: Comput. Sustainability (AAAI Press, Palo Alto, CA).Google Scholar
• Sun L, Hong LJ, Hu Z (2014) Balancing exploitation and exploration in discrete optimization via simulation through a Gaussian process-based search. Oper. Res. 62(6):1416–1438.Link, Google Scholar
• Vaidya PM (1996) A new algorithm for minimizing convex functions over convex sets. Math. Programming 73(3):291–341.Crossref, Google Scholar
• Wainwright MJ (2019) High-Dimensional Statistics: A Non-Asymptotic Viewpoint, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 48 (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Wang H, Pasupathy R, Schmeiser BW (2013) Integer-ordered simulation optimization using r-spline: Retrospective search with piecewise-linear interpolation and neighborhood enumeration. ACM Trans. Model. Comput. Simulation 23(3):1–24.Crossref, Google Scholar
• Wang T, Xu J, Hu JQ, Chen CH (2021) Optimal computing budget allocation for regression with gradient information. Automatica J. IFAC 134:109927.Crossref, Google Scholar
• Wolff RW, Wang CL (2002) On the convexity of loss probabilities. J. Appl. Probab. 39(2):402–406.Crossref, Google Scholar
• Xu WL, Nelson BL (2013) Empirical stochastic branch-and-bound for optimization via simulation. IIE Trans. 45(7):685–698.Crossref, Google Scholar
• Xu J, Zheng Z (2023) Gradient-based simulation optimization algorithms via multi-resolution system approximations. INFORMS J. Comput. 35(3):633–651.Google Scholar
• Xu Y, Lin Q, Yang T (2019) Accelerate stochastic subgradient method by leveraging local growth condition. Anal. Appl. 17(5): 773–818.Google Scholar
• Xu J, Nelson BL, Hong JL (2010) Industrial strength compass: A comprehensive algorithm and software for optimization via simulation. ACM Trans. Model. Comput. Simulation 20(1):1–29.Google Scholar
• Zhong Y, Hong LJ (2022) Knockout-tournament procedures for largescale ranking and selection in parallel computing environments. Oper. Res. 70(1):432–453.Google Scholar
• Zhang H, Zheng Z, Lavaei J (2021) Stochastic l♮-convex function minimization. Adv. Neural Inform. Processing Systems, vol. 34 (NIPS, San Diego, CA), 13004–13018.Google Scholar
• Zhang H, Zheng Z, Lavaei J (2022) Gradient-based algorithms for convex discrete optimization via simulation. Oper. Res 71(5):1815–1834.Google Scholar
• Zipkin P (2008) On the structure of lost-sales inventory models. Oper. Res. 56(4):937–944.Link, Google Scholar