Stochastic radial basis function algorithms for large-scale optimization involving expensive black-box objective and constraint functions

Abstract

This paper presents a new algorithm for derivative-free optimization of expensive black-box objective functions subject to expensive black-box inequality constraints. The proposed algorithm, called ConstrLMSRBF, uses radial basis function (RBF) surrogate models and is an extension of the Local Metric Stochastic RBF (LMSRBF) algorithm by Regis and Shoemaker (2007a) [1] that can handle black-box inequality constraints. Previous algorithms for the optimization of expensive functions using surrogate models have mostly dealt with bound constrained problems where only the objective function is expensive, and so, the surrogate models are used to approximate the objective function only. In contrast, ConstrLMSRBF builds RBF surrogate models for the objective function and also for all the constraint functions in each iteration, and uses these RBF models to guide the selection of the next point where the objective and constraint functions will be evaluated. Computational results indicate that ConstrLMSRBF is better than alternative methods on 9 out of 14 test problems and on the MOPTA08 problem from the automotive industry (Jones, 2008 [2]). The MOPTA08 problem has 124 decision variables and 68 inequality constraints and is considered a large-scale problem in the area of expensive black-box optimization. The alternative methods include a Mesh Adaptive Direct Search (MADS) algorithm (Abramson and Audet, 2006 [3]; Audet and Dennis, 2006 [4]) that uses a kriging-based surrogate model, the Multistart LMSRBF algorithm by Regis and Shoemaker (2007a) [1] modified to handle black-box constraints via a penalty approach, a genetic algorithm, a pattern search algorithm, a sequential quadratic programming algorithm, and COBYLA (Powell, 1994 [5]), which is a derivative-free trust-region algorithm. Based on the results of this study, the results in Jones (2008) [2] and other approaches presented at the ISMP 2009 conference, ConstrLMSRBF appears to be among the best, if not the best, known algorithm for the MOPTA08 problem in the sense of providing the most improvement from an initial feasible solution within a very limited number of objective and constraint function evaluations.

Introduction

In many engineering optimization problems, the objective and constraint functions are black-box functions that are outcomes of computationally expensive computer simulations and the derivatives of these functions are usually not available. This paper presents a new method for derivative-free optimization of expensive black-box objective functions subject to expensive black-box inequality constraints. The proposed method uses multiple radial basis function (RBF) surrogate models to approximate the expensive objective and constraint functions and uses these models to identify a promising point for function evaluation in each iteration. The method can be used for constrained optimization problems that are considered large-scale (in terms of number of decision variables and constraints) in the general area of surrogate model-based expensive black-box optimization and it is designed to obtain good solutions after only a relatively small number of objective and constraint function evaluations. Computational results demonstrate the effectiveness of this method on a large-scale optimization problem from the automotive industry involving 124 decision variables and 68 inequality constraints, and on a collection of 14 constrained optimization test problems, four of which are engineering design problems.

Our focus is to solve an optimization problem of the following form:

$$\min f(x)\text{s.t.}x\in {\mathbb{R}}^d,a\le x\le b{g}_i(x)\le 0,i=1,2,\dots ,m$$

where f, g₁, …, g_m are deterministic black-box functions that are computationally expensive and $a,b\in {\mathbb{R}}^d$. Future work will address the case where there is noise in the objective and constraint functions and also when there are explicit linear inequality or equality constraints. We assume that the derivatives of f, g₁, …, g_m are unavailable, which is the case in many practical applications. Define the vector-valued function g(x)=(g₁(x),…,g_m(x)) and let $\mathcal{D}≔\{x\in {\mathbb{R}}^d:g(x)\le 0,a\le x\le b\}$ be the search space of the above optimization problem. Furthermore, we assume that f, g₁, …, g_m are all continuous on [a,b] so that $\mathcal{D}$ is a compact subset of ${\mathbb{R}}^d$ and f is guaranteed to have a global minimum point over $\mathcal{D}$. We also assume that the values of f and g=(g₁, …, g_m) for a given $x\in [a,b]$ can be obtained from computer simulations and that the simulator will not crash for any input $x\in [a,b]$. Future work will also address the case when the simulator crashes for some $x\in [a,b]$.

Ideally, we would like to obtain a global minimum point for f over $\mathcal{D}$ using only a relatively small number of objective and constraint function evaluations. However, it usually takes a large number of function evaluations to guarantee that the solution obtained is even approximately optimal on low-dimensional bound constrained problems. For high-dimensional problems, finding the global minimum within a reasonable number of function evaluations is almost impossible (and hence not realistic) for general black-box problems with black-box constraints. Hence, most practitioners are typically concerned with obtaining a reasonably good feasible solution given a severe computational budget on the number of function evaluations. Although real-world optimization problems typically involve multiple local minima, the proposed algorithm focuses more on finding good local solutions from a given feasible starting point. Future work will consider infeasible starting points and more global approaches, including a multistart approach for expensive nonlinearly constrained problems that can be effectively combined with this local search method. However, in theory, the proposed method can find the global minimum of the above optimization problem if it is allowed to run indefinitely using a convergence argument similar to that used in Regis and Shoemaker [1]. Moreover, previous experience with the LMSRBF algorithm [1] indicates that the proposed method can deal with rugged landscapes similar to those found in groundwater bioremediation problems.

