Crate egobox_ego

This library implements Efficient Global Optimization method, it started as a port of the EGO algorithm implemented as an application example in SMT.

The optimizer is able to deal with inequality constraints. Objective and contraints are expected to computed grouped at the same time hence the given function should return a vector where the first component is the objective value and the remaining ones constraints values intended to be negative in the end.
The optimizer comes with a set of options to:

• specify the initial doe,
• parameterize internal optimization,
• parameterize mixture of experts,
• save intermediate results and allow hot restart,

Examples

Continuous optimization

use ndarray::{array, Array2, ArrayView2};
use egobox_ego::EgorBuilder;

// A one-dimensional test function, x in [0., 25.] and min xsinx(x) ~ -15.1 at x ~ 18.9
fn xsinx(x: &ArrayView2<f64>) -> Array2<f64> {
    (x - 3.5) * ((x - 3.5) / std::f64::consts::PI).mapv(|v| v.sin())
}

// We ask for 10 evaluations of the objective function to get the result
let res = EgorBuilder::optimize(xsinx)
            .configure(|config| config.max_iters(10))
            .min_within(&array![[0.0, 25.0]])
            .run()
            .expect("xsinx minimized");
println!("Minimum found f(x) = {:?} at x = {:?}", res.x_opt, res.y_opt);

The implementation relies on Mixture of Experts.

Mixed-integer optmization

While Egor optimizer works with continuous data (i.e floats), the optimizer allows to make basic mixed-integer optimization. The configuration of the Optimizer as a mixed_integer optimizer is done though the EgorBuilder

As a second example, we define an objective function mixsinx taking integer input values from the previous function xsinx defined above.

use ndarray::{array, Array2, ArrayView2};
use linfa::ParamGuard;
#[cfg(feature = "blas")]
use ndarray_linalg::Norm;
#[cfg(not(feature = "blas"))]
use linfa_linalg::norm::*;
use egobox_ego::{EgorBuilder, InfillStrategy, XType};

fn mixsinx(x: &ArrayView2<f64>) -> Array2<f64> {
    if (x.mapv(|v| v.round()).norm_l2() - x.norm_l2()).abs() < 1e-6 {
        (x - 3.5) * ((x - 3.5) / std::f64::consts::PI).mapv(|v| v.sin())
    } else {
        panic!("Error: mixsinx works only on integer, got {:?}", x)
    }
}

let max_iters = 10;
let doe = array![[0.], [7.], [25.]];   // the initial doe

// We define input as being integer
let xtypes = vec![XType::Int(0, 25)];

let res = EgorBuilder::optimize(mixsinx)
    .configure(|config|
        config.doe(&doe)  // we pass the initial doe
              .max_iters(max_iters)
              .infill_strategy(InfillStrategy::EI)
              .random_seed(42))     
    .min_within_mixint_space(&xtypes)  // We build a mixed-integer optimizer
    .run()
    .expect("Egor minimization");
println!("min f(x)={} at x={}", res.y_opt, res.x_opt);

Usage

The EgorBuilder class is used to build an initial optimizer setting the objective function, an optional random seed (to get reproducible runs) and a design space specifying the domain and dimensions of the inputs x.

The min_within() and min_within_mixed_space() methods return an Egor object, the optimizer, which can be further configured. The first one is used for continuous input space (eg floats only), the second one for mixed-integer input space (some variables, components of x, may be integer, ordered or categorical).

Some of the most useful options are:

• Specification of the size of the initial DoE. The default is nx+1 where nx is the dimension of x. If your objective function is not expensive you can take 3*nx to help the optimizer approximating your objective function.

    egor_config.n_doe(100);

You can also provide your initial doe though the egor.doe(your_doe) method.

• As the dimension increase the gaussian process surrogate building may take longer or even fail in this case you can specify a PLS dimension reduction [Bartoli2019]. Gaussian process will be built using the ndim (usually 3 or 4) main components in the PLS projected space.

    egor_config.kpls_dim(3);

• Specifications of constraints (expected to be negative at the end of the optimization) In this example below we specify that 2 constraints will be computed with the objective values meaning the objective function is expected to return an array ‘[nsamples, 1 obj value + 2 const values]’.

    egor_config.n_cstr(2);

• If the default infill strategy (WB2, Watson and Barnes 2nd criterion), you can switch for either EI (Expected Improvement) or WB2S (scaled version of WB2). See [Priem2019]

    egor_config.infill_strategy(InfillStrategy::EI);

• The default gaussian process surrogate is parameterized with a constant trend and a squared exponential correlation kernel, also known as Kriging. The optimizer use such surrogates to approximate objective and constraint functions. The kind of surrogate can be changed using regression_spec and correlation_spec() methods to specify trend and kernels tested to get the best approximation (quality tested through cross validation).

    egor_config.regression_spec(RegressionSpec::CONSTANT | RegressionSpec::LINEAR)
               .correlation_spec(CorrelationSpec::MATERN32 | CorrelationSpec::MATERN52);

