Note from the Editor

Introduction

In this issue, we recognize two outstanding papers published in INFORMS Journal on Computing (IJOC). One is recent, whereas the other appeared nearly two decades earlier.

Recognized as a Meritorious Paper is “An Efficient Node Selection Policy for Monte Carlo Tree Search with Neural Networks” by Xiaotian Liu, Yijie Peng, Gongbo Zhang, and Ruihan Zhou (Liu et al. 2024b). In the words of the associate editor, “This paper combines the sequential sampling policy proved to show good asymptotic behavior in solving the classical ranking and selection (R&S) problem to improve the Monte Carlo Tree Search algorithm popular in reinforcement learning. The algorithm is supported by the theoretical advantage of the sequential sampling algorithm in solving the R&S algorithm over the popular upper confidence bounds applied to the tree (UCT) sampling rule. Given the timeliness and contribution of this paper, the paper is nominated for meritorious recognition.”

For the more historic paper, we continue to announce the winners of the IJOC Test of Time Paper Award to cover the backlog of awards since the journal’s inception. The energetic and able committee chaired by John Chinneck, with members Bill Cook, Bruce Golden, Karla Hoffman, and David Woodruff, has selected the awardees, Rommel Regis and Christine Shoemaker, covering the period 2005–2009. What follows is the citation from the award committee and then, a reflective interview with the authors concerning this paper.

I want to thank the committee for their superb efforts and am very pleased to share this recognition of the impactful heritage of our journal.

All my best,

The Test of Time Award for papers published in the INFORMS Journal on Computing in the years 2005–2009 is awarded to

A Stochastic Radial Basis Function Method for the Global Optimization of Expensive Functions

Rommel G. Regis and Christine A. Shoemaker

INFORMS Journal on Computing 19(4):497–509, 2007

https://pubsonline.informs.org/doi/10.1287/ijoc.1060.0182

Test of Time Award Citation 2005–2009

The authors propose and test methods for solving global optimization problems in which the function to be minimized is expensive to compute. It can be thought of as a black-box function or a simulation experiment. A single objective function evaluation can take hours, and derivatives may not be available. The authors propose two stochastic radial basis function (RBF) methods in which the expensive objective function evaluations are approximated by a surrogate model. The surrogate model allows for a stochastic and much more extensive exploration of the solution space. These new methods are tested against six alternative global optimization methods on 17 multimodal test problems and a real-world groundwater bioremediation application involving partial differential equations. Their multistart local metric stochastic RBF (MSRBF) algorithm is the overall winner. This highly cited article is noteworthy for several reasons. First, the authors tackle a difficult and general optimization problem. Second, they develop new algorithms and prove a convergence result. Third, they carry out comprehensive computational experiments. Finally, the success of the new algorithms demonstrates that they can be applied to other real-world optimization problems.

Please note the link included in their retrospective of the newly established IJOC GitHub repository with the code associated with this landmark paper.

Reflections on “A Stochastic Radial Basis Function Method for the Global Optimization of Expensive Functions” by Rommel G. Regis and Christine A. Shoemaker (June 2025)

We greatly appreciate the selection of our paper “A Stochastic Radial Basis Function Method for the Global Optimization of Expensive Functions” (Regis and Shoemaker 2007) for the INFORMS Journal of Computing Test of Time Paper Award for 2005–2009. We thank the award committee, the Editor-in-Chief, and the journal for this honor and for their support. This paper was one of the PhD dissertation papers of Rommel Regis completed under the supervision of Prof. Christine Shoemaker, who had both operations research and environmental engineering PhD students, at Cornell University. At the time the project was undertaken, Shoemaker was supported by grants from the Computer and Information Science and Engineering (CISE) and the Engineering Directorates at National Science Foundation (NSF), which also funded a research assistantship for Regis. In addition, during the early stages of the project, Regis was funded by a research assistantship provided by Cornell’s Intelligent Information Systems Institute directed by Prof. Carla Gomes.

The initial version of this paper was written in 2003, and around that time, Shoemaker had been helping her environmental engineering graduate students find approximate solutions to computationally expensive, simulation-based optimization problems that require solving partial differential equation models to compute the objective function. The goal was to find the best set of parameter values of a complex numerical simulation model to fit observed data. The simulation model was expensive to compute, with each objective function evaluation taking multiple hours on a desktop computer at that time. Hence, an optimization run that used even just a moderate number of function evaluations took several days. In general, simulation-based objective functions are not guaranteed to be convex, and accurate gradient information is often unavailable or difficult to obtain. These functions are typically treated as black boxes, meaning that mathematical expressions for the objective function and its gradient are not explicitly available and that no special properties that can be exploited are known about the function.

