MCS algorithm

The second one, splitting by expected gain, employs a local one-dimensional parabolic quadratic model (surrogate) along a single coordinate.

The algorithm is guaranteed to converge to the global minimum in the long run (i.e. when the number of function evaluations and the search depth are arbitrarily large) if the objective function is continuous in the neighbourhood of the global minimizer.

This follows from the fact that any box will become arbitrarily small eventually, hence the spacing between samples tends to zero as the number of function evaluations tends to infinity.

MCS is designed to be implemented in an efficient recursive manner with the aid of trees.

With this approach the amount of memory required is independent of problem dimensionality since the sampling points are not stored explicitly.

A cartoon centipede reads books and types on a laptop.
Figure 1: MCS algorithm ( without local search) applied to the two-dimensional Rosenbrock function . The global minimum is located at . MCS identifies a position with within 21 function evaluations. After additional 21 evaluations the optimal value is not improved and the algorithm terminates. Observe dense clustering of samples around potential minima - this effect can be reduced significantly by employing local searches appropriately.
no alt
Figure 2: MCS (without local search) applied to the Himmelblau's function with four local minima where .