In the above example all GP with combinations of regression and correlation will be tested and the best combination for each modeled function will be retained. You can also simply specify RegressionSpec::ALL and CorrelationSpec::ALL to test all available combinations but remember that the more you test the slower it runs.

Implementation notes

• Mixture of experts and PLS dimension reduction is explained in [Bartoli2019]
• Parallel optimization is available through the selection of a qei strategy. More information in [Ginsbourger2010]
• Mixed integer approach is implemented using continuous relaxation. More information in [Garrido2018]

References

[Bartoli2019]: Bartoli, Nathalie, et al. Adaptive modeling strategy for constrained global optimization with application to aerodynamic wing design Aerospace Science and technology 90 (2019): 85-102.

[Priem2019] Priem, Rémy, Nathalie Bartoli, and Youssef Diouane. On the use of upper trust bounds in constrained Bayesian optimization infill criteria. AIAA aviation 2019 forum. 2019.

[Ginsbourger2010]: Ginsbourger, D., Le Riche, R., & Carraro, L. (2010). Kriging is well-suited to parallelize optimization.

[Garrido2018]: E.C. Garrido-Merchan and D. Hernandez-Lobato. Dealing with categorical and integer-valued variables in Bayesian Optimization with Gaussian processes.

Modules

• ei
• wb2

Structs

• CorrelationSpec
  Enums for regression and correlation selection Flags to specify tested correlation models during experts selection (see correlation_spec()).
• Egor
  Egor optimizer structure used to parameterize the underlying argmin::Solver and trigger the optimization using argmin::Executor.
• EgorBuilder
  EGO optimizer builder allowing to specify function to be minimized subject to constraints intended to be negative.
• EgorConfig
  Egor optimizer configuration
• EgorService
  Egor optimizer service.
• EgorServiceBuilder
  EGO optimizer service builder allowing to use Egor optimizer as a service.
• EgorSolver
  Implementation of argmin::core::Solver for Egor optimizer. Therefore this structure can be used with argmin::core::Executor and benefit from observers and checkpointing features.
• EgorState
  Maintains the state from iteration to iteration of the crate::EgorSolver.
• ExpectedImprovement
• MixintContext
  A factory to build consistent sampling method and surrogate regarding XType specifications
• MixintGpMixParams
  Parameters for mixture of experts surrogate model
• MixintMoe
  The Moe model that takes into account XType specifications
• MixintMoeValidParams
  A decorator of Moe surrogate builder that takes into account XType specifications
• MixintSampling
  A decorator of LHS sampling that takes into account XType specifications casting continuous LHS result from floats to discrete types.
• ObjFunc
  As structure to handle the objective and constraints functions for implementing argmin::CostFunction to be used with argmin framework.
• OptimResult
  Optimization result
• RegressionSpec
  Enums for regression and correlation selection Flags to specify tested regression models during experts selection (see regression_spec()).
• WB2Criterion

Enums

• EgoError
  An error for efficient global optimization algorithm
• InfillOptimizer
  Optimizer used to optimize the infill criteria
• InfillStrategy
  Infill criterion used to select next promising point
• QEiStrategy
  Strategy to choose several points at each iteration to benefit from parallel evaluation of the objective function (The Multi-points Expected Improvement (q-EI) Criterion)
• XType
  An enumeration to define the type of an input variable component with its domain definition

Constants

• DEFAULT_CSTR_TOL
  Default tolerance value for constraints to be satisfied (ie cstr < tol)
• DOE_FILE
  Numpy Filename for current DOE dump
• DOE_INITIAL_FILE
  Numpy filename for initial DOE dump
• EI
  Expected Improvement infill criterion
• WB2
  WB2 infill criterion
• WB2S
  WB2 scaled infill criterion

Traits

• GroupFunc
  An interface for objective function to be optimized
• InfillCriterion
  A trait for infill criterion which maximmum location will determine the next most promising point expected to be the optimum location of the objective function
• ObjFn
• SurrogateBuilder
  A trait for surrogate training

Functions

• as_continuous_limits
  Expand xlimits to add continuous dimensions for enumeration x features.
• find_best_result_index
  Find best (eg minimal) cost value (y_data[0]) with valid constraints (y_data[1..] < cstr_tol). y_data containing ns samples [objective, cstr_1, … cstr_nc] is given as a matrix (ns, nc + 1)
• to_continuous_space
  Continuous relaxation of x given possibly discrete types Alias of unfold_with_enum_mask
• to_discrete_space
  Convenient method to pass from continuous unfolded space to discrete folded space
• to_xtypes
  Build xtypes from simple float bounds of x input components when x belongs to R^n. xlimits are bounds of the x components expressed a matrix (dim, 2) where dim is the dimension of x the ith row is the bounds interval [lower, upper] of the ith comonent of x.

Type Aliases

• MoeBuilder
  Moe type builder for mixed-integer Egor optimizer
• Result
  A result type for EGO errors