Among the most popular optimization approaches at the time for nonconvex black-box functions for which accurate derivative information was difficult to obtain were metaheuristic methods, such as genetic and evolutionary algorithms. However, because typical implementations of evolutionary algorithms require a large number of function evaluations, optimizing computationally expensive simulation-based black-box objective functions in this manner would not be efficient. Regis and Shoemaker and others (e.g., Jones et al. 1998, Gutmann 2001) thought that a better approach would be to approximate the expensive black-box function using a response surface model or function approximation model, now commonly referred to as a surrogate model. This model is built using data from function evaluations at a relatively small number of space-filling design points. However, instead of simply optimizing the surrogate and taking that as the final solution to the original optimization problem, they considered iterative algorithms that use the surrogate to identify promising points for subsequent function evaluations, dynamically updating the surrogate as new data are gathered during the search for an optimal solution. This approach falls under derivative-free optimization methods because it does not use gradients of the black-box function. However, approximate gradients can be easily obtained from the surrogate model, which provides even more information to guide the search for an optimal solution. It is worth noting that evolutionary and metaheuristic methods have also been assisted by surrogates, resulting in significantly improved performance on computationally expensive problems (e.g., Regis and Shoemaker 2004).

Shoemaker came across an article by Björkman and Holmström (2000), which implements the radial basis function method for global optimization by Gutmann (2001) to solve a train design optimization problem and some benchmark test problems. Regis began implementing this RBF method in MATLAB and experimented with its performance on the same test problems. We found that this particular RBF algorithm incurred significant computational overhead, especially if one tries to thoroughly solve the global optimization subproblem needed to determine the next function evaluation point in every iteration. This limited the applicability of the algorithm to low-dimensional problems and made it time consuming to do multiple trial runs to thoroughly assess the algorithm on any given test problem. Regis and Shoemaker then started developing alternatives to address these difficulties. In one approach, they tried avoided the costly step of exhaustively solving the global optimization subproblem. Instead, they simply selected a promising point from a randomly generated set of points according to a weighted combination of a response surface criterion and a distance criterion. This gave rise to the metric stochastic response surface (MSRS) method (Regis and Shoemaker 2007), which is a general framework that can be implemented in a multitude of ways by specifying the probability distribution for the generation of candidate points, the metric for quantifying distance between sample points, and the response surface or surrogate model to approximate the objective function. In addition, because some surrogate-based methods for global optimization get stalled for some choices of the initial space-filling design, a multistart strategy was sometimes incorporated to obtain more consistent performance in finding near-optimal solutions.

The initial version of the paper did not include a convergence proof. When Prof. Shane Henderson from Cornell’s School of Operations Research and Information Engineering became aware of our work, he suggested that we prove the convergence of the algorithm using a theorem on random search from Spall (2003). We came up with a convergence proof for an algorithmic framework that was more general than the MSRS method under some mild conditions on the objective function and the probability distributions that generate the random vector iterates using an extension of the ideas from Spall (2003). This probabilistic convergence proof was incorporated in the revision of the paper, and we are grateful to Prof. Henderson for this valuable suggestion.

To assess the effectiveness of the MSRS framework, we carried out many time-consuming computational experiments. An RBF surrogate was used for the MSRS method. Global and local implementations (named global MSRBF and multistart local MSRBF) were compared with alternative approaches that were popular at the time on many test problems and on a groundwater bioremediation application (Yoon and Shoemaker 1999). The comparison algorithms included the RBF method by Gutmann (2001), the derivative-free trust region method unconstrained optimization by quadratic approximation (UOBYQA) (Powell 2002), a pattern search algorithm (Torczon 1997), and multistart sequential quadratic programming that uses finite difference derivatives. At the time, papers on surrogate-based optimization typically performed numerical experiments on only a small number of low-dimensional test problems and only a few trial runs for each test problem because of the enormous computational cost of these experiments. Because the MSRBF algorithms had significantly much lower overhead run times compared with other surrogate-based methods at that time, we were able to easily apply them to a larger set of problems that includes a 14-dimensional multimodal test problem and a 12-dimensional groundwater bioremediation application. These problems both have much higher dimensionality than the test functions used in prior papers on surrogate-based optimization. Moreover, we conducted 30 trial runs of each algorithm on each test function, providing a more reliable estimate of performance. The results showed that multistart local MSRBF outperformed the other methods, especially on the higher-dimensional problems when computational budgets are severely limited. Additionally, global MSRBF was competitive with the alternatives on most of the lower-dimensional problems with 10 dimensions or less.

