{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T14:40:10Z","timestamp":1730990410758,"version":"3.28.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T00:00:00Z","timestamp":1729036800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T00:00:00Z","timestamp":1729036800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a new algorithm Directional Optimization Search with Surrogate (DOSS), for optimizing problems with box constraints and a computationally expensive black-box objective function. DOSS is a radial basis function (RBF) based method that mainly focuses on higher dimensional and computationally expensive objective functions that can be multimodal. DOSS introduces three new techniques not previously used in earlier RBF algorithms, including using a combination of the coordinates knowledge level, fewer initial sampling points, and the surrogate\u2019s gradient information. Numerical results on a test set including 14 test problems with 36, 48, and 60 dimensions show that DOSS outperforms two recently published algorithms RBFOpt and TuRBO, and earlier RBF algorithms such as DYCORS. TuRBO is a Gaussian process based optimization algorithm, which outperformed earlier state-of-the-art methods. DOSS algorithm also has a good performance on real-world optimization problems, including robot pushing and rover trajectory planning problems. Almost sure convergence for the DOSS algorithm is also proven in this paper. An implementation of DOSS is available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/doi.org\/10.5281\/zenodo.13731558\">https:\/\/doi.org\/10.5281\/zenodo.13731558<\/jats:ext-link>.<\/jats:p>","DOI":"10.1007\/s12532-024-00267-7","type":"journal-article","created":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T08:02:15Z","timestamp":1729065735000},"page":"665-693","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving higher dimensional expensive black box global optimization problems using sparse directional search on surrogates"],"prefix":"10.1007","volume":"16","author":[{"given":"Limeng","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Muming","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christine A.","family":"Shoemaker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tingting","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,16]]},"reference":[{"issue":"2","key":"267_CR1","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s10898-007-9234-1","volume":"41","author":"C Audet","year":"2008","unstructured":"Audet, C., B\u00e9chard, V., Le Digabel, S.: Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search. Journal of Global Optimization 41(2), 299\u2013318 (2008)","journal-title":"Journal of Global Optimization"},{"key":"267_CR2","doi-asserted-by":"crossref","unstructured":"Binois, M., Ginsbourger, D., Roustant, O.: A warped kernel improving robustness in bayesian optimization via random embeddings. In: International Conference on Learning and Intelligent Optimization, pp. 281\u2013286. Springer (2015)","DOI":"10.1007\/978-3-319-19084-6_28"},{"issue":"1","key":"267_CR3","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s10898-019-00839-1","volume":"76","author":"M Binois","year":"2020","unstructured":"Binois, M., Ginsbourger, D., Roustant, O.: On the choice of the low-dimensional domain for global optimization via random embeddings. Journal of global optimization 76(1), 69\u201390 (2020)","journal-title":"Journal of global optimization"},{"issue":"4","key":"267_CR4","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1023\/A:1011584207202","volume":"1","author":"M Bj\u00f6rkman","year":"2000","unstructured":"Bj\u00f6rkman, M., Holmstr\u00f6m, K.: Global optimization of costly nonconvex functions using radial basis functions. Optimization and Engineering 1(4), 373\u2013397 (2000)","journal-title":"Optimization and Engineering"},{"key":"267_CR5","unstructured":"Chen, B., Castro, R., Krause, A.: Joint optimization and variable selection of high-dimensional gaussian processes. arXiv preprint arXiv:1206.6396 (2012)"},{"issue":"2","key":"267_CR6","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Mathematical programming 91(2), 201\u2013213 (2002)","journal-title":"Mathematical programming"},{"key":"267_CR7","unstructured":"Eriksson, D., Bindel, D., Shoemaker, C.A.: pysot and poap: An event-driven asynchronous framework for surrogate optimization. arXiv preprint arXiv:1908.00420 (2019)"},{"key":"267_CR8","unstructured":"Eriksson, D., Pearce, M., Gardner, J., Turner, R.D., Poloczek, M.: Scalable global optimization via local Bayesian optimization. In: Advances in Neural Information Processing Systems, pp. 5496\u20135507 (2019). http:\/\/papers.nips.cc\/paper\/8788-scalable-global-optimization-via-local-bayesian-optimization.pdf"},{"key":"267_CR9","unstructured":"Gardner, J., Guo, C., Weinberger, K., Garnett, R., Grosse, R.: Discovering and exploiting additive structure for bayesian optimization. In: Artificial Intelligence and Statistics, pp. 1311\u20131319. PMLR (2017)"},{"issue":"2","key":"267_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2950048","volume":"43","author":"N Gould","year":"2016","unstructured":"Gould, N., Scott, J.: A note on performance profiles for benchmarking software. ACM Transactions on Mathematical Software (TOMS) 43(2), 1\u20135 (2016)","journal-title":"ACM Transactions on Mathematical Software (TOMS)"},{"issue":"3","key":"267_CR11","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1023\/A:1011255519438","volume":"19","author":"HM Gutmann","year":"2001","unstructured":"Gutmann, H.M.: A radial basis function method for global optimization. Journal of global optimization 19(3), 201\u2013227 (2001)","journal-title":"Journal of global optimization"},{"key":"267_CR12","unstructured":"Hansen, N., Ostermeier, A.: Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In: Proceedings of IEEE international conference on evolutionary computation, pp. 312\u2013317. IEEE (1996)"},{"issue":"2","key":"267_CR13","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1162\/106365601750190398","volume":"9","author":"N Hansen","year":"2001","unstructured":"Hansen, N., Ostermeier, A.: Completely derandomized self-adaptation in evolution strategies. Evolutionary computation 9(2), 159\u2013195 (2001)","journal-title":"Evolutionary computation"},{"issue":"4","key":"267_CR14","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1023\/A:1008306431147","volume":"13","author":"DR Jones","year":"1998","unstructured":"Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. Journal of Global optimization 13(4), 455\u2013492 (1998)","journal-title":"Journal of Global optimization"},{"key":"267_CR15","unstructured":"Kandasamy, K., Schneider, J., P\u00f3czos, B.: High dimensional bayesian optimisation and bandits via additive models. In: International conference on machine learning, pp. 295\u2013304. PMLR (2015)"},{"issue":"4","key":"267_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1916461.1916468","volume":"37","author":"S Le Digabel","year":"2011","unstructured":"Le Digabel, S.: Algorithm 909: Nomad: Nonlinear optimization with the mads algorithm. ACM Transactions on Mathematical Software (TOMS) 37(4), 1\u201315 (2011)","journal-title":"ACM Transactions on Mathematical Software (TOMS)"},{"issue":"1","key":"267_CR17","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1137\/080724083","volume":"20","author":"JJ Mor\u00e9","year":"2009","unstructured":"Mor\u00e9, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization 20(1), 172\u2013191 (2009)","journal-title":"SIAM Journal on Optimization"},{"key":"267_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.5802\/ojmo.3","volume":"2","author":"G Nannicini","year":"2021","unstructured":"Nannicini, G.: On the implementation of a global optimization method for mixed-variable problems. Open Journal of Mathematical Optimization 2, 1\u201325 (2021)","journal-title":"Open Journal of Mathematical Optimization"},{"key":"267_CR19","doi-asserted-by":"crossref","unstructured":"Powell, M.: The theory of radial basis function approximation in 1990, advances in numerical analysis ii: Wavelets, subdivision, and radial functions (wa light, ed.). Oxford University Press, Oxford 105, 210 (1992)","DOI":"10.1093\/oso\/9780198534396.003.0003"},{"issue":"5","key":"267_CR20","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1016\/j.cor.2010.09.013","volume":"38","author":"RG Regis","year":"2011","unstructured":"Regis, R.G.: Stochastic radial basis function algorithms for large-scale optimization involving expensive black-box objective and constraint functions. Computers & Operations Research 38(5), 837\u2013853 (2011)","journal-title":"Computers & Operations Research"},{"issue":"4","key":"267_CR21","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1287\/ijoc.1060.0182","volume":"19","author":"RG Regis","year":"2007","unstructured":"Regis, R.G., Shoemaker, C.A.: A stochastic radial basis function method for the global optimization of expensive functions. INFORMS Journal on Computing 19(4), 497\u2013509 (2007)","journal-title":"INFORMS Journal on Computing"},{"issue":"5","key":"267_CR22","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1080\/0305215X.2012.687731","volume":"45","author":"RG Regis","year":"2013","unstructured":"Regis, R.G., Shoemaker, C.A.: Combining radial basis function surrogates and dynamic coordinate search in high-dimensional expensive black-box optimization. Engineering Optimization 45(5), 529\u2013555 (2013)","journal-title":"Engineering Optimization"},{"key":"267_CR23","unstructured":"Wang, J., Clark, S.C., Liu, E., Frazier, P.I.: Parallel bayesian global optimization of expensive functions. arXiv preprint arXiv:1602.05149 (2016)"},{"key":"267_CR24","unstructured":"Wang, Z., Gehring, C., Kohli, P., Jegelka, S.: Batched large-scale bayesian optimization in high-dimensional spaces. In: International Conference on Artificial Intelligence and Statistics, pp. 745\u2013754. PMLR (2018)"},{"key":"267_CR25","unstructured":"Wu, J., Poloczek, M., Wilson, A.G., Frazier, P.I.: Bayesian optimization with gradients. arXiv preprint arXiv:1703.04389 (2017)"},{"issue":"2","key":"267_CR26","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1287\/opre.2016.1480","volume":"64","author":"J Xie","year":"2016","unstructured":"Xie, J., Frazier, P.I., Chick, S.E.: Bayesian optimization via simulation with pairwise sampling and correlated prior beliefs. Operations Research 64(2), 542\u2013559 (2016)","journal-title":"Operations Research"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-024-00267-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-024-00267-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-024-00267-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T14:14:48Z","timestamp":1730988888000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-024-00267-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,16]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["267"],"URL":"https:\/\/doi.org\/10.1007\/s12532-024-00267-7","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"type":"print","value":"1867-2949"},{"type":"electronic","value":"1867-2957"}],"subject":[],"published":{"date-parts":[[2024,10,16]]},"assertion":[{"value":"8 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}