# Surrogate Library

The *SGTELIB* library is a dynamic surrogate modelling library. It is used in the *Search* step of Mads to dynamically construct models from the previous evaluations.
During a *Search* step that uses *SGTELIB*, models of the objective and the constraints are constructed and a surrogate subproblem involving these models is optimized.
The resulting solutions are the next candidates for evaluation by the true problem.

*SGTELIB*library can be used by setting the parameter

`SGTELIB_MODEL_SEARCH`

to `yes`

or `true`

.## Models

Models in *SGTELIB* are defined by using a succession of field names and field values.
To choose a model, the parameter `SGTELIB_MODEL_DEFINITION`

must be used followed by the field name `TYPE`

, and then by the model type.
The subsequent fields enable to define the settings of the model.
Each field name is made of one single word and each field value is made of one single word or numerical value.

Example : `SGTELIB_MODEL_DEFINITION TYPE <model type> FIELD1 <field 1 value> FIELD2 <field 2 value>`

The section below describes the models and settings available.

### Types of models

Below is the list of all possible models and their authorized fields.

`PRS`

DEGREE (Can be optimized)

RIDGE (Can be optimized)

BUDGET: Defines the budget allocated for parameter optimization.

OUTPUT: Defines the output text file.

`TYPE PRS DEGREE 2`

`TYPE PRS DEGREE OPTIM RIDGE OPTIM`

`PRS_EDGE`

DEGREE (Can be optimized)

RIDGE (Can be optimized)

BUDGET: Defines the budget allocated for parameter optimization.

OUTPUT: Defines the output text file.

`TYPE PRS_EDGE DEGREE 2`

`TYPE PRS_EDGE DEGREE OPTIM RIDGE OPTIM`

`PRS_CAT`

DEGREE (Can be optimized)

RIDGE (Can be optimized)

BUDGET: Defines the budget allocated for parameter optimization.

OUTPUT: Defines the output text file.

`TYPE PRS_CAT DEGREE 2`

`TYPE PRS_CAT DEGREE OPTIM RIDGE OPTIM`

`RBF`

KERNEL_TYPE (Can be optimized)

KERNEL_SHAPE (Can be optimized)

DISTANCE_TYPE (Can be optimized)

RIDGE (Can be optimized)

PRESET: Defines the type of RBF model used.

BUDGET: Defines the budget allocated for parameter optimization.

OUTPUT: Defines the output text file.

`TYPE RBF KERNEL_TYPE D1 KERNEL_SHAPE OPTIM DISTANCE TYPE NORM2`

`KS`

KERNEL_TYPE (Can be optimized)

KERNEL_SHAPE (Can be optimized)

DISTANCE_TYPE (Can be optimized)

BUDGET: Defines the budget allocated for parameter optimization.

OUTPUT: Defines the output text file.

`TYPE KS KERNEL_TYPE OPTIM KERNEL_SHAPE OPTIM`

`KRIGING`

RIDGE (Can be optimized)

DISTANCE_TYPE (Can be optimized)

BUDGET: Defines the budget allocated for parameter optimization.

OUTPUT: Defines the output text file.

`TYPE KRIGING`

`LOWESS`

DEGREE: Must be 1 (default) or 2 (Can be optimized).

RIDGE (Can be optimized)

KERNEL_TYPE (Can be optimized)

KERNEL_SHAPE (Can be optimized)

DISTANCE_TYPE (Can be optimized)

PRESET: Defines how the weight of each data point is computed.

BUDGET: Defines the budget allocated for parameter optimization.

OUTPUT: Defines the output text file.

`TYPE LOWESS DEGREE 1`

`TYPE LOWESS DEGREE OPTIM KERNEL_SHAPE OPTIM KERNEL_TYPE D1`

`TYPE LOWESS DEGREE OPTIM KERNEL_SHAPE OPTIM KERNEL_TYPE OPTIM DISTANCE TYPE OPTIM`

`CN`

DISTANCE_TYPE (Can be optimized)

BUDGET: Defines the budget allocated for parameter optimization.

OUTPUT: Defines the output text file.

`TYPE CN`

`ENSEMBLE`

WEIGHT: Defines how the ensemble weights are computed.

METRIC: Defines which metric is used to compute the weights.

DISTANCE_TYPE: This parameter is transfered to the models contained in the Ensemble.

PRESET: Defines the selection of models in the ensemble.

BUDGET: Defines the budget allocated for parameter optimization.

OUTPUT: Defines the output text file.

`TYPE ENSEMBLE WEIGHT SELECT METRIC OECV`

