Module ego 

Efficient global optimization (EGO): minimizing a model that is slow to evaluate in few evaluations, by fitting a surrogate to the points evaluated so far and evaluating next where the surrogate expects the most improvement.

The method is D. R. Jones, M. Schonlau and W. J. Welch, “Efficient global optimization of expensive black-box functions”, Journal of Global Optimization 13, 455–492 (1998), https://doi.org/10.1023/A:1008306431147:

1. Evaluate the model at an initial design that spreads over the variables’ box: a Latin hypercube (each variable’s range cut into n equal slices, one point in each), the most spread out (largest least distance between two points) of DESIGNS drawn. Its size is 10 points per variable by default, the rule of J. L. Loeppky, J. Sacks and W. J. Welch, “Choosing the sample size of a computer experiment: a practical guide”, Technometrics 51(4), 366–376 (2009), https://doi.org/10.1198/TECH.2009.08040.

2. Fit a kriging surrogate (a Gaussian process): the model’s values are taken as a constant mean μ plus a correlated deviation of variance σ², the correlation of two points x, x' being exp(−Σₖ θₖ (xₖ − x'ₖ)²) with the variables scaled to [0, 1] (Jones et al. eq. (1) with pₖ = 2, as they use on their test functions). μ, σ² and each θₖ are those of most likelihood (eq. (4)): μ and σ² in closed form (eqs. (5), (6)), the θₖ by cmaes over log₁₀ θₖ in [−3, 3].

3. The surrogate predicts the model at a point, ŷ, with a standard error s (eqs. (7), (9)), zero at an evaluated point and growing away from them. The expected improvement over the best value so far f_min is (eq. (15))

   E[I] = (f_min − ŷ) Φ((f_min − ŷ)/s) + s φ((f_min − ŷ)/s),

   Φ and φ the standard normal distribution and density. It is large where ŷ is low (exploiting what is known) and where s is large (exploring what isn’t).

4. Evaluate the model where the expected improvement is largest, found by CMA-ES started from the best of SEARCH_POINTS random points per variable and from the best point so far, refit, and repeat until the budget is spent, the target is met, or the largest expected improvement falls below a tolerance. Jones et al. maximize it exactly, by branch and bound; a multistart search, as here, may miss the largest.

Departures from the paper: the search of step 4; no diagnostic tests of the surrogate; and a value of +∞, a failed evaluation, which is fitted as the largest finite value so far. Where the surrogate can’t be fitted (every value equal, say), the next point is drawn uniformly from the box instead.

Transforming the values

Where the surrogate fits the values badly, Jones et al. fit it to a transformation of them instead: “we typically try the log transformation, ln(y), or the inverse transformation, −1/y” (§3, p. 468), and the transformed function is used “in the rest of the analysis” (§4.2, p. 473): the surrogate, its prediction and the expected improvement are all on the transformed scale. On their test functions the diagnostic tests chose ln y for Goldstein–Price’s function and −ln(−y) for Hartmann’s six-variable function (§4.2, p. 474). Transform offers the two log transformations, chosen by the caller (Ego::with_transform); hpr runs no diagnostic test to choose one. Both increase with y, so the least transformed value is at the least value, and the best point, the target and the result are on the model’s own scale. A value outside the transformation’s domain (y ≤ 0 for ln y, y ≥ 0 for −ln(−y)) is an error, not something to fit.

The values are standardized (their mean taken off, divided by their standard deviation) before fitting, which changes neither the predictions nor where the improvement is largest. The correlation matrix gets NUGGET added to its diagonal so its Cholesky factorization stays defined as points crowd together near a minimum.

Reproducibility

A run’s random numbers (the designs, the search’s points, and each CMA-ES run’s seed) come from streams keyed by the seed and the evaluation’s number (SeededRng::for_stream), so a run is bit for bit the same every time on one platform.

Structs

Ego

The optimizer’s settings: the variables, the initial design’s size, and when to stop. It serializes as its fields, and reads back through the same checks as Ego::new and its with_ methods.

Optimum

What a run found.

Enums

Stop

Why a run stopped.

Transform

A transformation of the model’s values that the surrogate is fitted to (Jones et al. 1998, §3, p. 468 and §4.2, pp. 473–474; see the module’s page).

Constants

DESIGNS

How many Latin hypercube designs are drawn for the initial design; the most spread out is kept.

MAX_EGO_VARIABLES

The most variables EGO takes: 10 points each for the initial design stay within MAX_POINTS. It is checked on two, three and six.

MAX_POINTS

The most points a run may evaluate, the initial design’s included: a fit factorizes an m × m matrix, O(m³) work, a hundred times per variable per step.

NUGGET

Added to the correlation matrix’s diagonal, in units of σ²: about the square of 10⁻⁴, the smallest relative scatter the surrogate is allowed to see between two values.

SEARCH_POINTS

How many random points per variable the search for the largest expected improvement starts from.