# Optimization via Infill Criteria using Surrogates¶

When dealing with a non linear problem (NLP), such as in (3), typically it is resorted to classical solvers (e.g. SQP, trust-region-dogleg, genetic algorithms, simulated annealing, etc.) to obtain its solution, depending on the nature of the NLP (e.g. presence of discontinuities, whether or not the function is differentiable, etc.).

There is a entire field of study dedicated to find these NLP solutions with
*Kriging* surrogates. In the works of
[20][30][11][1], there are entire
discussions and frameworks on how to solve non linear problems and
comparisons of several metrics involved in the optimization process with
metamodels.

The premise of performing a optimization using surrogates is that the model to be optimized is too time consuming or computationally expensive to be solved with classical solvers. To circumvent this, the following steps are proposed:

Build an approximation model with

*Kriging*surrogates using a limited number of initial samples. This approximation is a “generalist” enough representation of the real model;Perform an optimization of the approximation model using classical NLP solvers and an infill criteria. The surrogate model reduces the “search area” needed by the solver;

Compare the surrogate optimum found in step 2 with the result from original model. In other words: feed the results from the

*Kriging*metamodel optimum into the original model and see if they are close enough;If the optimum from the metamodel is close enough (based on a chosen metric) to the original model, then this may be the true optimum. Otherwise, update the

*Kriging*model by introducing the value found and return to step 2;

This process is basically “filling holes” (hence the name *infill*)
in our *Kriging* metamodel until original model optimum is found. To illustrate
this in the simplest way, we are going to use the same function (24).

Assuming that we only have three initial points sampled from this model
function, we build our *Kriging* model. As can be seen in Fig. 126.

When applying an optimization solver on the *Kriging* model, we get a new
optimal value for \(x\) near 7.8 (3.47 for \(f(x)\)) in the
sample and rebuild the *Kriging* metamodel. The result is shown
Fig. 127. We keep repeating this procedure until we get the result
in Fig. 128.

This is the entire process animated in Fig. 129:

This example is a trivial one because the problem involves a single input
variable and infill criteria is the own *Kriging* prediction of the model. As
discussed in [20], this criteria has its pitfalls if used
without other precautions.

[6] presented an algorithm, based on the “method 2” in the work of [20], referred as a gradient matching technique where the gradient of the surrogate is forced to match with the true function gradient, this is done through trust-region approach to ensure local convergence which was proven in the work of [1].

Important

The basic idea of this approach is:

Minimize the NLP problem metamodel.

Consult the original function at the minimum found in the metamodel.

Update the sample matrix used to build the surrogate.

Repeat this until a convergence criteria is met.

The flowchart depicting the whole procedure is defined in Fig. 130. For detailed explanation of each step of the proposed algorithm, one must refer to [6] and [3].