qEI_with_grad: Computes the Multipoint Expected Improvement (qEI) Criterion

In libKriging/dolka: Utility functions for Bayesian optimization

Computes the Multipoint Expected Improvement (qEI) Criterion

Description

Analytical expression of the multipoint expected improvement criterion, also known as the q-point expected improvement and denoted by q-EI or qEI.

Usage

qEI_with_grad(
  x,
  model,
  plugin = NULL,
  type = c("UK", "SK"),
  minimization = TRUE,
  fastCompute = TRUE,
  eps = 1e-05,
  deriv = TRUE,
  out_list = TRUE,
  trace = 0
)

Arguments

x	A numeric matrix representing the set of input points (one row corresponds to one point) where to evaluate the qEI criterion.
model	An object of class km.
plugin	Optional scalar: if provided, it replaces the minimum of the current observations.
type	"SK" or "UK" (by default), depending whether uncertainty related to trend estimation has to be taken into account.
minimization	Logical specifying if EI is used in minimiziation or in maximization.
fastCompute	Logical. If TRUE, a fast approximation method based on a semi-analytic formula is used. See the reference Marmin (2014) for details.
eps	Numeric value of epsilon in the fast computation trick. Relevant only if fastComputation is TRUE.
deriv	Logical. When TRUE the dervivatives of the kriging mean vector and of the kriging covariance (Jacobian arrays) are computed and stored in the environment given in envir.
out_list	Logical. Logical When out_list is TRUE the result is a list with one element objective. If deriv is TRUE the list has a second element gradient. When out_list is FALSE the result is the numerical value of the objective, possibly having an attribute named "gradient".
trace	Integer level of verbosity.

Value

The multipoint Expected Improvement, defined as

qEI(Xnew) := E[{ min Y(X) - min Y(Xnew) }_{+} \vert Y(X) = y(X)],

where X is the current design of experiments, Xnew is a new candidate design, and Y is a random process assumed to have generated the objective function y.

Author(s)

Sebastien Marmin, Clement Chevalier and David Ginsbourger.

References

C. Chevalier and D. Ginsbourger (2014) Learning and Intelligent Optimization - 7th International Conference, Lion 7, Catania, Italy, January 7-11, 2013, Revised Selected Papers, chapter Fast computation of the multipoint Expected Improvement with applications in batch selection, pages 59-69, Springer.

D. Ginsbourger, R. Le Riche, L. Carraro (2007), A Multipoint Criterion for Deterministic Parallel Global Optimization based on Kriging. The International Conference on Non Convex Programming, 2007.

S. Marmin (2014). Developpements pour l'evaluation et la maximisation du critere d'amelioration esperee multipoint en optimisation globale. Master's thesis, Mines Saint-Etienne (France) and University of Bern (Switzerland).

D. Ginsbourger, R. Le Riche, and L. Carraro. Kriging is well-suited to parallelize optimization (2010), In Lim Meng Hiot, Yew Soon Ong, Yoel Tenne, and Chi-Keong Goh, editors, Computational Intelligence in Expensive Optimization Problems, Adaptation Learning and Optimization, pages 131-162. Springer Berlin Heidelberg.

J. Mockus (1988), Bayesian Approach to Global Optimization. Kluwer academic publishers.

M. Schonlau (1997), Computer experiments and global optimization, Ph.D. thesis, University of Waterloo.

See Also

EI

Examples

set.seed(7)
## Monte-Carlo validation

## a 4-d, 81-points grid design, and the corresponding response
## ============================================================
d <- 4; n <- 3^d
design <- expand.grid(rep(list(seq(0, 1, length = 3)), d))
names(design) <- paste0("x", 1:d)
y <- apply(design, 1, hartman4)

## learning
## ========
model <- km(~1, design = design, response = y, control = list(trace = FALSE))

## pick up 10 points sampled from the 1-point expected improvement
## ===============================================================
q <- 10
X <- sampleFromEI(model, n = q)

## simulation of the minimum of the kriging random vector at X
## ===========================================================
t1 <- proc.time()
newdata <- as.data.frame(X)
colnames(newdata) <- colnames(model@X)

krig  <- predict(object = model, newdata = newdata, type = "UK",
                 se.compute = TRUE, cov.compute = TRUE)
mk <- krig$mean
Sigma.q <- krig$cov
mychol <- chol(Sigma.q)
nsim <- 300000
white.noise <- rnorm(n = nsim * q)
minYsim <- apply(crossprod(mychol, matrix(white.noise, nrow = q)) + mk,
                 MARGIN = 2, FUN = min)

## simulation of the improvement (minimization)
## ============================================
qImprovement <- min(model@y) - minYsim
qImprovement <- qImprovement * (qImprovement > 0)

## empirical expectation of the improvement and confidence interval (95%)
## ======================================================================
EIMC <- mean(qImprovement)
seq <- sd(qImprovement) / sqrt(nsim)
confInterv <- c(EIMC - 1.96 * seq, EIMC + 1.96 * seq)

## evaluate time
## =============
tMC <- proc.time() - t1

## MC estimation of the qEI
## ========================
print(EIMC) 

## qEI with analytical formula and with fast computation trick
## ===========================================================
tForm <- system.time(qEI(X, model, fastCompute = FALSE))
tFast <- system.time(qEI(X, model))

rbind("MC" = tMC, "form" = tForm, "fast" = tFast)

libKriging/dolka documentation built on April 14, 2022, 7:17 a.m.