`TYPE ENSEMBLE WEIGHT OPTIM METRIC RMSECV DISTANCE TYPE NORM2 BUDGET 100`

`ENSEMBLE_STAT`

all the fields from ENSEMBLE (with different default values though).

UNCERTAINTY: Selects an alternative for the uncertainty (smooth or nonsmooth).

SIZE_PARAM: Defines the size parameter (different meaning depending on the value of UNCERTAINTY).

SIGMA_MULT: Defines the scaling factor of the uncertainty.

LAMBDA_P: Defines the shape parameter of the probability of feasibility.

LAMBDA_PI: Defines the shape parameter of the probability of improvement.

`TYPE ENSEMBLE_STAT UNCERTAINTY SMOOTH WEIGHT SELECT5 METRIC RMSECV SIZE_PARAM 15`

The following table summarizes the possible fields for every model.

Model type |
|||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

✔ |
✔ |
✔ |
✔ |
||||||||

✔ |
✔ |
✔ |
✔ |
||||||||

✔ |
✔ |
✔ |
✔ |
||||||||

✔ |
✔ |
✔ |
✔ |
✔ |
✔ |
✔ |
|||||

✔ |
✔ |
✔ |
✔ |
✔ |
|||||||

✔ |
✔ |
✔ |
✔ |
||||||||

✔ |
✔ |
✔ |
✔ |
✔ |
✔ |
✔ |
✔ |
||||

✔ |
✔ |
✔ |
|||||||||

✔ |
✔ |
✔ |
✔ |
✔ |
✔ |
||||||

✔ |
✔ |
✔ |
✔ |
✔ |
✔ |
✔ |

### Main model parameters

Below is the list of fields and their descriptions.

`DEGREE`

For PRS models, the default degree is 2.

For LOWESS models, the degree must be 1 (default) or 2.

`TYPE PRS DEGREE 3 defines a PRS model of degree 3.`

`TYPE PRS_EDGE DEGREE 2 defines a PRS_EDGE model of degree 2.`

`TYPE LOWESS DEGREE OPTIM defines a LOWESS model where the degree is optimized.`

`RIDGE`

`TYPE PRS DEGREE 3 RIDGE 0`

defines a PRS model of degree 3 with no ridge.`TYPE PRS DEGREE OPTIM RIDGE OPTIM`

defines a PRS model where the degree and ridge coefficient are optimized.`KERNEL_TYPE`

`KERNEL`

is equivalent.`D1`

: Gaussian kernel`D2`

: Inverse Quadratic Kernel`D3`

: Inverse Multiquadratic Kernel`D4`

: Bi-quadratic Kernel`D5`

: Tri-cubic Kernel`D6`

: Exponential Sqrt Kernel`D7`

: Epanechnikov Kernel`I0`

: Multiquadratic Kernel`I1`

: Polyharmonic splines, degree 1`I2`

: Polyharmonic splines, degree 2`I3`

: Polyharmonic splines, degree 3`I4`

: Polyharmonic splines, degree 4`OPTIM`

: The type of kernel is optimized

`D1`

, except for RBF models where it is `I2`

.`TYPE KS KERNEL_TYPE D2`

defines a KS model with Inverse Quadratic Kernel.`TYPE KS KERNEL_TYPE OPTIM KERNEL_SHAPE OPTIM`

defines a KS model with optimized kernel shape and type.`KERNEL_SHAPE`

`KERNEL_COEF`

is equivalent. Note that this field name has no impact for kernel types `I1`

, `I2`

, `I3`

and `I4`

because these kernels do not include a shape parameter.`TYPE RBF KERNEL_TYPE D4 KERNEL_SHAPE 10`

defines a RBF model with an inverse bi-quadratic kernel of shape coefficient \(10\).`TYPE KS KERNEL_TYPE OPTIM KERNEL_SHAPE OPTIM`

defines a KS model with optimized kernel shape and type.`DISTANCE_TYPE`

`NORM1`

: Euclidian distance`NORM2`

: Distance based on norm \(1\)`NORMINF`

: Distance based on norm \(1\)`NORM2_IS0`

: Tailored distance for discontinuity in \(0\)`NORM2_CAT`

: Tailored distance for categorical models

`NORM2`

.`TYPE KS DISTANCE NORM2_IS0`

defines a KS model tailored for VAN optimization.`PRESET`

- When applied to RBF models, PRESET defines the type of RBF.
Possible values:

`O`

: RBF with linear terms and orthogonal constraints`R`

: RBF with linear terms and regularization term`I`

: RBF with incomplete set of basis functions (see [AuKoLedTa2016] for RBFI models)