When the objective function f(x) and the constraint functions g₁(x),…,g_m(x) are smooth and f(x) is not riddled with local minima, then the traditional optimization approach is to use a gradient-based local minimization algorithm. In addition, if a global minimum is desired, then this local minimization algorithm can be used in conjunction with a multistart approach for constrained optimization such as OQNLP [6] or the Tabu Tunneling or Tabu Cutting Method [7]. However, in many practical applications, the derivatives of the objective and constraint functions are not explicitly available so they would have to be obtained by automatic differentiation or finite-differencing. Unfortunately, automatic differentiation does not always produce accurate derivatives and it cannot be used when the complete source codes for the objective and constraint functions are not available. Moreover, finite-differencing may be unreliable when the objective function or the constraint functions are nonsmooth. Hence, many practitioners rely on derivative-free optimization methods (or direct search methods) [8], [9] such as pattern search [10], Mesh Adaptive Direct Search (MADS) [3], [4] and derivative-free trust-region methods [11], [9], [12], [13], [14]. Furthermore, derivative-free heuristic methods such as simulated annealing, evolutionary algorithms (e.g., genetic algorithms, evolution strategies and evolutionary programming), differential evolution [15], [16], and scatter search [17], [18], [19], [20] are also used to solve constrained optimization problems.

When the objective and constraint functions are computationally expensive black-box functions, a suitable optimization approach is to use response surface models (also known as surrogate models or metamodels) for these expensive functions. Here, the term response surface model is used in a broad sense to mean any function approximation model such as polynomials, which are used in traditional response surface methodology [21], radial basis functions (RBF) [22], [23], kriging [24], [25], regression splines, neural networks and support vector machines. Note that the RBF model described in Powell [23] is equivalent to a form of kriging called dual kriging (see Cressie [25]).

The use of response surface models for expensive black-box optimization has become widespread within the last decade. For example, polynomial and kriging response surface models have been used to solve aerospace design problems [26], [27]. Kriging interpolation was used by Jones et al. [28] to develop the EGO method, which is a global optimization method where the next iterate is obtained by maximizing an expected improvement function. A variant of the EGO method was used by Aleman et al. [29] to optimize beam orientation in intensity modulated radiation therapy (IMRT) treatment planning. Villemonteix et al. [30] also used kriging to develop the IAGO method, which uses minimizer entropy as a criterion for determining new evaluation points. RBF interpolation was used by Gutmann [31] to develop a global optimization method where the next iterate is obtained by minimizing a bumpiness function. Variants of this RBF method were developed by Björkman and Holmström [32] and by Regis and Shoemaker [33]. Kriging was used in conjunction with pattern search to solve a helicopter rotor blade design problem [34] and an aeroacoustic shape design problem [35]. Egea et al. [36] also used kriging to improve the performance of scatter search on computationally expensive problems. Finally, derivative-free trust-region methods for unconstrained optimization (e.g., Conn et al. [11], Powell [5], [12], [13], Wild et al. [14]) use local interpolation models of the objective function using a subset of previously evaluated points.

Most of the surrogate model-based optimization methods mentioned above can only be used for bound constrained problems where only the objective function is expensive. Relatively few surrogate model-based approaches have been developed for optimization problems involving nonlinear constraints. For example, the CORS method by Regis and Shoemaker [37] can be used for problems involving inexpensive and explicitly defined nonlinear constraints. The Adaptive Radial Basis algorithm (ARBF) by Holmström et al. [38] can handle nonlinear constraints that are either inexpensive or are incorporated into the objective function via penalty terms. ASAGA (Adaptive Surrogate-Assisted Genetic Algorithm) [39] also handles constraints via a penalty and uses a surrogate model to approximate the fitness function for a genetic algorithm. For optimization problems involving an expensive objective function and expensive black-box inequality constraints, there are even fewer surrogate model-based methods that do not use penalty terms to handle the black-box constraints. For example, the NOMADm software by Abramson [40] implements the MADS algorithm [3], [4] for constrained optimization and it has the option of using a kriging surrogate model to improve the performance of MADS on computationally expensive problems. COBYLA [5] is a derivative-free trust region method for constrained optimization that uses linear interpolation models of the objective and constraint functions. Kleijnen et al. [41] recently developed a method for constrained nonlinear stochastic optimization that uses kriging models of the stochastic black-box objective and constraint functions but the decision variables are required to be nonnegative integers. The proposed method also handles the expensive black-box inequality constraints by using RBF models of the constraint functions.