The stochastic RBF method (Regis and Shoemaker 2007) gave rise to several extensions that have also been successfully applied to a variety of engineering optimization problems. These extensions include parallel stochastic RBF (Regis and Shoemaker 2009), constrained local metric stochastic radial basis function (ConstrLMSRBF) method (Regis 2011), and dynamic coordinate search using response surface models (DYCORS) (Regis and Shoemaker 2013) and the related parallel algorithms parallel optimization with dynamic coordinate search using surrogates (PODS) (Xia et al. 2021) and global optimization in parallel with surrogate (GOPS) (Xia and Shoemaker 2021). Moreover, ideas from the stochastic RBF method (Regis and Shoemaker 2007) were also implemented in the surrogate optimization-mixed integer (SO-MI) algorithm for mixed-integer black-box optimization (Müller et al. 2013), two-phase constrained discrete optimization using response surfaces (CONDOR) for high-dimensional constrained discrete black-box optimization (Regis 2021), the reference vector-assisted candidate search with aggregated surrogate model (RECAS) for many-objective optimization (Wang and Shoemaker 2023), and directional optimization search with surrogate (DOSS) (Liu et al. 2024a).

ConstrLMSRBF (Regis 2011), DYCORS local metric stochastic RBF (Regis and Shoemaker 2013), and DOSS (Liu et al. 2024a) share some similarities with the local MSRBF algorithm, including using normally distributed perturbations to generate candidate trial points and using a weighted combination of a response surface criterion and a distance criterion to select its function evaluation points. However, these algorithms modified only a subset of the coordinates of the current best solution when generating trial candidate points for function evaluation. This idea was incorporated from the dynamically dimensioned search algorithm (Tolson and Shoemaker 2007), which does not use surrogates but which has been shown to be effective for high-dimensional optimization problems that do not have expensive objective functions. Also, ConstrLMSRBF was designed for problems with black-box inequality constraints, and it utilized multiple surrogates, one for the objective function and one for each of the inequality constraint functions. When they were introduced, ConstrLMSRBF and DYCORS were among a few surrogate-based approaches in the literature that successfully handled high-dimensional problems with hundreds of decision variables given a very limited computational budget. Notably, ConstrLMSRBF (Regis 2011) was one of the first methods to produce high-quality solutions to a benchmark automotive engineering optimization problem involving 124 decision variables and 68 black-box inequality constraints using only a relatively small number of function evaluations. Additionally, the GOPS, DYCORS, and DOSS algorithms were also proven to converge to the global optimum in a probabilistic sense (Xia and Shoemaker 2021, Liu et al. 2024a).

The stochastic RBF method (Regis and Shoemaker 2007) and its extensions have also been used to solve various optimization problems in environmental and renewable energy applications, including the calibration of groundwater bioremediation models (Mugunthan et al. 2005) and watershed models (Regis and Shoemaker 2013), coastal aquifer management (Christelis et al. 2018), optimization of photovoltaic and energy storage system configuration (Liu et al. 2023), and identification of cost-effective green infrastructure for urban flood control (Lu et al. 2022). Other applications include transportation network design (Chow et al. 2010), automotive design optimization (Regis 2011), airfoil design (Palar et al. 2019), hyperparameter optimization of deep learning algorithms (Ilievski et al. 2017), the tuning of spiking neural models of striatum plasticity (Cruz et al. 2022), parameter estimation for an infectious disease agent-based model (Perumal and van Zyl 2025), and protein structure prediction (Rakhshani et al. 2018). Prof. Shoemaker won the Hotelling Medal from INFORMS for her development and application of optimization algorithms, including the stochastic RBF method, to environmental problems.

A MATLAB code for the multistart local metric stochastic RBF algorithm is available in a GitHub repository maintained by the INFORMS Journal on Computing (https://github.com/INFORMSJoC/1060.0182), and we invite researchers and practitioners to apply it to their computationally expensive optimization problems. Moreover, the Python Surrogate Optimization Toolbox (pySOT) (Eriksson et al. 2019) for computationally expensive black-box objective functions implements several surrogate optimization algorithms, including stochastic RBF (Regis and Shoemaker 2007) and DYCORS (Regis and Shoemaker 2013), and it allows the user to run the algorithms in serial, synchronous parallel, or asynchronous parallel. This toolbox has over 330,000 downloads from GitHub (https://github.com/dme65/pySOT). The pySOT toolbox was developed in an NSF CISE project led by Profs. Shoemaker and Bindel, with coding by Bindel and Eriksson. Additionally, some of the ideas from the stochastic RBF method, such as using a weighted combination of a surrogate criterion and a distance criterion to select the next sample point, were implemented in the surrogateopt solver that has been available in the MATLAB Global Optimization Toolbox since 2018.

We again thank the award committee and the journal for their support. With its continued success in solving practical engineering optimization problems and the availability of accessible implementations, the stochastic RBF method and its extensions will hopefully also be widely used in the future.