1 Introduction

Surrogate use for constrained optimization and design under uncertainty has become popular (Basudhar and Missoum 2010; Ranjan et al. 2008; Kuczera et al. 2010; Valdebenito and Schuëller 2010; Picheny et al. 2010; Lee et al. 2011; Dubourg et al. 2011). Surrogates fitted to constraints must be most accurate near the contour demarcating the boundary of the feasible domain (limit state). Thus, algorithms that prefentially sample near the limit state have been developed—e.g., the efficient global reliability analysis (EGRA) algorithm (Bichon et al. 2008). These algorithms add one point at a time, not taking advantage of parallel computing for concurrent constraint evaluations.

We propose two strategies for parallelizing the sampling, both based on the efficient global optimization (EGO) algorithm (Jones et al. 1998). The first is to fit multiple surrogates to the data (Viana et al. 2010), each contributing one sample point. The second is based on the “kriging believer” approach (Ginsbourger et al. 2010), where after selecting a new sample, kriging is updated using the estimated value as if it were data.

2 Sequential sampling for contour estimation with the Efficient Global Reliability Analysis (EGRA) algorithm

Given the scalar constraint \(g(\mathbf{x}) \le \bar{g}\) defining the limit state \(\bar{g}\), EGRA (Bichon et al. 2008) defines the feasibilityFootnote 1 at x as

$$ F(\mathbf{x}) = \max \bigl(\epsilon(\mathbf{x}) - |\bar g - G(\mathbf{x})|, 0 \bigr), $$
(1)

where G(x) is the random variable representing the unknown g(x), and ϵ(x) measures the uncertainty in G(x).

F(x) is nonzero in a band near the limit state and maximal where the uncertainty ϵ(x) is largest. If G(x) is modeled by a kriging surrogate (Gaussian process), then the expectation of F(x) is easy to calculateFootnote 2 as

$$ \begin{array}{rll} E_G[F(\mathbf{x})] &=& ({\hat{g}}(\mathbf{x}) - \bar{g}) \left[2 \Phi(u) - \Phi(u^{+}) - \Phi(u^{-}) \right] \\ && - s(\mathbf{x}) \left[2 \phi(u) - \phi(u^{+}) - \phi(u^{-}) \right] \\ && + \epsilon \left[\Phi(u^{+}) - \Phi(u^{-}) \right] \text{ ,} \end{array} $$
(2)

where Φ and ϕ are the standard Gaussian CDF and PDF, respectively, \(\displaystyle u = \frac{\bar{g} - {\hat{g}}(\mathbf{x})}{s(\mathbf{x})}\), \(\displaystyle u^{+} = \frac{\bar{g} + \epsilon - {\hat{g}}(\mathbf{x})}{s(\mathbf{x})}\), \(\displaystyle u^{+} = \frac{\bar{g} - \epsilon - {\hat{g}}(\mathbf{x})}{s(\mathbf{x})}\), \({\hat{g}}(\mathbf{x})\) is the kriging prediction, s(x) is the square root of the kriging prediction variance, and ϵ = αs(x) (Bichon et al. 2008 suggested α = 2).

The efficient global reliability analysis (EGRA) algorithm sequentially adds points to the data set in an effort to improve the surrogate accuracy near the limit state. As an adaptive sampling strategy, EGRA involves solving the optimization problem of finding the best point to be sampled. In each cycle, the next point to be sampled is the one that maximizesFootnote 3 E G [F(x)]. Kriging is updated after adding the new point to the existing data set. EGRA iterates until a convergence criterion is met (e.g., computational budget or E G [F(x)] history).

3 Strategies for multiple point EGRA

The first strategy we propose to provide multiple points per cycle is the multiple surrogate efficient global reliability analysis (MSEGRA) algorithm. MSEGRA is inspired by the multiple surrogate efficient global optimization algorithm (Viana et al. 2010) and uses n surrogates to provide up to n points per cycle. In each cycle, we maximize E G [F(x)] of each surrogate. MSEGRA could use different instances of kriging (with different correlation functions). However, we illustrate the algorithm with surrogates based on different techniques (radial basis function, linear Shepard, and support vector regression).Footnote 4

The second strategy uses the kriging believer heuristic (Ginsbourger et al. 2010). In each cycle, n points are created by sequentially maximizing E G [F(x)] (n times). When a point is obtained, via maximization of E G [F(x)], the kriging prediction is “believed” (taken as new data) and kriging is updated. In other words, the kriging believer replaces the actual response at the chosen sites by the kriging prediction. In practice, this makes the kriging uncertainty vanish at that point—and thus also E G [F(x)]. At the end of the cycle, actual simulations are conducted at the n new points (which are added to the data set). Kriging is then updated with the augmented data set.