The main contribution of this paper is a new RBF algorithm called Constrained Local Metric Stochastic RBF (ConstrLMSRBF), which is an extension of the Local Metric Stochastic RBF (LMSRBF) algorithm by Regis and Shoemaker [1]. The original LMSRBF algorithm was designed for bound constrained optimization problems with an expensive black-box objective function. ConstrLMSRBF is designed to handle black-box inequality constraints by using multiple RBF models to approximate the objective and constraint functions and identify promising evaluation points for subsequent iterations. Previous papers on expensive black-box optimization using response surface models have mostly dealt with bound constrained problems where only the objective function is black-box and expensive (e.g., Jones et al. [28], Björkman and Holmström [32], Gutmann [31], Regis and Shoemaker [42], [37], [1], [33], Egea et al. [36]). To the best of my knowledge, this is one of the few surrogate model-based optimization methods at present that treats each inequality constraint individually instead of lumping all of them into one penalty function.

This study involves a comparison of seven very different methods for constrained optimization (including the proposed ConstrLMSRBF algorithm) on 14 test problems (four of which are engineering design problems) where the number of decision variables ranges from 2 to 20 and the number of inequality constraints ranges from 1 to 11. ConstrLMSRBF is compared to six alternative methods: (1) NOMADm-DACE, which is a Mesh Adaptive Direct Search (MADS) algorithm [3], [4] that uses a DACE surrogate model [43]; (2) MLMSRBF-Penalty, which is the Multistart LMSRBF algorithm by Regis and Shoemaker [1] that has been modified to handle black-box constraints via a penalty approach; (3) a sequential quadratic programming (SQP) algorithm where the derivatives are obtained by finite differencing; (4) a pattern search algorithm [10]; (5) a genetic algorithm; and (6) the derivative-free trust-region algorithm COBYLA [5]. The computational results indicate that ConstrLMSRBF is generally better than these alternative methods on 9 of the 14 test problems, including three of the engineering design problems.

In addition, the computational results show that ConstrLMSRBF is also a very promising method for problems that are relatively high dimensional in the area of expensive black-box optimization. Previous papers on expensive black-box optimization using response surface models have also mostly dealt with low dimensional problems, usually less than 15 dimensions (e.g., Jones et al. [28], Björkman and Holmström [32], Gutmann [31], Regis and Shoemaker [42], [37], [1], [33], Aleman et al. [29], Egea et al. [36], Villemonteix et al. [30]). For high dimensional problems (involving more than 100 decision variables), the computational overhead involved in determining a promising function evaluation point in each iteration for some surrogate model-based global optimization algorithms such as the RBF method by Gutmann [31] and the CORS-RBF method by Regis and Shoemaker [37] could rival the cost of an objective or constraint function evaluation so it is not easy to develop a reasonably good algorithm for such problems. This paper shows very promising results for ConstrLMSRBF on the MOPTA08 benchmark problem from the automotive industry developed by Jones [2]. The MOPTA08 problem is an optimization problem that has 124 decision variables and 68 inequality constraints and is considered large-scale in the area of expensive black-box optimization. This problem is important because it has vastly more decision variables and constraints than other test problems used in surrogate model-based optimization.

To the best of my knowledge and based on other approaches mentioned by Jones [2] and the two other approaches presented at the ISMP 2009 conference (i.e., Forrester and Jones [44], Quttineh and Holmström [45]), ConstrLMSRBF is among the best, if not the best, known method for the MOPTA08 problem in the sense of providing the most improvement from an initial feasible solution within a very limited number of objective and constraint function evaluations [46]. From the results for the MOPTA08 problem in this study, ConstrLMSRBF and its variants outperformed NOMADm-DACE, MLMSRBF-Penalty, a Fortran 90 implementation of COBYLA and three optimization solvers in Matlab, namely, Fmincon, pattern search and genetic algorithm. Based on results for the MOPTA08 problem presented by Jones [2], ConstrLMSRBF is also better than Generalized Reduced Gradient (using iSIGHT-FD), SQP (Harwell routine VF13), an evolution strategy, a local search algorithm with search directions from local surface approximations (LS-OPT), and also the original Fortran 77 implementation of COBYLA due to Powell [5].

In summary, the proposed ConstrLMSRBF algorithm represents substantial progress in the area of expensive black-box optimization. Computational results show that this is a very promising method compared to alternative methods for expensive black-box optimization. It deals with some important issues that were not previously addressed by similar algorithms, namely, how to deal with nonlinear black-box inequality constraints and how to deal with problems involving a large number of decision variables and constraints.