Default value:`I`

.Example:`TYPE RBF PRESET O`

- When applied to LOWESS models [TaAuKoLed2016], PRESET defines how the weight \(w_i\) of each data point \(x_i\) is computed.
Possible values:

`D`

: \(w_i=\phi(d_i)\) where \(\phi\) is the kernel of type and shape defined by the fields KERNEL_TYPE and KERNEL_SHAPE, respectively, and \(d_i\) is the distance between the prediction point and the data point \(x_i\)`DEN`

: \(w_i=\phi(d_i/d_q)\) where \(d_q\) is the distance between the prediction point and the \(q^{th}\) closest data point, and \(d_q\) is computed with an empirical method`DGN`

: \(w_i=\phi(d_i/d_q)\) where \(d_q\) is computed with the Gamma method`RE`

: \(w_i=\phi(r_i)\) where \(r_i\) is the rank of \(x_i\) in terms of distance to the prediction point, and \(r_i\) is computed with empirical method`RG`

: \(w_i=\phi(r_i)\) where \(r_i\) is computed with the Gamma method`REN`

: same as`RE`

but the ranks are normalized in \([0,1]\)`RGN`

: same as`RG`

but the ranks are normalized in \([0,1]\)

Default value:`DGN`

.Example:`TYPE LOWESS PRESET RE`

- When applied to ENSEMBLE or ENSEMBLE_STAT models, PRESET determines the selection of models in the ensemble.
Possible values:

`DEFAULT`

: selection of 18 models of types PRS, KS, RBF and CN with various settings`KS`

: selection of 7 models of type KS with various kernel shapes`PRS`

: selection of 7 models of type PRS with various degrees`IS0`

: selection of 30 models of type PRS_EDGE, KS, RBF with various settings and DISTANCE_TYPE set to NOMR2_IS0`CAT`

: selection of 30 models of type PRS_EDGE, KS, RBF with various settings and DISTANCE_TYPE set to NOMR2_CAT`SUPER1`

: selection of 4 models of types PRS, KS, RBF and LOWESS

Default value:`DEFAULT`

.Example:`TYPE ENSEMBLE PRESET SUPER1`

`WEIGHT`

`WEIGHT_TYPE`

is equivalent.`WTA1`

: \(w_k \propto \mathcal{E}_{sum} - \mathcal{E}_k\)`WTA3`

: \(w_k \propto (\mathcal{E}_k + \alpha\mathcal{E}_{mean})^{\beta}\)`SELECT`

: \(w_k \propto 1\) if \(\mathcal{E}_k = \mathcal{E}_{min}\) (only the best model is selected)`SELECTN`

: \(w_k \propto \mathcal{E}_{sum}^N - \mathcal{E}_k\) (for \(N=1,2,\dots,6\))`OPTIM`

: \(\boldsymbol{w}\) minimizes \(\mathcal{E}(\boldsymbol{w})\)

Where \(\mathcal{E}_k\) is the error metric (defined by the field name METRIC) of the \(k^{th}\) model in the ensemble, \(\mathcal{E}_{sum}\) is the cumulated error of all models, \(\mathcal{E}_{min}\) is the minimal error, \(\mathcal{E}_{mean}\) is the average error, \(\alpha=0.05\), \(\beta=-1\), and \(\mathcal{E}_{sum}^N\) is the cumulated error metric of the \(N\) best models.

`SELECT`

for ENSEMBLE models, `SELECT3`

for ENSEMBLE_STAT models with UNCERTAINTY set to `SMOOTH`

, and `SELECT4`

for ENSEMBLE_STAT models with UNCERTAINTY set to `NONSMOOTH`

.`TYPE ENSEMBLE WEIGHT SELECT METRIC RMSECV`

defines an ensemble of models which selects the model that has the best RMSECV.`TYPE ENSEMBLE WEIGHT OPTIM METRIC RMSECV`

defines an ensemble of models where the weights \(\boldsymbol{w}\) are computed to minimize the RMSECV of the model.`TYPE ENSEMBLE WEIGHT SELECT3 METRIC OECV`

defines an ensemble of models which selects the 3 models that have the best OECV.`UNCERTAINTY`

(specific to ENSEMBLE_STAT models)

`SMOOTH`

: Smooth alternative of the uncertainty (default)`NONSMOOTH`

: Nonmooth alternative of the uncertainty

`TYPE ENSEMBLE_STAT UNCERTAINTY NONSMOOTH`

`SIZE_PARAM`

(advanced parameter specific to ENSEMBLE_STAT models)

the simplex used to compute the simplex gradients of the models if the field UNCERTAINTY is set to