While kriging believer find samples in sequence, in MSEGRA they can be found in parallel. Therefore, when search for samples (and surrogate updates) dominates the cost of function evaluations, MSEGRA may have some gains of parallelization. When using multiple surrogates, selection is done after sampling is finished (e.g., using cross-validation (Viana et al. 2009)).

4 Numerical experiments

As test problem, we used the Branin-Hoo function (Dixon and Szegö 1978)

$$ \begin{array}{rll} g(\mathbf{x}) &=& \left( x_2 - \frac{5.1x_1^2}{4\pi^2} + \frac{5x_1}{\pi} - 6 \right)^2 \\ &&+ 10\left( 1- \frac{1}{8\pi} \right)\cos(x_1) + 10 \le 50 , \\ &&-5 \le x_1 \le 10 \text{ , and } 0\le x_2 \le 15 . \end{array} $$
(3)

The surrogates of Table 1 are initially fitted with ten points. To average out the influence of the initial data, we repeat the experiments with 100 different Latin hypercube designs created with the MATLAB® function lhsdesign (Mathworks contributors 2004) (set with “maxmin” and 1,000 iterations).

Table 1 Setup for the surrogates used
Full size table

We run EGRA, MSEGRA and EGRA-believer for 20 cycles (details in Table 2) tracking the performance with test points and the misclassification fraction (Basudhar and Missoum 2010)

$$ m_f = \frac{\sum_i{I(g(\mathbf{x}_i) \leq \bar{g}) \oplus I({\hat{g}(\mathbf{x}_i)} \leq \bar{g}) }}{p_{\rm test}} \text{ ,} $$
(4)

where I(.) is the indicator function, ⊕ represents the exclusive disjunction (which is 1 if only one of the operands is true and 0 otherwise), and p test = 10,000 (created with the lhsdesign set with “maxmin” and 50 iterations). m f indicates the fraction of the design space the surrogate misclassifies as either feasible or infeasible.

Table 2 Setup for the sequential sampling
Full size table

5 Results and discussion

We illustrate the EGRA using a single data set. Figure 1a shows kriging fitted to ten points (misclassification fraction m f  = 0.1). Figure 1b illustrates results after 20 cycles. The misclassification fraction is reduced to m f  = 0.01. Figure 1c shows changes in misclassification fraction as points are added one at a time.

Fig. 1
figure 1

EGRA for a single experimental design. Points added after 20 EGRA cycles reduce misclassification (4)

Full size image

Figure 2 shows the median of m f with 100 experimental designs for the three EGRA variants. Figure 2a shows that while MSEGRA and EGRA-believer have approximately m f  = 0.007 by the third cycle, EGRA only achieves that mark by the 12th cycle. If function evaluations can be done in parallel (concurrently), MSEGRA and EGRA-believer save about ten cycles (many days for some applications).

Fig. 2
figure 2

Median (over 100 experimental designs) of misclassification fraction (4) for EGRA variants of Table 2. Five points per cycle improve performance without a severe penalty in terms of number of function evaluations

Full size image

Using multiple function evaluations per cycle is attractive when the main concern is the number of cycles, rather than number of simulations. However, one would expect a cost associated with the number function evaluations. Figure 2b shows the median of misclassification fraction versus the number of function evaluations for all three algorithms. For this problem, the penalty in increased number of evaluations is small.

6 Summary and conclusions

We proposed two approaches for contour estimation with concurrent function evaluations. The multiple surrogate efficient global reliability analysis (MSEGRA) algorithm uses a set of surrogates. EGRA-believer runs the kriging believer heuristic. We demonstrated the two approaches for an algebraic example and surrogates including kriging, radial basis function, linear Shepard and support vector regression. We found that

  1. 1.

    MSEGRA and EGRA-believer reduced substantially the number of cycles required for convergence, and

  2. 2.

    the penalty in terms of total number of function evaluations was less than a factor of two.

Results for the demonstration example need to be augmented with other problems to provide a more solid estimate of the savings associated with the procedure. In particular, the optimal number of simultaneous evaluations needs to be studied as function of the cost of function evaluations and the benefit of short wall times. The multiple surrogate version also allows one to select a single surrogate after the sampling is concluded based on accuracy measures, such as cross validation errors.