{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:34:10Z","timestamp":1787340850898,"version":"build-2736575974"},"reference-count":60,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We consider unconstrained optimization problems where only \u201cstochastic\u201d estimates of the objective function are observable as replicates from a Monte Carlo oracle. The Monte Carlo oracle is assumed to provide no direct observations of the function gradient. We present ASTRO-DF---a class of derivative-free trust-region algorithms, where a stochastic local model is constructed, optimized, and updated iteratively. Function estimation and model construction within ASTRO-DF is adaptive in the sense that the extent of Monte Carlo sampling is determined by continuously monitoring and balancing measures of sampling error (or variance) and structural error (or model bias) within ASTRO-DF. Such balancing of errors is designed to ensure that Monte Carlo effort within ASTRO-DF is sensitive to algorithm trajectory: sampling is higher whenever an iterate is inferred to be close to a critical point and lower when far away. We demonstrate the almost sure convergence of ASTRO-DF's iterates to first-order critical points when using stochastic polynomial interpolation models. The question of using more complicated models, e.g., regression or stochastic kriging, in combination with adaptive sampling is worth further investigation and will benefit from the methods of proof presented here. We speculate that ASTRO-DF's iterates achieve the canonical Monte Carlo convergence rate, although a proof remains elusive.<\/jats:p>","DOI":"10.1137\/15m1042425","type":"journal-article","created":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T15:37:40Z","timestamp":1543333060000},"page":"3145-3176","source":"Crossref","is-referenced-by-count":67,"title":["ASTRO-DF: A Class of Adaptive Sampling Trust-Region Algorithms for Derivative-Free Stochastic Optimization"],"prefix":"10.1137","volume":"28","author":[{"given":"Sara","family":"Shashaani","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fatemeh S.","family":"Hashemi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raghu","family":"Pasupathy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,11,27]]},"reference":[{"key":"atypb1","first-page":"1","author":"Alagoz O.","year":"2009","journal-title":"MA"},{"key":"atypb2","unstructured":"B. D. Amos, D. R. Easterling, L. T. Watson, W. I. Thacker, B. S. Castle, and M. W. Trosset,\n                      Algorithm XXX: QNSTOP-Quasi Newton Algorithm for Stochastic Optimization\n                      , preprint,https:\/\/vtechworks.lib.vt.edu\/bitstream\/handle\/10919\/49672\/qnTOMS14.pdf, 2014."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0754"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"S. Asmussen and P. W. Glynn,\n                      Stochastic Simulation: Algorithms and Analysis\n                      , Stoch. Model. Appl. Probab. 57, Springer, New York, 2007.","DOI":"10.1007\/978-0-387-69033-9"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/130915984"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0708-6"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s10287-005-0044-y"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0720-x"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.0926"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/090773143"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. S. Bazaara, H. Sherali, and C. M. Shetty,\n                      Nonlinear Programming: Theory and Algorithms\n                      , John Wiley, New York, 2006.","DOI":"10.1002\/0471787779"},{"key":"atypb12","unstructured":"P. Billingsley,\n                      Probability and Measure\n                      , John Wiley, New York, 1995."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/100814688"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728794"},{"key":"atypb15","unstructured":"V. S. Borkar,\n                      Stochastic Approximation: A Dynamical Systems Viewpoint\n                      , Cambridge University Press, Cambridge, 2008."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080173"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. Broadie, D. M. Cicek, and A. Zeevi,\n                      An adaptive multidimensional version of the Kiefer-Wolfowitz stochastic approximation algorithm\n                      , in Proceedings of the 2009 Winter Simulation Conference, M. D. Rossetti, R. R. Hill, B. Johansson, A. Dunkin, and R. G. Ingalls, eds., IEEE Press, Piscataway, NJ, 2009, pp. 601-612.","DOI":"10.1109\/WSC.2009.5429708"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.0970"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1120.0498"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1141-8"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177700156"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"A. R. Conn, N. I. M. Gould, and P. L. Toint,\n                      Trust-Region Methods\n                      , MOS-SIAM Ser. Optim., SIAM, Philadelphia, PA, 2000.","DOI":"10.1137\/1.9780898719857"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0073-5"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drn046"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/060673424"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"A. R. Conn, K. Scheinberg, and L. N. Vicente,\n                      Introduction to Derivative-Free Optimization\n                      , MOS-SIAM Ser. Optim. 8, SIAM, Philadelphia, PA, 2009.","DOI":"10.1137\/1.9780898718768"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"G. Deng and M. C. Ferris,\n                      Adaptation of the UOBYQA Algorithm for Noisy Functions\n                      , in Proceedings of the 38th Conference on Winter Simulation, Monterey, CA, 2006, pp. 312-319.","DOI":"10.1109\/WSC.2006.323088"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0164-y"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"R. Durrett,\n                      Probability: Theory and Examples\n                      , Cambridge University Press, New York, 2010.","DOI":"10.1017\/CBO9780511779398"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"R. Garmanjani, D. J\u00fadice, and L. N. Vicente,\n                      Trust-Region Methods Without Using Derivatives: Worst Case Complexity and the Non-Smooth Case\n                      , preprint,https:\/\/www.mat.uc.pt\/~lnv\/papers\/str.pdf, 2015.","DOI":"10.1137\/151005683"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1080\/03610927908827789"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"M. Ghosh, N. Mukhopadhyay, and P. K. Sen,\n                      Sequential Estimation\n                      , Wiley Ser. Probab. Stat., 1997.","DOI":"10.1002\/9781118165928"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"Y. T. Hou, Y. Shi, and H. D. Sherali,\n                      Applied Optimization Methods for Wireless Networks\n                      , Cambridge University Press, Cambridge, 2014.","DOI":"10.1017\/CBO9781139088466"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729392"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"S. Kim, R. Pasupathy, and S. G. Henderson,\n                      A Guide to sample average approximation\n                      , in Handbook of Simulation Optimization, Internat. Ser. Oper. Res. Management Sci. 216, Fu M. (ed.), Springer, New York, NY, 2015.","DOI":"10.1007\/978-1-4939-1384-8_8"},{"key":"atypb36","unstructured":"H. J. Kushner and G. G. Yin,\n                      Stochastic Approximation and Recursive Algorithms and Applications\n                      , Springer, New York, 2003."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-016-9827-z"},{"key":"atypb38","unstructured":"J. M. Larson,\n                      Derivative-Free Optimization of Noisy Functions\n                      , Ph.D. thesis, Department of Applied Mathematics, University of Colorado, Denver, CO, 2012."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00054-6"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1137\/080718395"},{"key":"atypb41","unstructured":"J. Nocedal and S. J. Wright,\n                      Numerical Optimization\n                      , Springer, Berlin, 2006."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0067164"},{"key":"atypb43","unstructured":"C. Osorio and M. Bierlaire,\n                      A Surrogate Model for Traffic Optimization of Congested Networks: An Analytic Queueing Network Approach\n                      , Report TRANSP-OR 90825, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, France, 2009."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0773"},{"key":"atypb45","first-page":"122","author":"Pasupathy R.","year":"2013","journal-title":"MD"},{"key":"atypb46","unstructured":"R. Pasupathy, P. W. Glynn, S. G. Ghosh, and F. S. Hahemi,\n                      On Sampling Rates in Simulation-Based Recursions\n                      , preprint,http:\/\/www.optimization-online.org\/DB_HTML\/2016\/03\/5361.html, 2017."},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"R. Pasupathy and S. G. Henderson,\n                      A testbed of simulation-optimization problems\n                      , in Proceedings of the 2006 Winter Simulation Conference, IEEE Press, Piscataway, NJ, pp. 255-263.","DOI":"10.1109\/WSC.2006.323081"},{"key":"atypb48","first-page":"4075","author":"Pasupathy R.","year":"2011","journal-title":"NJ"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1145\/1502787.1502788"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1137\/0330046"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100290"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729586"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1163"},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"A. Ruszczynski and A. Shapiro, eds.\n                      Stochastic Programming\n                      , Handbooks Oper. Res. Management Sci. 10, Elsevier, New York, 2003.","DOI":"10.1016\/S0927-0507(03)10001-1"},{"key":"atypb55","doi-asserted-by":"crossref","unstructured":"R. J. Serfling,\n                      Approximation Theorems of Mathematical Statistics\n                      , John Wiley, New York, 1980.","DOI":"10.1002\/9780470316481"},{"key":"atypb56","doi-asserted-by":"crossref","unstructured":"A. Shapiro, D. Dentcheva, and A. Ruszczynski,\n                      Lectures on Stochastic Programming: Modeling and Theory\n                      , SIAM, Philadelphia, PA, 2009.","DOI":"10.1137\/1.9780898718751"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2000.880982"},{"key":"atypb58","doi-asserted-by":"crossref","unstructured":"J. C. Spall,\n                      Introduction to Stochastic Search and Optimization\n                      , John Wiley, Hoboken, NJ, 2003.","DOI":"10.1002\/0471722138"},{"key":"atypb59","doi-asserted-by":"crossref","unstructured":"M. L. Stein,\n                      Interpolation of Spatial Data: Some Theory for Kriging\n                      , Springer, New York, 1999.","DOI":"10.1007\/978-1-4612-1494-6"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2011.09.043"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1042425","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:52:25Z","timestamp":1787338345000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1042425"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":60,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/15M1042425"],"URL":"https:\/\/doi.org\/10.1137\/15m1042425","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}