`SMOOTH`

the positive spanning set used to compare models values if the field UNCERTAINTY is set to

`NONSMOOTH`

`SMOOTH`

, \(0.005\) if the field UNCERTAINTY is set to `NONSMOOTH`

.`TYPE ENSEMBLE_STAT UNCERTAINTY SMOOTH SIZE_PARAM 0.003`

`SIGMA_MULT`

(advanced parameter specific to ENSEMBLE_STAT models)

`TYPE ENSEMBLE_STAT UNCERTAINTY NONSMOOTH SIGMA_MULT 30`

`LAMBDA_P`

(advanced parameter specific to ENSEMBLE_STAT models)

*probability of feasibility*(P).

`SMOOTH`

, \(1\) if the field UNCERTAINTY is set to `NONSMOOTH`

.`TYPE ENSEMBLE_STAT UNCERTAINTY NONSMOOTH LAMBDA_P 1.5`

`LAMBDA_PI`

(advanced parameterspecific to ENSEMBLE_STAT models)

*probability of improvement*(PI).

`SMOOTH`

, \(0.5\) if the field UNCERTAINTY is set to `NONSMOOTH`

.`TYPE ENSEMBLE_STAT UNCERTAINTY NONSMOOTH LAMBDA_PI 0.3`

`OUTPUT`

Defines a text file in which model information are recorded. Allowed for ALL types of model.

### Parameter optimization and selection

Below is the list of some field names and values that influence the behaviour of other fields.

`OPTIM`

`TYPE PRS DEGREE OPTIM`

`TYPE LOWESS DEGREE OPTIM KERNEL_TYPE OPTIM KERNEL_SHAPE OPTIM METRIC ARMSECV`

`METRIC`

`EMAX`

: Error Max`EMAXCV`

: Error Max with Cross-Validation`RMSE`

: Root Mean Square Error`RMSECV`

: RMSE with Cross-Validation`OE`

: Order Error`OECV`

: Order Error with Cross-Validation [AuKoLedTa2016]`LINV`

: Invert of the Likelihood`AOE`

: Aggregate Order Error`AOECV`

: Aggregate Order Error with Cross-Validation [TaAuKoLed2016]

`TYPE ENSEMBLE WEIGHT SELECT METRIC RMSECV`

defines an ensemble of models which selects the model that has the best RMSECV.`BUDGET`

`TYPE LOWESS KERNEL_SHAPE OPTIM METRIC AOECV BUDGET 100`

`TYPE ENSEMBLE WEIGHT OPTIM METRIC RMSECV BUDGET 50`

## Surrogate subproblem formulations

The *SGTELIB* library offers different formulations of the surrogate subproblem to be optimized at the *Search* step (see [TaLeDKo2014]).
The `SGTELIB_MODEL_FORMULATION`

parameter enables to choose a formulation, and the parameter `SGTELIB_MODEL_DIVERSIFICATION`

enables to adjust a diversification parameter.

`SGTELIB_MODEL_FORMULATION`

`SGTELIB_MODEL_FORMULATION`

. Some formulations involve a parameter \(\lambda\) that is described later.`FS`

(default):

`FSP`

:

where \(\mathrm{P}\) is the *probability of feasibility* which is the probability that a given point is feasible.

`EIS`

:

where \(\mathrm{EI}\) is the *expected improvement* that takes into account the probability of improvement and
the expected amplitude thereof.

`EFI`

:

where \(\mathrm{EFI}\) is the *expected feasible improvement* : \(\mathrm{EFI} = \mathrm{EI}\times\mathrm{P}\).

`EFIS`

:

`EFIM`

:

where \(\mu\) is the *uncertainty in the feasibility* : \(\mu = 4\mathrm{P}\times(1-\mathrm{P})\).

`EFIC`

:

`PFI`

:

where \(\mathrm{PFI}\) is the *probability of improvement* : \(\mathrm{PFI} = \mathrm{PI}\times\mathrm{P}\),
with \(\mathrm{PI}\) being the *probability of improvement* which is the probability that the objective decreases from the best known value at a given point.

`SGTELIB_MODEL_DEFINITION TYPE KRIGING`

`SGTELIB_MODEL_FORMULATION EFIC`

`SGTELIB_MODEL_DIVERSIFICATION`

`SGTELIB_MODEL_DIVERSIFICATION`

.`SGTELIB_MODEL_DEFINITION TYPE ENSEMBLE`

`SGTELIB_MODEL_FORMULATION FSP`

`SGTELIB_MODEL_DIVERSIFICATION 0.1`