An empirical study of various candidate selection and partitioning techniques in the  framework

Study of various candidate selection and partitioning techniques used in

Linas Stripinis         Remigijus Paulavičius

L. Stripinis, R. Paulavičius Vilnius University, Institute of Data Science and Digital Technologies, Akademijos 4, LT-08663 Vilnius, Lithuania

R. Paulavičius<EMAIL_ADDRESS>
Over the last three decades, many attempts have been made to improve the  (DIviding RECTangles) algorithm's efficiency.
Various novel ideas and extensions have been suggested.
The main two steps of -type algorithms are selecting and partitioning potentially optimal rectangles.
However, the most efficient combination of these two steps is an area that has not been investigated so far.
This paper presents a study covering an extensive examination of various candidate selection and partitioning techniques within the same  algorithmic framework.

Twelve -type algorithmic variations are compared on $800$  randomly generated GKLS-type test problems and $96$ box-constrained global optimization problems from  with varying complexity.
Based on these studies, we have identified the most efficient selection and partitioning combinations leading to new, more efficient, -type algorithms.
All these algorithms are included in the latest version of  and are publicly available.

90C26 90C56

§ INTRODUCTION

In this paper, we consider a box-constrained global optimization problem of the form:

\begin{equation}
\label{eq:opt-problem}
\begin{aligned}
& \min_{\mathbf{x}\in D} && f(\mathbf{x})
\end{aligned}
\end{equation}

where $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is a Lipschitz-continuous, potentially “black-box”  objective function, and $\mathbf{x}$ is the input vector.
Thus, we assume that the analytical information of the objective function $f$ is unknown and can only be obtained by evaluating $f$ at various points of the feasible region, which is an $n$-dimensional hyper-rectangle

\[
D = [ \mathbf{a},  \mathbf{b}] = \{ \mathbf{x} \in \mathbb{R}^n: a_j \leq x_j \leq b_j, j = 1, \dots, n\}.
\]

Moreover, $f$ can be non-linear, multi-modal, non-convex, and non-differentiable.

The optimization community attracted considerable interest from the simplicity and efficiency of the deterministic -type algorithms.
The original  algorithm was developed by Jones et al. [25] and is a well-known and widely used solution technique for derivative-free global optimization.
The  algorithm extends classical Lipschitz optimization [36, 37, 38, 39, 42, 43, 47, 49], where the need for the Lipschitz constant is eliminated.
This feature made -type methods especially attractive for solving various real-world optimization problems (see, e.g., [1, 2, 3, 5, 6, 11, 31, 35, 41, 53] and the references given therein).
Furthermore, the extensive numerical benchmarks in [44] revealed an encouraging performance of the  algorithm among other tested derivative-free global optimization approaches, belonging to genetic [22], simulated annealing [27], and particle swarm optimization [26].

Typically, the -type algorithms include three main steps: selection, sampling, and partitioning (subdivision).
At each iteration, a specific -type algorithm identifies (selects) the set of potentially optimal hyper-rectangles (POHs) and then samples and subdivides them.
The original  algorithm uses hyper-rectangular subdivisions based on $n$-dimensional trisection.
The objective function is evaluated at the center points of the newly-formed sub-rectangles.
Moreover, if several dimensions have the maximum side length,  starts trisection from the dimension with the lowest $w_j$ and continues to the highest [24, 25].
Here $w_j$ is defined as the best function values sampled along dimension $j$

\begin{equation}
w_j = \min \{ f(\mathbf{c} + \delta\mathbf{e}_j),  f(\mathbf{c} - \delta\mathbf{e}_j) \},
\end{equation}

where $j \in M$ (set of dimensions with the maximum side length), $\delta$ is equal to one-third of the maximum side length, $\mathbf{c}$ is the center of the hyper-rectangle, and $\mathbf{e}_j$ is the $j$th unit vector.
<Ref> illustrates the selection, sampling, and subdivision (trisection) in the original  algorithm for a two-dimensional Branin test function.

Since the original  algorithm was published, various -type extensions and modifications have been proposed.
One large group of existing modifications aim to improve the selection of POHs (see, e.g.,  [1, 10, 32, 35, 52]), while the other group concentrates on different partitioning techniques (see, e.g., [23, 28, 33, 40, 45]).
In addition, the authors also make some modifications to the other steps of their algorithms.

Consequently, it is unclear which suggested improvements have the most potential within the  algorithmic framework.

xlabel = $c_1$,
ylabel = $c_2$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
only marks,mark=*,color=black
Sampling point
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.05pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:1,1);
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.5,0.5) node[yshift=-8pt] $24.13$;

xlabel = $c_1$,

title=Iteration $1$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
area legend,blue!30,fill=blue!50,opacity=0.4
Selected POH
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,0.3333) (0,0.3333);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,0.6666) (0,0.6666);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0.3333) (0,0.6666) (0.3333,0.6666) (0.3333,0.3333);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (1,0.3333) (1,0.6666) (0.6666,0.6666) (0.6666,0.3333);
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:1,0.3333);
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.5,0.5) node[yshift=-8pt] $24.13$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.5,0.16666) node[yshift=-8pt] $2.41$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.5,0.83333) node[yshift=-8pt] $95.84$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.16666,0.5) node[yshift=-8pt] $13.10$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.83333,0.5) node[yshift=-8pt] $51.39$;

xlabel = $c_1$,

title=Iteration $2$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
area legend,black,fill=white,opacity=0.5
Unselected region
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0.3333,0.3333) rectangle (axis cs:0.6666,0.6666);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0.3333,0) rectangle (axis cs:0.6666,0.6666);
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0,0.6666) rectangle (axis cs:1,1);
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0.3333,0) rectangle (axis cs:0.6666,0.3333);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0.6666,0.3333) rectangle (axis cs:1,0.6666);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0,0.6666) rectangle (axis cs:1,1);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0,0.3333) rectangle (axis cs:0.3333,0.6666);

[only marks,mark=*, mark size=1.5pt,black] coordinates (0.5,0.5) node[yshift=-8pt] $24.13$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.5,0.16666) node[yshift=-8pt] $2.41$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.5,0.83333) node[yshift=-8pt] $95.84$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.16666,0.5) node[yshift=-8pt] $13.10$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.83333,0.5) node[yshift=-8pt] $51.39$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.16666,0.16666) node[yshift=-8pt] $70.96$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.83333,0.16666) node[yshift=-8pt] $14.69$;

Illustration of selection, sampling, and subdivision (trisection) used in the original  algorithm [25] on a two-dimensional Branin test function in the first two iterations

We address this problem by comparing various proposed candidate selection and partitioning techniques for the remaining algorithmic steps under the same conditions.
This way, we seek to improve the efficiency of existing -type algorithms by creating new combinations based on the previous proposals.
Twelve mostly new  -type algorithmic variations are introduced and investigated using three selection and four partitioning schemes.

The rest of the paper is organized as follows.
<Ref> reviews the original  algorithm and well-known -type modifications proposed for the candidate selection and subdivision.

The obtained new combinations are described in <Ref>.
An extensive experimental analysis using traditional test problems is presented in <Ref>, while on GKLS-type test problems in <Ref>.
Finally, in <Ref>, we conclude the paper.

§ OVERVIEW OF CANDIDATE SELECTION AND PARTITIONING TECHNIQUES USED IN -TYPE ALGORITHMS

This section reviews the most well-known strategies for selecting and partitioning potentially optimal candidates in -type algorithms.
We start with a brief review of the main steps of the original  algorithm, with particular emphasis on candidate selection and partitioning techniques.

§.§ Original  algorithm

The original  algorithm is a deterministic derivative-free global optimization [20, 48, 56] algorithm subject to simple box constraints.
The main steps of  are summarized in <Ref>.
At the Initialization step (see <Ref>, Lines <ref>–<ref>),  normalizes the search region $D$ to unit hyper-rectangle $\bar{D}$ and refers to the original space $D$ only when evaluating the objective function.
Regardless of the dimension $n$, the first evaluation of the objective function is performed at the midpoint of the unit hyper-rectangle $\mathbf{c}^1 = (1/2, \dots,1/2) \in \bar{D}$.

MmaxM$_{\rm max}$
KmaxK$_{\rm max}$

Objective function $(f)$, search domain $(D)$, and adjustable algorithmic options $(opt)$: tolerance ($\varepsilon_{\rm pe}$), maximal number of function evaluations ($\Mmax$) and algorithmic iterations ($\Kmax$) ;
The best found objective value $(f^{\min})$, solution point $(\mathbf{x}^{\min})$, and record of various performance metrics: percent error $(pe)$, number of iterations $(k)$, number of function evaluations $(m)$;
Initialization step:

Normalize the search domain $D$ to be the unit hyper-rectangle $\bar{D}$;

Evaluate the objective function at the center point ($\mathbf{c}^1$) of $\bar{D}$ and set:

$\mathbf{c}^1 = \left(\frac{1}{2}, \frac{1}{2}, ..., \frac{1}{2}\right)$;

$x^{\min}_j = \mid b_j - a_j \mid  c^1_j + a_j, j=1, \dots, n$; *[f]referring to $D$

$f^1 = f(\mathbf{x}^{\min})$, $f^{\min} = f^1$;

Initialize performance measures: $k=1$, $m=1$, $pe$; *[f]pe defined in (<ref>)

$pe > \varepsilon_{\rm pe}$ $m < \Mmax$ $k < \Kmax$

Selection step: Identify the set $S_k$ of POHs using <Ref>

$\bar{D}^j_k \in S_k$
Sampling step: Evaluate $f$ at the newly sampled points in $\bar{D}^j_k$;

Subdivision step: Trisect $\bar{D}^j_k$ as illustrated in <Ref>

Update $f^{\min}, \mathbf{x}^{\min}$, and performance measures: $k$, $m$ and $pe$;

Return $f^{\min}, \mathbf{x}^{\min}$, and performance measures: $k$, $m$ and $pe$.
Main steps of the  algorithm

Two of the most critical steps in the original  and other existing modifications are Selection and Subdivision.

§.§.§ Original selection strategy

Let the current partition at the iteration $ k $ is defined as

\[
\mathcal{P}_k = \{ \bar{D}^i_k : i \in \indexsett_k \},
\]

where $ \bar{D}^i_k = [\mathbf{a}^i, \mathbf{b}^i] = \{ \mathbf{x} \in \bar{D}: 0 \leq a_j^i \leq x_j \leq b_j^i \leq 1, j = 1,\dots, n, \forall i \in \indexsett_k \} $ and $ \indexsett_k $ is the index set identifying the current partition $ \mathcal{P}_k $.
The next partition, $\mathcal{P}_{k+1}$, is obtained by subdividing selected POHs from the current partition $ \mathcal{P}_k $.
Note there is only one candidate, $\bar{D}^1_1$, that at the first iteration ($k=1$), which is automatically potentially optimal.

The formal requirement of potential optimality in subsequent iterations is stated in <Ref>.

Let $ \mathbf{c}^i $ denote the center sampling point and $ \delta^i_k $ be a measure (equivalently, sometimes called distance or size) of the hyper-rectangle $ \bar{D}^i_k$.
Let $ \varepsilon > 0 $ be a positive constant and $f^{\min}$ be the best currently found value of the objective function.
A hyper-rectangle $ \bar{D}^h_k, h \in \indexsett_k $ is said to be potentially optimal if there exists some rate-of-change (Lipschitz) constant $ \tilde{L} > 0$ such that

\begin{eqnarray}
f(\mathbf{x}^h) - \tilde{L}\delta^h_k & \leq & f(\mathbf{x}^i) - \tilde{L}\delta^i_k, \quad \forall i \in \indexsett_k, \label{eqn:potOptRect1} \\
f(\mathbf{x}^h) - \tilde{L}\delta^h_k & \leq & f^{\min} - \varepsilon|f^{\min}|, \label{eqn:potOptRect2}
\end{eqnarray}

\begin{equation}
\label{eq:space_original}
x^i_j = \mid b_j - a_j \mid  c^i_j + a_j, j=1,\dots,n,
%	\mathbf{x}^i = \| \mathbf{b} - \mathbf{a} \|  \mathbf{c}^i + \mathbf{a},
\end{equation}

and the measure of the hyper-rectangle $ \bar{D}^i_k$ is

\begin{equation}
\label{eq:distance}
\delta^i_k = \frac{1}{2} \| {\mathbf{b}}^i - {\mathbf{a}}^i \|_2.
\end{equation}

The hyper-rectangle $ \bar{D}^j_k $ is potentially optimal if the lower Lipschitz bound for the objective function computed by the left-hand side of (<ref>) is the smallest one with some positive constant $\tilde{L}$ in the current partition $ \mathcal{P}_k $.
In (<ref>), the parameter $\varepsilon$ is used to protect from an excessive refinement of the local minima [25, 34].
In [25], the authors obtained good results for $\varepsilon$ values ranging from $10^{-3}$ to $10^{-7}$.
A geometrical interpretation of POH selection using <Ref> is illustrated on the left panel of <Ref>.
Here each hyper-rectangle is represented as a point.
The $x$-axis shows the size of the measure $(\delta)$ while the $y$-axis – the objective function value attained at the midpoint $(\mathbf{c})$ of this hyper-rectangle.
The hyper-rectangles meeting conditions (<ref>) and (<ref>) are points on the lower-right convex hull (highlighted in blue color).

However, such a selection strategy can be especially inefficient, e.g., for symmetric problems.
There may be many POHs with the same diameter $\delta^i_k$ and objective value, leading to a drastic increase of selected POHs per iteration.
To overcome this, authors in [11] proposed selecting only one of these many “equivalent” candidates.
In [24], the authors revealed that such modification could significantly increase the performance of the  algorithm.
In this paper, we call this an improved original selection strategy.

§.§.§ Original partitioning scheme

In the Sampling and Subdivision steps (see Algorithm <ref>, Lines <ref> and <ref>), a hyper-rectangular partition based on $n$-dimensional trisection is used.
Using this scheme, the POHs are partitioned into smaller non-intersecting hyper-rectangles (see <Ref>), containing the lower function values in larger new hyper-rectangles.

§.§ Other candidate selection schemes in -type algorithms

Various improvements and new ideas for candidate selection were proposed in the literature.
To prevent the  algorithm from being sensitive to the objective function's additive scaling, authors in [9] introduced a scaling of the objective function values by subtracting the median value calculated from the previously evaluated function values.
More specifically, in the selection step, a new  replaces (<ref>) from <Ref> to:

\begin{equation}
f(\mathbf{x}^i) - \tilde{L}\delta^i \leq f^{\min} - \varepsilon|f^{\min} - {f}^{\rm median}|. \label{eqn:potOptRectz}
\end{equation}

Similarly, in [29], authors adopted the similar idea in .
At each iteration, instead of the median value (${f}^{\rm median}$), authors proposed to use the average value $({f}^{\rm average})$:

\begin{equation}
f(\mathbf{x}^i) - \tilde{L}\delta^i \leq f^{\min} - \varepsilon|f^{\min} - {f}^{\rm average}|. \label{eqn:potOptRect4}
\end{equation}

The authors in [8, 28, 30] showed that different schemes controlling the $\varepsilon$ parameter in (<ref>) could increase the efficiency of the  algorithm, especially when needed to fine-tune the solution to higher accuracy.

In order to verify this, the experimental investigation of the original ,  (based on <ref>), and  (based on <ref>) algorithms on an extensive set consisting of $81$ test and six engineering problems (from  [54]) were performed in [50].
Our investigation revealed that in solving engineering problems, a significant performance difference was not observed.
However, on $81$ test problems, the original  proved to be more efficient, and using the same stopping conditions solved $10$ and $23$ more test problems than  and  accordingly (for details, see Table $3$ in [50]).
Based on this, the original eq. (<ref>) was used in an improved original selection strategy in our experimental study.

Below we focus on the other two selection schemes considered in this research.

§.§.§ Aggressive selection

In [1], the authors relaxed the selection criteria of POHs and proposed an aggressive version of the  algorithm ().
The main idea is to select and divide at least one hyper-rectangle from each group of different diameters $(\delta_k^i)$ containing the lowest objective function value.
Such aggressive selection ensures much more objective function evaluations per iteration compared to other existing POH selection schemes.

From the optimization point of view, such an approach may seem less favorable since it “wastes” function evaluations by exploring unnecessary (non-potentially optimal) hyper-rectangles.
However, such a strategy is much more appealing in a parallel environment, as was shown in [15, 17, 18, 58].

In [16], authors showed that limiting the refinement of the search-space when the size of hyper-rectangles $ \delta^i_k $ reached some prescribed size $ \delta^{\rm limit} $, the memory usage reduces from $10 \%$ to $70 \%$, and the algorithm can run longer without memory allocation failure.
In the experimental part (described in <Ref>), the limit parameter $ (\delta^{\rm limit}) $ was set to the size of a hyper-rectangle that has been subdivided $ 50 n $ times.
The $ \delta^{\rm limit} $ parameter is intended for the same purpose as the equation (<ref>) and tries to avoid wasting function estimates by “over-exploring” the local minimum area.
We call this an improved aggressive selection strategy.
A geometrical interpretation of the aggressive selection is shown in the middle panel of <Ref>.

group style=

group size=3 by 1,

x descriptions at=edge bottom,
y descriptions at=edge left,

vertical sep=0pt,
horizontal sep=6pt,

title  = 3.7cmOriginal  selection,
xlabel = $\delta$,
ylabel = Function values,
ytick distance=0.2,
xtick distance=0.2,

legend style=font=,

black!60,only marks,mark=*,mark size=2pt
non-potentially optimal
blue,mark=*,mark size=2.5pt
potentially optimal
[black!60,only marks,mark=*,mark size=2pt] table[x=D,y=F] data/ddr2.txt;
[blue,mark=*,mark size=2.5pt] table[x=D_pot_opt,y=F_pot_opt] data/ddr2.txt;
title  = 3.7cmAggressive selection,
xlabel = $\delta$,
ytick distance=0.25,
xtick distance=0.2,
black!60,only marks,mark=*,mark size=2pt
non-potentially optimal
blue,mark=*,mark size=2.5pt
potentially optimal
[black!60,only marks,mark=*,mark size=2pt] table[x=D,y=F] data/ddr1.txt;
[blue,mark=*,mark size=2.5pt] table[x=D_pot_opt,y=F_pot_opt] data/ddr1.txt;
title  = 3.7cmPareto selection,
xlabel = $\delta$,
xtick distance=0.2,
black!60,only marks,mark=*,mark size=2pt
non-potentially optimal
blue,mark=*,mark size=2.5pt
potentially optimal
[black!60,only marks,mark=*,mark size=2pt] table[x=D,y=F] data/ddr.txt;
[blue,mark=*,mark size=2.5pt] table[x=D_pot_opt,y=F_pot_opt] data/ddr.txt;

Comparison of three different selection schemes (original , aggressive, and Pareto) applied on the same set of points

§.§.§ Two-step-based Pareto selection

In a more recent modification  [52], we proposed a new two-step-based selection strategy for the identification of the extended set of POHs.
In both steps,  selects only Pareto optimal hyper-rectangles: in the ﬁrst step, non-dominated on size (the higher, the better) and center point function value (the lower, the better), while in the second, non-dominated on size and distance from the current minimum point (the closer, the better) and takes the unique union of identified candidates in both steps.
We note this scheme does not have any protection against over-exploration in sub-optimal local minima regions.

A geometrical interpretation of the selection procedure is shown in the right panel of <Ref>.
In the first step,  selects Pareto hyper-rectangles concerning the size and function value.
Therefore, unlike the  strategy, hyper-rectangles from the groups where the minimum objective function value is higher than the minimum value from the larger groups are not selected in .
Compared to the original selection (Definitions <ref>), in , the set of POHs is enlarged by adding more medium-sized hyper-rectangles.
In this sense, Pareto selection may be more global than the original  selection.
Additionally, in the second step,  selects the hyper-rectangles that are non-dominated concerning the size and distance from the current minimum point.
This way, the set of POHs is enlarged with various size hyper-rectangles nearest the current minimum point, assuring a broader examination around it.

§.§ Other partitioning schemes in -type algorithms

§.§.§ Trisection strategy, along single the longest side

In [23], the author proposed a revised version of the original  algorithm.
One of the main modifications is to trisect selected POHs only along the single longest side (coordinate), see <Ref>.
If there are several equal longest sides, the coordinate that has been split the least times during the entire search process so far is selected.
If there is a tie on the latter criterion, the lowest indexed dimension is selected.
In [24], authors showed that dividing a selected rectangle on only one the longest side instead of all can significantly increase the convergence speed.

xlabel = $c_1$,
ylabel = $c_2$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
only marks,mark=*,color=black
Sampling point
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.05pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:1,1);
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.5,0.5) node[yshift=-8pt] $24.13$;

xlabel = $c_1$,

title=Iteration $1$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
area legend,blue!30,fill=blue!50,opacity=0.4
Selected POH
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:1,1);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0.3333,0) rectangle (axis cs:0.6666,1);
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:0.3333,1);
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.5,0.5) node[yshift=-8pt] $24.13$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.16666,0.5) node[yshift=-8pt] $13.10$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.83333,0.5) node[yshift=-8pt] $51.39$;

xlabel = $c_1$,

title=Iteration $2$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
area legend,black,fill=white,opacity=0.5
Not selected region
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:1,1);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0.3333,0) rectangle (axis cs:0.6666,1);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:0.3333,1);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0,0.3333) rectangle (axis cs:0.3333,0.6666);
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0,0.6666) rectangle (axis cs:0.3333,1);
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0.3333,0) rectangle (axis cs:0.6666,1);
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.5,0.5) node[yshift=-8pt] $24.13$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.16666,0.5) node[yshift=-8pt] $13.10$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.83333,0.5) node[yshift=-8pt] $51.39$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.16666,0.16666) node[yshift=-8pt] $70.96$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.16666,0.83333) node[yshift=-8pt] $5.24$;

Two-dimensional illustration of the partitioning technique used in the revised version of the  algorithm [23] on a two-dimensional Branin test function

§.§.§ Diagonal trisection strategy

Adaptive diagonal curves () based algorithm was introduced in [45].
Independently of the problem dimension, the  algorithm evaluates the objective function $f(\mathbf{x})$ at two vertices of the main diagonals of each hyper-rectangle $ \bar{D}_k^i$, as shown in <Ref>.
Same as in the revised version of  [23], each selected POH is trisected along just one of the longest sides.

Such a diagonal scheme potentially obtains more comprehensive information about the objective function than center sampling.
The center sampling strategies may sometimes take many iterations to find the solution when a hyper-rectangle containing the optimum has a midpoint with a very bad function value, which makes it undesirable for further selection.
The  algorithm intuitively reduces this chance for both sampling points in the hyper-rectangle containing the optimum solution by sampling two points per hyper-rectangle.
Therefore, better performance could be expected, especially solving more complex problems.

The main advantage of such a strategy is that it addresses one of the well-known algorithmic weaknesses of the original .
The feasible region boundary points can only be approached arbitrarily closely but never sampled using the center sampling technique.
Authors in [21, 28] have shown that the latter fact can cause very slow convergence to an optimum if it lies on the feasible region's boundary.

xlabel = $c_1$,
ylabel = $c_2$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
only marks,mark=*,color=black
Sampling point
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.05pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:1,1);
[only marks,mark=*, mark size=1.5pt,black] coordinates (1,1) node[yshift=-8pt,xshift=-12pt] $145.87$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0,0) node[yshift=8pt,xshift=12pt] $308.12$;

xlabel = $c_1$,

title=Iteration $1$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
area legend,blue!30,fill=blue!50,opacity=0.4
Selected POH
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:1,1);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0.3333,0) rectangle (axis cs:0.6666,1);
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0.3333,0) rectangle (axis cs:0.6666,1);
[only marks,mark=*, mark size=1.5pt,black] coordinates (1,1) node[yshift=-8pt,xshift=-12pt] $145.87$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0,0) node[yshift=8pt,xshift=12pt] $308.12$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.6666,0) node[yshift=8pt,xshift=-12pt] $14.34$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.3333,1) node[yshift=-8pt,xshift=12pt] $100.60$;

xlabel = $c_1$,

title=Iteration $2$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
area legend,black,fill=white,opacity=0.5
Not selected region
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:1,1);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0.3333,0) rectangle (axis cs:0.6666,1);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:0.3333,1);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0.3333,0.3333) rectangle (axis cs:0.6666,0.6666);
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0.3333,0) rectangle (axis cs:0.6666,0.3333);
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0.6666,0) rectangle (axis cs:1,1);

[only marks,mark=*, mark size=1.5pt,black] coordinates (1,1) node[yshift=-8pt,xshift=-12pt] $145.87$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0,0) node[yshift=8pt,xshift=12pt] $308.12$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.6666,0) node[yshift=8pt,xshift=-12pt] $14.34$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.3333,1) node[yshift=-8pt,xshift=12pt] $100.60$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.6666,0.6666) node[yshift=-8pt,xshift=12pt] $88.90$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.3333,0.3333) node[yshift=-8pt,xshift=-12pt] $20.60$;

Two-dimensional illustration of the diagonal trisection strategy introduced in the  [45] algorithm on a two-dimensional Branin test function

§.§.§ Diagonal bisection strategy

(secting angles) [33] is motivated by the diagonal partitioning approach [45, 46, 48].

The bisection is used instead of a trisection typical for diagonal-based and most -type algorithms.

However, neither sampling at the center nor the diagonal's endpoints are appropriate for bisection.
Therefore, in , the objective function is evaluated at two points lying on the diagonal equidistant between themselves and a diagonal's vertices (see <Ref>).
Such a sampling strategy enables the reuse of the sampling points in descendant hyper-rectangles.
Like the  algorithm (see <Ref>),  samples two points per hyper-rectangle.
Therefore, more comprehensive information about the objective function is considered compared to the central sampling strategy used in most -type algorithms.

xlabel = $c_1$,
ylabel = $c_2$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
only marks,mark=*,color=black
Sampling point
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.05pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:1,1);
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.3333,0.3333) node[yshift=8pt,xshift=-12pt] $20.60$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.6666,0.6666) node[yshift=8pt,xshift=12pt] $88.90$;

xlabel = $c_1$,

title=Iteration $1$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
area legend,blue!30,fill=blue!50,opacity=0.4
Selected POH
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.05pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:0.5,1);
[black, thick, mark size=0.1pt,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:0.5,1);
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.3333,0.3333) node[yshift=8pt,xshift=-12pt] $20.60$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.6666,0.6666) node[yshift=8pt,xshift=12pt] $88.90$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.8333,0.3333) node[yshift=-8pt,xshift=-12pt] $26.79$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.1666,0.6666) node[yshift=-8pt,xshift=12pt] $2.92$;

xlabel = $c_1$,

title=Iteration $2$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.925,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=0.1cm,
ytick distance=1/6,
xtick distance=1/6,
every axis/.append style=font=,
yticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
xticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
area legend,black,fill=white,opacity=0.5
Not selected region
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (0,0) (1,0) (1,1) (0,1) ;
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0.5,0) rectangle (axis cs:1,1);
[black, thick, mark size=0.1pt, fill=blue!50,opacity=0.4,line width=0.3mm] (axis cs:0,0.5) rectangle (axis cs:0.5,1);
[black, thick, mark size=0.1pt ,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:0.5,1);
[black, thick, mark size=0.1pt ,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:0.5,0.5);
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.3333,0.3333) node[yshift=8pt,xshift=-12pt] $20.60$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.6666,0.6666) node[yshift=8pt,xshift=12pt] $88.90$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.8333,0.3333) node[yshift=-8pt,xshift=-12pt] $26.79$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.1666,0.6666) node[yshift=-8pt,xshift=12pt] $2.92$;

[only marks,mark=*, mark size=1.5pt,black] coordinates (0.1666,0.1666) node[yshift=-8pt,xshift=12pt] $70.96$;
[only marks,mark=*, mark size=1.5pt,black] coordinates (0.3333,0.8333) node[yshift=8pt,xshift=-12pt] $61.85$;

Two-dimensional illustration of the diagonal bisection strategy used in the  algorithm [33] on a two-dimensional Branin test function

§ SUMMARY OF NEW -TYPE ALGORITHMIC VARIATIONS

In this section, we define new variations of the -type algorithms.
In total, twelve variants of -type algorithms are constructed (see <Ref>) by combining three different selection and four partitioning techniques reviewed in the previous section.

Abbreviations of new twelve -type algorithmic variations based on three different selection and four partitioning strategies

2c     4cPartitioning strategy

2c     N-DTC     1-DTC     1-DTDV     1-DBDP

3*901.6cmSelection scheme     IO     N-DTC-IO     1-DTC-IO     1-DTDV-IO     1-DBDP-IO

IA     N-DTC-IA     1-DTC-IA     1-DTDV-IA     1-DBDP-IA

GL     N-DTC-GL     1-DTC-GL     1-DTDV-GL     1-DBDP-GL

The selection strategies used to create these new -type algorithmic variations are:

1. Improved Original selection (IO) as described in <Ref>.

2. Improved Aggressive selection (IA) as described in <Ref>.

3. Two-step-based (Global-Local) Pareto selection (GL) as described in <Ref>.

The partitioning strategies used in these combinations are the following:

1. Hyper-rectangular partitioning based on N-Dimensional Trisection and objective function evaluations at Center points (N-DTC) as described in <Ref>.

2. Hyper-rectangular partitioning based on 1-Dimensional Trisection and objective function evaluations at Center points (1-DTC) as described in <Ref>.

3. Hyper-rectangular partitioning based on 1-Dimensional Trisection and objective function evaluations at two Diagonal Vertices (1-DTDV) as described in <Ref>.

4. Hyper-rectangular partitioning based on 1-Dimensional Bisection and objective function evaluations at two Diagonals Points (1-DBDP) as described in <Ref>.

Let us note that some constructed combinations are already used in existing -type algorithms.
For example, the N-DTC-GL algorithm is identical to the recently proposed  [52].
Furthermore, the N-DTC-IO and 1-DBDP-IO algorithms are highly related to  [25] and  [33] algorithms.
The only difference is that  and  algorithms select all “equivalent” candidates (with the same diameter and objective function value), while the IO selection rule restricts to one candidate.
The  [1] algorithm is close to the N-DTC-IA variation.
The only difference is the selection step using the limit parameter $ (\delta^{\rm limit}) $.
Moreover, discarding the local search subroutine from the revised hybrid version of the  algorithm [23] would lead to 1-DTC-IO variation.
Finally, the 1-DTDV-IO combination is highly related to the  algorithm [45], but the latter approach has distinct “local” and “global” phases in the selection procedure.

§ EXPERIMENTAL INVESTIGATION USING TEST PROBLEMS FROM

Test problems from the  library [55] (listed in <Ref> <Ref>) are used to evaluate the developed algorithms.

In total, we examined new algorithms on $96$  box-constrained global optimization test instances.
Note that different subsets (e.g., low dimensional problems $(n \le 4)$, non-convex problems, etc.) of the entire set were used to deepen the investigation.
All problems and algorithms are implemented in the Matlab R2022a environment and are included in the most recent version of  -type Matlab toolbox [51].

All computations were performed on 8th Generation Intel R Core$^\textit{TM}$ i7-8750H @ 2.20GHz Processor.
All $12$ algorithms were tested using a limit of M$_{\rm max} = 10^6$ function evaluations in each run.
For the $96$ analytical test cases with a priori known global optima $ f^* $, the used stopping criterion is based on the percent error:

\begin{equation}
\label{eq:pe}
\ pe = 100 \% \times
\begin{cases}
\frac{f({\mathbf{x}}) - f^*}{|f^*|},  & f^* \neq 0, \\
f({\mathbf{x}}),  & f^* = 0,
\end{cases}
\end{equation}

where $ f^* $ is the known global optimum.
In all experimental studies presented in this section, the algorithms were stopped when the percent error became smaller than the prescribed value $\varepsilon_{\rm pe} = 10^{-2}$ or when the number of function evaluations exceeded the prescribed limit of $10^6$.
In other words, we stop the search when the algorithm has attained an objective function value very close to the known optimum value.

Experimental results presented in this paper are also available in digital form in the  directory of the Github repository [51].
The  directory of the same Github repository [51] provides the  script for cycling through all different classes of  test problems used in this paper.
The constructed script can be handy for reproducing the results presented here and comparing and evaluating newly developed algorithms.

§.§ Investigation of different partitioning strategies

First, we compare the performance of new -type algorithms by stressing the used partitioning strategy.
<Ref> summarizes comparative results using all twelve -type variations on the whole set of $96$  test problems.
In <Ref>, each column corresponds to a different partitioning method.
Since each partitioning method was run on the $96$ problems using $3$ different selection methods (rows of <Ref>), it follows that each partitioning method was involved in solving $3 \times 96 = 288$ problems.
The best results are marked in bold.
In total, all three 1-DBDP partitioning-strategy-based algorithms failed to solve ($28/288$) test cases.
In contrast, the second and third best partitioning technique (N-DTC, 1-DTC) based -type approaches did not solve ($29/288$) and ($36/288$) cases accordingly.
Not surprisingly, a higher number of solved test problems leads to a better overall average performance of 1-DBDP partitioning strategy-based -type approaches.
In total, the 1-DBDP partitioning technique-based -type methods required approximately $7 \%$ and $18 \%$ fever function evaluations than the second and third best partitioning scheme (N-DTC and 1-DTC) based -type algorithms accordingly.

However, the situation is different when comparing algorithms based on the median number of function evaluations.
The diagonal trisection strategy (1-DTDV) based -type algorithms are more efficient than competitors.
The median value for all $288$ test problems solved with the 1-DTDV partitioning scheme is approximately $23 \%$ and $47 \%$ better than the second and third best 1-DTC and 1-DBDP approaches accordingly.
Therefore, 1-DTDV partitioning strategy-based -type algorithms can solve at least half of these test problems with the best performance.
Furthermore, most of the time, the 1-DTDV partitioning strategy-based algorithms delivered the best average results in solving low-dimensional test problems ($n \leq 4$).
In total, on $153$ low-dimensional ($n \leq 4$) test cases, the 1-DTDV partitioning strategy-based algorithms required approximately $22 \%$ fever function evaluations than the second-best partition strategy (1-DTC) based variants.
To sum up, the 1-DTDV partitioning strategy performs the best combined with a two-step-based selection scheme (GL).
The 1-DTDV-GL algorithm in general significantly outperformed the other two variations based on IA and IO selection schemes.

The 1-DBDP partitioning strategy-based variation combined with two of the selection schemes (GL and IA) delivered the best average results on higher dimension ($n > 4$) test problems.
In total, the 1-DBDP partitioning strategy-based algorithms required approximately $16 \%$ fever function evaluations than the second-best partition strategy (N-DTC) based variants.

The number of function evaluations of twelve -type variants on  test problems
Criteria / Algorithms     $\#$ of cases     2cN-DTC-IA     2c1-DTC-IA     2c1-DBDP-IA     2c1-DTDV-IA

$\#$ of failed problems     $96$        $13$ 		       $13$ 		       $\mathbf{11}$ 		       $18$

Average results			    $96$        $172,805$        $160,691$ 	       $\mathbf{146,887}$ 	       $202,694$

Average ($n \leq 4$) 	    $51$        $25,968$ 	       $23,638$ 	       $45,643$ 			       $\mathbf{9,785}$

Average ($n > 4$)		    $45$        $339,791$        $316,541$ 	       $\mathbf{262,640}$ 	       $421,539$

Average (convex) 		    $30$        $149,711$        $126,030$ 	       $\mathbf{109,374}$ 	       $153,594$

Average (non-convex) 	    $66$        $183,302$        $176,446$ 	       $\mathbf{163,939}$ 	       $225,012$

Average (uni-modal)		    $15$        $108,068$        $78,226$ 	       $\mathbf{73,957}$ 	       $111,805$

Average (multi-modal)	    $81$        $187,744$        $179,722$ 	       $\mathbf{163,717}$ 	       $223,668$

Median results			    $96$        $7,608$ 	       $\mathbf{1,287}$        $2,108$        $1,586$

Criteria / Algorithms     $\#$ of cases     2cN-DTC-IO     2c1-DTC-IO     2c1-DBDP-IO     2c1-DTDV-IO

$\#$ of failed problems	    $96$        $\mathbf{12}$ 		       $18$ 		       $\mathbf{12}$ 		       $21$

Average results			    $96$        $\mathbf{142,277}$ 	       $211,463$ 	       $146,133$ 			       $227,455$

Average ($n \leq 4$) 	    $51$        $43,832$ 				       $42,633$ 	       $\mathbf{41,602}$  	       $41,990$

Average ($n > 4$)		    $45$        $\mathbf{254,819}$ 	       $403,749$ 	       $265,522$ 			       $438,574$

Average (convex) 		    $30$        $111,817$ 			       $170,675$ 	       $\mathbf{80,490}$ 	       $171,868$

Average (non-convex) 	    $66$        $\mathbf{156,122}$ 	       $230,004$ 	       $175,971$ 			       $252,722$

Average (uni-modal)		    $15$        $60,100$ 				       $\mathbf{57,360}$        $62,016$ 		       $111,547$

Average (multi-modal)	    $81$        $\mathbf{161,240}$ 	       $247,026$ 	       $165,545$ 			       $254,203$

Median results			    $96$        $\mathbf{771}$ 		       $1,198$ 		       $953$ 				       $847$

Criteria / Algorithms     $\#$ of cases     2cN-DTC-GL     2c1-DTC-GL     2c1-DBDP-GL     2c1-DTDV-GL

$\#$ of failed problems     $96$        $\mathbf{4}$	       $5$ 				       $5$ 					       $5$

Average results			    $96$        $71,488$ 	       $\mathbf{62,475}$	       $65,442$ 			       $71,319$

Average ($n \leq 4$) 	    $51$        $9,675$ 	       $7,073$ 				       $41,300$ 			       $\mathbf{5,772}$

Average ($n > 4$)		    $45$        $141,753$        $125,417$ 			       $\mathbf{93,714}$ 	       $145,733$

Average (convex) 		    $30$        $55,320$ 	       $45,520$ 			       $42,326$ 			       $\mathbf{8,950}$

Average (non-convex) 	    $66$        $78,837$ 	       $\mathbf{70,182}$  	       $75,949$ 			       $99,669$

Average (uni-modal)		    $15$        $28,478$ 	       $\mathbf{12,624}$ 	       $23,300$ 			       $25,796$

Average (multi-modal)	    $81$        $81,183$ 	       $\mathbf{73,979}$  	       $75,398$ 			       $81,825$

Median results			    $96$        $1,848$ 	       $960$ 				       $2,042$ 				       $\mathbf{775}$

§.§.§ Investigating the impact of the solution on the boundary

In <Ref>, we stressed that the diagonal trisection strategy (1-DTDV) is especially appealing on problems where the solution lies on the boundary of the feasible region.
We have carried out an additional experimental study presented here to investigate this.
Note that the selection strategy was fixed (IO), and only the influence on the performance of four partitioning strategies was investigated.

Out of the 46 box-constrained unique (excluding dimensionality variations) test problems from , only the Deb02 problem has a solution on the boundary.
More precisely, the solution lies on the feasible region's vertex, making this situation particularly favorable to the 1-DTDV strategy.

Experimental results using four -type variations on the Deb02 test problem (with varying dimensionality $n$) are given in the upper part of <Ref>.
Since the solution is at the vertex, independently of the dimension, the 1-DTDV-IO algorithm found the solution in the initialization step and took only two objective function evaluations.
The other three -type algorithms required significantly more function evaluations until the stopping condition was satisfied.

In order to carry out a more detailed investigation, test problems with solution coordinates lying on the boundary were artificially constructed.
For this purpose, ten variations of $10$-dimensional Levy and five variations of $5$-dimensional D. Price test problems with perturbed feasible regions were created.

Let us first consider the case of the Levy function.
The original feasible region is $D=[-5, 5]^{10}$ and the solution point $\mathbf{x}^* = (1,1,\dots,1)$.
Thus none of the solution coordinates are on the boundary of the permissible area.
On the original Levy problem, the 1-DTDV-IO algorithm performed significantly worse than any of the other three tested -type counterparts (see the first row in the middle part of <Ref>).

However, the situation changes completely when Levy variations with the perturbed feasible region are considered.
We artiﬁcially reconstructed the original domain so that an increasing number of solution coordinates are located on the boundary—the column “Feasible region” in <Ref> specifies the modified feasible region.
For example, for the first Levy variation (Levy1), the modified feasible region coincides with the original one (i.e., $D^m_1 = D$) apart from the coordinate $x_1$, whose new domain is $x_1 \in [-5, 1]$ (original was $x_1 \in [-5, 5]$).
Therefore, for the Levy1 problem, one of its solution coordinates $(x_1)$ is on the boundary of the modified feasible region.
The other nine Levy function variations are again obtained by substituting only one but the following coordinate compared to the previous Levy variation, as shown in <Ref>.
The $\nu$ value (the third column in <Ref>) indicates the number of solution coordinates projected onto the boundary.
From the obtained results presented in <Ref>, observe that the more coordinates of the solution are located on the boundary, the fewer objective function evaluations the 1-DTDV-IO algorithm needs to ﬁnd the solution.
When $\nu \geq 8$ (i.e., at least eight out of 10 coordinates lie on the boundary), the 1-DTDV-IO algorithm outperformed other approaches.
However, the situation is the opposite of the other three partitioning schemes based on -type algorithms.
For almost all cases, they required more function evaluations when $\nu$ increases.

In the last investigation, five variations of D. Price test function (original $D = [-10, 10]^5$ and the solution point lying close to the center-point of the domain) were considered.
For D. Price, we perturbed the feasible region by the same strategy as for the Levy test problem.
Same as before, when most of the solution coordinates are located on the boundaries of the domain ($\nu \geq 4$), the 1-DTDV-IO algorithm is the most efficient.

However, unlike for the Levy function, the presence of the solution coordinates on the boundary did not worsen the other -type algorithms but rather improved.
These results show that the performance of center-based partitioning techniques will not necessarily worsen when at least part of the solution coordinates are on the boundary.

The number of function evaluations required for four different -type algorithms to find optimal solution lying on the boundary

Label     $n$     $\nu$     1lFeasible region     N-DTC-IO     1-DTC-IO     1-DBDP-IO     1-DTDV-IO

Deb02     $2$     $2$     $D =[0, 1]^n$      $77$     $75$     $100$     $2$

Deb02     $4$     $4$     $D =[0, 1]^n$      $199$     $145$     $220$     $2$

Deb02     $8$     $8$     $D =[0, 1]^n$      $653$     $329$     $494$     $2$

Deb02     $16$     $16$     $D =[0, 1]^n$      $3,827$     $1,279$     $2,368$     $2$

Levy     $10$     $0$     $D = [-5, 5]^n$      $2,589$     $919$     $1,496$     $141,999$

Levy$1$     $10$     $1$     $D^{\rm m}_1 = D$ and $x_1 \in [-5, 1]$      $2,847$     $973$     $1,326$     $24,439$

Levy$2$     $10$     $2$     $D^{\rm m}_2 = D^{\rm m}_1$ and $x_2 \in [1, 5]$       $3,221$     $1,033$     $1,386$     $16,291$

Levy$3$     $10$     $3$     $D^{\rm m}_3 = D^{\rm m}_2$ and $x_3 \in [-10, 1]$     $3,447$     $1,079$     $2,002$     $13,625$

Levy$4$     $10$     $4$     $D^{\rm m}_4 = D^{\rm m}_3$ and $x_4 \in [1, 10]$      $3,919$     $1,119$     $2,048$     $14,166$

Levy$5$     $10$     $5$     $D^{\rm m}_5 = D^{\rm m}_4$ and $x_5 \in [-2, 1]$      $4,091$     $1,195$     $2,116$     $10,927$

Levy$6$     $10$     $6$     $D^{\rm m}_6 = D^{\rm m}_5$ and $x_6 \in [1, 4]$       $4,483$     $1,287$     $2,316$     $5,416$

Levy$7$     $10$     $7$     $D^{\rm m}_7 = D^{\rm m}_6$ and $x_7 \in [-7, 1]$      $5,215$     $2,193$     $2,484$     $3,069$

Levy$8$     $10$     $8$     $D^{\rm m}_8 = D^{\rm m}_7$ and $x_8 \in [1, 15]$      $5,487$     $2,579$     $3,174$     $2,494$

Levy$9$     $10$     $9$     $D^{\rm m}_9 = D^{\rm m}_8$ and $x_9 \in [-13, 1]$     $6,299$     $6,581$     $3,518$     $547$

Levy$10$     $10$     $10$     $D^{\rm m}_{10} = D^{\rm m}_{9}$ and $x_{10} \in [1,10]$     $6,487$     $2,487$     $3,572$     $551$

D. Price     $5$     $0$     $D = [-10, 10]^n$      $22,465$     $20,791$     $4,060$     $134,011$

D. Price$1$     $5$     $1$     $D^{\rm m}_1 = D$ and $x_1 \in [-19, 1]$       $18,245$     $18,707$     $2,930$     $16,089$

D. Price$2$     $5$     $2$     $D^{\rm m}_2 = D^{\rm m}_1$ and $x_2 \in [0.7071, 21]$       $4,975$     $1,455$     $1,322$     $3,434$

D. Price$3$     $5$     $3$     $D^{\rm m}_3 = D^{\rm m}_2$ and $x_3 \in [-19, 0.5946]$     $7,709$     $3,845$     $1,610$     $2,759$

D. Price$4$     $5$     $4$     $D^{\rm m}_4 = D^{\rm m}_3$ and $x_4 \in [0.5452, 21]$      $3,989$     $1,315$     $2,280$     $728$

D. Price$5$     $5$     $5$     $D^{\rm m}_5 = D^{\rm m}_4$ and $x_5 \in [-19, 0.5221]$      $3,247$     $1,443$     $2,396$     $565$

8l$\nu$ – the number of solution coordinates lying on the boundary

§.§.§ Investigating the impact of the domain perturbation

By investigating the impact of different partitioning strategies, we observed several situations where one method (or partitioning scheme) dominates the others significantly.
However, sometimes one method may be lucky because the partitioning approach in the initial steps naturally samples near the solution.
In such situations, the location of the solution may favor one partitioning scheme over another.
In this section, we explore whether such dominance is robust to slight perturbations of the domain.

Initially, we identified test problems for which a particular partitioning scheme (regardless of the selection strategy) had a clear dominance, possibly due to the conveniently defined variable bounds.
Out of the $46$  unique box-constrained test problems, the dominance of a particular partitioning scheme was identified for eight of them.
We made domain perturbations for all eight problems keeping the same optimal solution.
First, if any partitioning scheme-based -type algorithm can find the solution in the initialization step, the original domain $(D)$ has been shifted by $22.5 \%$ to the right side.
In some cases, we have made further perturbations that none of the partitioning schemes would sample on initial iterations close to the solution (the column “Feasible region”  in <Ref> specifies the original and perturbed domains).

The obtained experimental results revealing the impact of the domain perturbation of twelve -type variants on eight selected original and perturbed test problems with varying dimensionality are given in <Ref>.

None of the partitioning schemes proved to be robust.
Perturbation of the bounds may significantly reduce the dominance of a particular partitioning scheme.
Quite often, the previously dominant approach may not solve the perturbed problem within the given budget of function evaluations at all.
For example, the 1-DTC partitioning scheme-based -type algorithms undoubtedly dominate original Rastrigin and Griewank test problems.
However, for perturbed variations of Rastrigin and Griewank, the same 1-DTC partitioning scheme-based -type algorithms could not be able to find a solution for most of these cases.

Another obvious example is the Rosenbrock test problem case.
The 1-DTDV partitioning scheme-based -type algorithms are most efficient when the problem is considered in the original domain $D$.
However, after the $D$'s perturbation, the 1-DTDV partitioning scheme proved to be very inefficient.
Also, in some cases, the bounds' perturbation helped other algorithms perform significantly better than on the original domain.
Examples of such problems are Styblinski-Tang, Easom, and Power Sum.
Furthermore, only for the Schwefel test problem, the same two partitioning schemes (1-DBDP and 1-DTDV) based -type algorithms remained the most efficient in the original and perturbed domains.

Experimental results of twelve -type variants on 8 selected original and perturbed test problems with varying dimensionality

1*Label     1*$n$     1*Feasible region     N-DTC-IA     1-DTC-IA     1-DBDP-IA     1-DTDV-IA     N-DTC-IO     1-DTC-IO     1-DBDP-IO     1-DTDV-IO     N-DTC-GL     1-DTC-GL     1-DBDP-GL     1-DTDV-GL

Alpine     $5$     $[0, 10]^n$     $61,485$     $10,343$     $\mathbf{714}$      $>10^6$      $2,033$     $1,231$     $\mathbf{168}$     $460,445$      $1,287$     $685$     $\mathbf{320}$     $27,074$

$10$     $[0, 10]^n$      $>10^6$      $>10^6$     $\mathbf{173,912}$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$     $61,209$     $\mathbf{4,063}$     $7,646$     $173,948$

Perturbed Alpine     $5$     $[\sqrt[i]{2}, 8+\sqrt[i]{2}]^n$     $61,485$       $10,343$      $\mathbf{2,678}$     $10,941$        $2,209$     $\mathbf{1,403}$     $5,790$     $3,920$     $1,479$     $\mathbf{853}$     $3,462$     $19,417$

$10$     $[\sqrt[i]{2}, 8+\sqrt[i]{2}]^n$      $>10^6$      $>10^6$     $\mathbf{218,170}$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$     $31,967$     $\mathbf{7,245}$     $15,500$      $>10^6$

Griewank     $5$      $[-330, 870]^n$     $719,985$     $69,979$      $>10^6$     $\mathbf{47,581}$      $>10^6$      $>10^6$      $>10^6$      $>10^6$     $524,765$     $457,207$     $\mathbf{14,706}$      $>10^6$

$10$     $[-330, 870]^n$      $>10^6$     $\mathbf{8,799}$     $20,534$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$     $\mathbf{14,593}$     $204,940$      $>10^6$

Perturbed Griewank     $5$      $\left[-\sqrt{600i}, \dfrac{600}{\sqrt{i}}\right]^n$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$     $187,811$     $\mathbf{102,961}$     $175,806$     $353,028$

$10$     $\left[-\sqrt{600i}, \dfrac{600}{\sqrt{i}} \right]^n$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$

Styblinski-Tang     $5$      $[-5, 5]^n$     $4,941$      $627$       $\mathbf{164}$     $243,882$     $539$        $>10^6$     $\mathbf{78}$      $7,077$     $1,779$      $\mathbf{865}$       $192$     $682$

$10$     $[-5, 5]^n$     $68,025$     $2,631$     $\mathbf{714}$      $>10^6$       $9,785$      $>10^6$     $\mathbf{180}$      $>10^6$     $11,347$     $3,237$     $\mathbf{784}$     $5,248$

Perturbed Styblinski-Tang     $5$      $[-5, 5 + \sqrt[i]{3}]^n$     $3,919$     $\mathbf{533}$     $1,056$     $66,810$     $395$     $\mathbf{273}$     $278$     $4,098$     $1,659$     $\mathbf{841}$     $1,654$     $36,655$

$10$     $[-5, 5 + \sqrt[i]{3}]^n$     $68,025$     $\mathbf{2,151}$     $6,736$      $>10^6$     $2,917$     $\mathbf{829}$     $1,368$      $>10^6$     $13,431$     $\mathbf{3,447}$     $11,386$      $>10^6$

Easom     $2$     $[-100, 100]^n$     $433,031$       $429,743$     $\mathbf{444}$     $20,316$     $7,581$     $6,619$     $\mathbf{322}$     $6,651$     $451$     $\mathbf{321}$     $544$     $348$

Perturbed Easom     $2$     $\left[ \dfrac{-100}{i+1}, 100i \right]^n$     $214,331$     $429,743$     $\mathbf{71,392}$     $177,258$     $\mathbf{3,689}$     $6,659$     $18,462$     $10,078$     $475$     $393$     $924$     $\mathbf{376}$

Power Sum     $4$      $[0.9, 4.9]^n$      $>10^6$      $>10^6$     $\mathbf{13,828}$      $>10^6$     $321,595$     $144,385$     $\mathbf{4,790}$      $>10^6$     $69,327$     $77,353$     $\mathbf{14,214}$     $37,012$

Perturbed Power Sum     $4$      $[1, 5 + \sqrt[i]{2}]^n$     $502,981$     $176,843$     $78,746$     $\mathbf{59,390}$     $67,959$     $25,453$     $17,930$     $\mathbf{12,219}$     $152,083$     $70,745$     $\mathbf{12,494}$     $40,753$

Rastrigin     $5$      $[-2.75, 7.25]^n$     $8,703$       $\mathbf{1,487}$     $314,712$ 			        $>10^6$     $597$       $\mathbf{453}$       $38,714$                  $112,597$                 $2,721$     $\mathbf{1,895}$     $19,642$     $7,345$

$10$     $[-2.75, 7.25]^n$     $143,755$     $\mathbf{7,215}$      $>10^6$      $>10^6$     $4,299$     $\mathbf{1,551}$      $>10^6$      $>10^6$     $22,971$     $\mathbf{8,105}$      $>10^6$     $140,756$

Perturbed Rastrigin     $5$      $[-5\sqrt[i]{2}, 7+\sqrt[i]{2}]^n$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$     $\mathbf{567,269}$     $694,812$      $>10^6$     $73,727$     $24,119$     $\mathbf{16,440}$     $90,134$

$10$     $[-5\sqrt[i]{2}, 7+\sqrt[i]{2}]^n$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$     $\mathbf{661,971}$      $>10^6$      $>10^6$      $>10^6$

Rosenbrock     $5$      $[-5, 10]^n$      $73,485$      $26,325$     $3,208$     $\mathbf{1,471}$      $15,577$     $1,889$     $1,494$     $\mathbf{916}$     $26,891$      $15,695$      $5,110$      $\mathbf{1,568}$

$10$     $[-5, 10]^n$     $297,755$      $>10^6$      $13,366$     $\mathbf{4,541}$     $71,021$      $>10^6$     $4,590$     $\mathbf{2,091}$      $104,643$     $171,019$     $22,194$     $\mathbf{5,759}$

Perturbed Rosenbrock     $5$      $\left[-\dfrac{5}{\sqrt{i}}, 10\sqrt{i}\right]^n$     $434,985$     $385,979$     $\mathbf{291,612}$      $>10^6$     $55,693$     $\mathbf{21,363}$     $101,508$      $>10^6$     $27,763$     $\mathbf{7,795}$     $33,056$     $16,971$

$10$     $\left[-\dfrac{5}{\sqrt{i}}, 10\sqrt{i}\right]^n$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$     $383,081$     $\mathbf{185,325}$     $316,392$     $432,903$

Schwefel      $5$      $[-500, 500]^n$      $>10^6$     $368,479	$     $\mathbf{7,566}$      $>10^6$     $74,989	$     $16,767$     $\mathbf{1,070}$     $9,561$     $768,549	$     $49,247$     $\mathbf{4,842}$     $109,746$

$10$     $[-500, 500]^n$      $>10^6$      $>10^6$     $\mathbf{817,512}$      $>10^6$      $>10^6$      $>10^6$     $\mathbf{57,736}$      $>10^6$      $>10^6$      $>10^6$     $\mathbf{33,522}$      $>10^6$

Perturbed Schwefel     $5$      $\left[-500 + \dfrac{100}{\sqrt{i}}, 500  - \dfrac{40}{\sqrt{i}} \right]^n$      $>10^6$     $458,979$     $19,972$     $\mathbf{2,135}$     $80,295$     $35,091$     $84,096$     $\mathbf{33,622}$     $336,581$     $65,329$     $9,548$     $\mathbf{1,580}$

$10$     $\left[-500 + \dfrac{100}{\sqrt{i}}, 500  - \dfrac{40}{\sqrt{i}} \right]^n$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$      $>10^6$     $99,824$     $336,983$

7l$i = 1,...,n$ – indexes used for variable bounds

§.§ Investigation of different selection schemes

Here, the efficiency of new -type algorithms is investigated based on the selection scheme.
In <Ref>, three row parts corresponds to a different selection approach.
Since each selection strategy was run on the $96$ problems using $4$ different partitioning methods (columns of <Ref>), it follows that each selection approach was involved in solving $4 \times 96 = 384$ test problems.
We note that algorithms incorporating a two-step-based Pareto selection scheme (GL) combined with any partitioning strategy, on average, deliver the best results.
All algorithmic variants based on the GL selection scheme did not solve ($19/384$).
In contrast, the IO and IA selection schemes based algorithms failed to solve ($63/384$) and ($55/384$) cases accordingly.
This leads to a much better average performance of -type algorithms based on the GL selection scheme.
In total, GL selection scheme-based algorithms required approximately $60\%$ and $62\%$ fever function evaluations compared with the IO and IA counterparts.
The GL selection scheme's most significant advantage can be seen in solving higher-dimensional $(n > 4)$ test problems.
In total, GL selection scheme-based algorithms solving ($n > 4$) test instances required approximately $72\%$ fever function evaluations compared with the IO or IA selection scheme-based counterparts.

The IO selection scheme seems the most suitable for simpler optimization problems (low dimensional, uni-modal, and problems with a few minima).
Of 63 failed problems using the IO selection scheme, 43 were extremely hard, i.e., multi-modal, sharply peaked, and multi-variable (e.g., $n \ge 10$).
The GL selection strategy-based variants usually select more regions to subdivide.
Therefore, they suffer for these more straightforward optimization problems.
However, the GL scheme ensured, that on average, all -type variants converged in significantly fewer function evaluations on complex multi-modal test problems.

legend pos=north west,

title  = Operational characteristics,
xlabel = Function evaluations,
ytick distance=0.1,
xtick distance=10,
ylabel = Proportion of solved problems,
ylabel style=yshift=-0.5em,
legend style=font=,xshift=-0.5em,
legend cell align=left,
legend columns=1,
every axis plot/.append style=very thick,

[mark=*,black,mark options=scale=1.5, fill=princetonorange, only marks,line width=0.75pt] coordinates (0.1,0.1) ;

[mark=square*,black,mark options=scale=1.5, fill=yellow, only marks,line width=0.75pt] coordinates (0.1,0.1) ;

[mark=diamond*,black,mark options=scale=1.5, fill=sienna, only marks,line width=0.75pt] coordinates (0.1,0.1) ;

[mark=triangle*,black,mark options=scale=1.5, fill=psychedelicpurple, only marks,line width=0.75pt] coordinates (0.1,0.1) ;

[draw,fill=white] at (rel axis cs: 0.85,0.14) [l]
Partitioning  schemes

<ref> N-DTC

<ref> 1-DTC

<ref> 1-DBDP

<ref> 1-DTDV;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.06 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=DDA] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.07 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=DRA] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.08 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=BIA] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.09 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=ADA] data/Overallass.txt;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.1 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=DDO] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.11 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=DRO] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.12 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=BIO] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.13 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=ADO] data/Overallass.txt;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.14 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=DDG] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.15 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=DRG] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.16 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=BIG] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.17 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=ADG] data/Overallass.txt;

[blue,line width=0.75pt] coordinates (0.1,0.1) ;

[sandstorm,line width=0.75pt,densely dashed] coordinates (0.1,0.1) ;

[onyx,line width=0.75pt,densely dotted] coordinates (0.1,0.1) ;

[draw,fill=white] at (rel axis cs: 0.2,0.88) [l]
POH selection schemes

<ref> Improved Original (IO)

<ref> Improved Aggressive (IA)

<ref> Global-Local (GL) Pareto;

Operational characteristics for all twelve -type algorithmic variations on  test problems

legend pos=north west,

title  = Operational characteristics,
xlabel = Function evaluations,
ytick distance=0.1,
xtick distance=10,
ylabel = Proportion of solved problems,
ylabel style=yshift=-0.5em,
legend style=font=,xshift=-0.5em,
legend cell align=left,
legend columns=1,
every axis plot/.append style=very thick,

[draw,fill=white] at (rel axis cs: 0.85,0.14) [l]
Partitioning  schemes

<ref> N-DTC

<ref> 1-DTC

<ref> 1-DBDP

<ref> 1-DTDV;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.06 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=DDA] data/Overallassa.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.07 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=DRA] data/Overallassa.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.08 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=BIA] data/Overallassa.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.09 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=ADA] data/Overallassa.txt;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.1 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=DDO] data/Overallassa.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.11 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=DRO] data/Overallassa.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.12 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=BIO] data/Overallassa.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.13 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=ADO] data/Overallassa.txt;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.14 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=DDG] data/Overallassa.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.15 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=DRG] data/Overallassa.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.16 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=BIG] data/Overallassa.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.17 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=ADG] data/Overallassa.txt;

[draw,fill=white] at (rel axis cs: 0.2,0.88) [l]
POH selection schemes

<ref> Improved Original (IO)

<ref> Improved Aggressive (IA)

<ref> Global-Local (GL) Pareto;

Operational characteristics for all twelve -type algorithmic variations solving higher-dimensional ($n > 4$) multi-modal  test problems

legend pos=north west,

title  = Operational characteristics,
xlabel = Function evaluations,
ytick distance=0.1,
xtick distance=10,
ylabel = Proportion of solved problems,
ylabel style=yshift=-0.5em,
legend style=font=,xshift=-0.5em,
legend cell align=left,
legend columns=1,
every axis plot/.append style=very thick,

[draw,fill=white] at (rel axis cs: 0.85,0.14) [l]
Partitioning  schemes

<ref> N-DTC

<ref> 1-DTC

<ref> 1-DBDP

<ref> 1-DTDV;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.06 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=DDA] data/Overallassb.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.07 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=DRA] data/Overallassb.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.08 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=BIA] data/Overallassb.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.09 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=ADA] data/Overallassb.txt;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.1 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=DDO] data/Overallassb.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.11 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=DRO] data/Overallassb.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.12 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=BIO] data/Overallassb.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.13 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=ADO] data/Overallassb.txt;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.14 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=DDG] data/Overallassb.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.15 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=DRG] data/Overallassb.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.16 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=BIG] data/Overallassb.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.17 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=ADG] data/Overallassb.txt;

[draw,fill=white] at (rel axis cs: 0.2,0.88) [l]
POH selection schemes

<ref> Improved Original (IO)

<ref> Improved Aggressive (IA)

<ref> Global-Local (GL) Pareto;

Operational characteristics for all twelve -type algorithmic variations solving uni-modal and convex   test problems

Additionally, the operational characteristics [14, 56] reported in <Ref> show the behavior of all twelve algorithms on different subsets of  box-constrained test problems.
Operational characteristics provide the proportion of problems that can be solved within a given budget of function evaluations.

<Ref>, drawn using all $96$ box-constrained problems from , clearly shows that IO selection scheme-based -type algorithms (1-DTDV-IO and N-DTC-IO) dominate for simpler problems.
They solved almost half of the 96 test problems within a small budget of objective function evaluations.
However, as the number of function evaluations increases (as more complex problems are considered), the GL scheme-based algorithms are most efficient.

Operational characteristics in <Ref> show the behavior of all twelve algorithms on $35$ higher-dimensionality ($n > 4$) multi-modal test problems.
Once again, when a given budget of function evaluations is low (M$_{\rm max} \leq 500$), all IO selection scheme-based variations perform better.
Unfortunately, with such a small function evaluation budget, the algorithms will only solve approximately $15 \%$ of all the test problems.
When the maximal budget of function evaluations increased (M$_{\rm max} \leq 4,000$), only one of the IO selection scheme combinations (N-DTC-IO) maintained the highest efficiency and solved approximately $50 \%$ of all the test cases.
Finally, when the function evaluation budget is higher (M$_{\rm max} \geq 4,000$), GL selection scheme-based variations (1-DTC-GL and 1-DBDP-GL) have the highest efficiency.

Similar tendencies regarding the best-performing selection strategies can be seen in <Ref>.
Here, the operational characteristics illustrate the behavior of algorithms solving simplest uni-modal and convex optimization test problems.
Among the partitioning strategies, the 1-DTDV scheme looks the most efficient here.

§ EXPERIMENTAL INVESTIGATION USING GKLS-TYPE TEST PROBLEMS

Additionally, we compare the performance of all twelve -type variants on GKLS-type test problems [13].
GKLS-generator allows generating three types (non-differentiable, continuously differentiable, and twice continuously differentiable) of multi-dimensional and multi-extremal optimization test functions with a priori known local and global minima.
The complexity of generated problems is established by setting different values for user-determined parameters: problem dimension $n$, the number of local minima $m$, global minimum value $f^*$, distance $d$ from the global minimizer to the paraboloid vertex, and radius $r$ of the attraction region of the global minimizer.

We use eight different complexity classes (see <Ref>).
The dimensionality ($n$) and other parameters are set as in [34, 35].
Each class consisted of $100$ test instances.
For each dimension $n$, two test classes were considered: the “simple” class and the “hard” one.
For three- and four-dimensional classes the difficulty is increased by enlarging the distance $d$ from the global minimizer $(\mathbf{x}^*)$ to the paraboloid vertex.
For two and five-dimensional classes this is achieved by decreasing the radius $r$ of the attraction region of the global minimizer.

Description of GKLS-type test classes used in numerical experiments

Class     Difficulty     $\Delta$     $n$     $f^*$     $d$     $r$     $m$

$1$     simple 	    $10^{-4}$     $2$     $-1$     $0.90$     $0.20$     $10$

$2$     hard 		    $10^{-4}$     $2$     $-1$     $0.90$     $0.10$     $10$

$3$     simple 	    $10^{-6}$     $3$     $-1$     $0.66$     $0.20$     $10$

$4$     hard 		    $10^{-6}$     $3$     $-1$     $0.90$     $0.20$     $10$

$5$     simple 	    $10^{-6}$     $4$     $-1$     $0.66$     $0.20$     $10$

$6$     hard 		    $10^{-6}$     $4$     $-1$     $0.90$     $0.20$     $10$

$7$     simple 	    $10^{-7}$     $5$     $-1$     $0.66$     $0.30$     $10$

$8$     hard 		    $10^{-7}$     $5$     $-1$     $0.66$     $0.20$     $10$

The same stopping rule is adopted in these experiments as in [34, 35].
The global minimizer $\mathbf{x}^* \in D$ is considered to be found when an algorithm generated a function evaluation point $\mathbf{x}^i \in D^i_k$ such that:

\begin{equation}
\label{eq:pes}
\arrowvert x^i_j - x^*_j \arrowvert \leq \sqrt[n]{\Delta}(b_j - a_j), \hspace{1cm} 1 \leq j \leq n,
\end{equation}

where $0 \leq \Delta \leq 1$ is an accuracy coefficient [45](see <Ref> for $\Delta$ parameter values).
In other words, we stop the search when the algorithm has produced a point very close to the known optimum.
In each run, we used the same limit of function evaluations equal to $10^6$.
Note that the stopping rule (<ref>) does not require algorithms to find a solution with high accuracy.

Therefore, the Pareto selection enhancing the local search (see <Ref>) was disabled.

The experimental results are summarized in <Ref>.
The notation “$>10^6(j)$” indicates that after the maximal number of function evaluations $10^6$, the algorithm under consideration was not able to solve $j$ problems in total.
First, contrary to the previous tendencies, the best results are obtained when -type variants include an improved original selection scheme (IO).
In numerical experiments described in <Ref>, -type algorithms with integrated IO selection schemes had almost the worst efficiencies.
However, all four -type variants based on the IO selection scheme are promising for GKLS-type test problems.

The least attractive is an improved aggressive selection scheme (IA).
All failed $40$ cases appeared when this selection scheme was combined with three different partitioning strategies (except 1-DBDP).

The best average results (see the upper part of <Ref>) are achieved using 1-DTC-IO (for seven different classes) and 1-DBDP-GL (for one class).
The average number using the 1-DTC-IO algorithm is $8,021$, while the second (1-DBDP-IO) and third-best (1-DTDV-IO) algorithms deliver approximately $19 \%$ ($9,571$) and $47 \%$ ($15,231$) worse overall performances.
Interestingly, the 1-DBDP-GL algorithm, which produced the best overall result in <Ref>, ranks only fifth as delivered $67 \%$ ($24,746$) worse average results than 1-DTC-IO.

The lowest aggregated median number (the middle part of <Ref>) for all eight classes again is obtained using the same 1-DTC-IO algorithm ($1,427$).
Therefore, the 1-DTC-IO algorithm can solve at least half of GKLS-type problems with the best performance.
In contrast, the second (1-DBDP-GL) and third (1-DBDP-IO) best algorithms delivered approximately $3.71 \%$ ($1,482$) and $3.84 \%$ ($1,484$) worse overall median values.

In the bottom part of <Ref>, the maximal number of function evaluations required to solve test problems within a particular class is reported.
The previously emphasized algorithmic variation 1-DTC-IO is the best for four out of eight classes.
However, solving two of the most complex (“hard”) classes (No = $6$ and $8$) 1-DTDV-IO algorithm seems the most promising.

Comparison of twelve -type variants on eight classes of GKLS-type problems
Class     N-DTC-IA     1-DTC-IA     1-DBDP-IA     1-DTDV-IA     N-DTC-IO     1-DTC-IO     1-DBDP-IO     1-DTDV-IO     N-DTC-GL     1-DTC-GL     1-DBDP-GL     1-DTDV-GL

13cAverage number of function evaluations

$1$     $510$          $289$          $257$         $1,148$       $198$         $\mathbf{149}$         $156$        $360$        $236$         $217$         $185$        $665$

$2$     $5,215$        $5,491$        $1,449$       $6,278$       $1,068$       $\mathbf{803}$         $863$        $1,458$      $2,332$       $3,130$       $1,245$      $3,454$

$3$     $4,069$        $1,747$        $1,252$       $9,870$       $1,019$       $\mathbf{673}$         $869$        $1,776$      $1,264$       $1,286$       $825$        $4,148$

$4$     $15,331$       $9,393$        $4,032$       $35,291$      $2,477$       $\mathbf{1,543}$       $1,832$      $4,539$      $5,125$       $4,427$       $2,640$      $14,943$

$5$     $36,586$       $20,911$       $13,179$      $91,161$      $7,843$       $\mathbf{4,591}$       $8,207$      $11,806$     $10,720$      $10,553$      $9,199$      $32,597$

$6$     $198,129$      $157,187$      $95,541$      $350,033$     $26,970$      $\mathbf{16,899}$      $23,905$     $34,020$     $77,715$      $68,348$      $57,867$     $117,684$

$7$     $21,811$       $17,769$       $4,956$       $67,634$      $6,216$       $4,419$     $3,974$      $11,156$     $12,262$     $10,645$      $\mathbf{3,472}$      $32,108$

$8$     $308,948$      $226,208$      $96,621$      $477,868$     $67,636$      $\mathbf{35,091}$      $36,768$     $55,625$     $120,118$     $99,362$      $58,278$     $183,881$

$1-8$     $73,825$     $54,874$       $27,160$      $129,910$     $14,178$      $\mathbf{8,021}$       $9,571$      $15,231$     $27,783$      $24,746$      $16,713$     $48,685$

13cMedian number of function evaluations

$1$     $308$          $207$          $204$         $878$         $119$         $122$     		     $\mathbf{111}$        $328$        $128$        $155$          $130$         $469$

$2$     $4,316$        $2,375$        $1,016$       $5,793$       $1,058$       $724$     		     $\mathbf{673}$        $1,364$      $1,979$      $2,097$        $855$         $3,272$

$3$     $1,267$        $949$          $755$         $7,813$       $\mathbf{387}$     $503$  	     $488$    	         $1,597$      $445$        $604$          $461$         $3,344$

$4$     $8,970$        $3,962$        $2,366$       $32,915$      $1,782$       $\mathbf{1,075}$     $1,189$  	         $4,230$      $2,463$      $2,992$        $1,399$       $13,753$

$5$     $15,523$       $9,063$        $5,851$       $78,151$      $4,874$       $\mathbf{2,872}$     $4,443$  	   	     $10,761$     $4,388$      $7,052$        $4,202$       $28,822$

$6$     $121,285$      $76,586$       $55,130$      $334,277$     $15,517$      $\mathbf{9,237}$     $15,628$ 	  	     $32,796$     $43,458$     $33,804$       $29,189$      $116,530$

$7$     $7,514$        $4,079$        $2,102$       $42,804$      $1,673$       $2,291$   		     $2,278$  		     $10,992$     $1,533$      $3,440$        $\mathbf{1,427}$       $29,635$

$8$     $203,711$      $128,408$      $53,291$      $429,811$     $43,400$      $24,327$  		     $\mathbf{19,967}$     $47,221$     $65,892$     $54,497$       $27,697$      $162,411$

$1-8$     $6,767$      $4,188$        $2,098$       $26,227$      $1,644$       $\mathbf{1,427}$     $1,487$  		     $4,599$      $2,117$      $3,178$      $1,482$      $13,235$

13cMaximal number of function evaluations

$1$     $4,777$        $1,955$        $1,178$       $4,811$         $1,153$       $\mathbf{655}$         $840$         $961$         $2,031$       $1,319$       $1,090$       $2,502$

$2$     $21,841$       $25,021$       $11,674$      $20,089$        $3,197$       $\mathbf{2,201}$       $4,374$       $3,964$       $8,431$       $11,041$      $8,836$       $10,269$

$3$     $31,291$       $13,233$       $8,196$       $34,607$        $6,625$       $\mathbf{3,273}$       $5,032$       $4,864$       $10,723$      $11,335$      $5,058$       $16,789$

$4$     $132,121$      $150,809$      $22,720$      $88,327$        $15,307$      $9,763$       $\mathbf{7,806}$       $10,236$      $48,371$      $45,721$      $14,064$      $37,514$

$5$     $212,339$      $131,783$      $116,136$     $280,015$       $39,129$      $\mathbf{18,853}$      $62,016$      $35,898$      $74,277$      $47,527$      $70,028$      $78,365$

$6$     $>10^6(4)$     $>10^6(4)$     $562,156$     $932,395$       $260,793$     $126,061$     $141,914$     $\mathbf{86,105}$      $907,497$     $662,983$     $345,082$     $280,069$

$7$     $266,007$      $220,647$      $77,998$      $317,351$       $110,237$     $33,691$      $\mathbf{27,380}$      $41,751$      $86,269$      $135,889$     $54,400$      $145,022$

$8$     $>10^6(8)$     $>10^6(6)$     $776,052$     $>10^6(18)$     $472,125$     $229,583$     $313,420$     $\mathbf{210,483}$     $960,573$     $700,615$     $436,072$     $718,803$

Additionally, we visualize the performance of all twelve -type variations on GKLS-type problems using the operational characteristics.
<Ref> shows the behavior on four “simple” GKLS classes, while <Ref> shows the “hard” ones.
For simple classes, IO and GL selection schemes seem the most promising.
Among algorithms, when a low budget of function evaluations is considered (M$_{\rm max} \leq 400$), the 1-DTC-IO algorithm is the most efficient.
However, when M$_{\rm max} > 400 $, the 1-DBDP-GL algorithmic combination outperforms all others.

Furthermore, the best performance on these simple classes is achieved regardless of the selection scheme used with the 1-DBDP  partitioning strategy.

Finally, for “hard” classes (see <Ref>) IO selection scheme seems the most favorable (especially for simpler problems), while GL is the second-best option.
However, when a higher maximal number of function evaluations is allowed, the performance of GL and IO selection scheme-based algorithms is quite similar.
Among the algorithms, 1-DBDP-IO and 1-DTC-IO are the two best-performing ones.

legend pos=north west,

title  = Operational characteristics,
xlabel = Function evaluations,
ytick distance=0.1,
xtick distance=10,
ylabel = Proportion of solved problems,
ylabel style=yshift=-0.5em,
legend style=font=,xshift=-0.5em,
legend cell align=left,
legend columns=1,
every axis plot/.append style=very thick,

[draw,fill=white] at (rel axis cs: 0.85,0.14) [l]
Partitioning  schemes

<ref> N-DTC

<ref> 1-DTC

<ref> 1-DBDP

<ref> 1-DTDV;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.06 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=DDA] data/Overallass1.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.07 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=DRA] data/Overallass1.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.08 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=BIA] data/Overallass1.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.09 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=ADA] data/Overallass1.txt;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.1 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=DDO] data/Overallass1.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.11 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=DRO] data/Overallass1.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.12 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=BIO] data/Overallass1.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.13 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=ADO] data/Overallass1.txt;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.14 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=DDG] data/Overallass1.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.15 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=DRG] data/Overallass1.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.16 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=BIG] data/Overallass1.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.17 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=ADG] data/Overallass1.txt;

[draw,fill=white] at (rel axis cs: 0.2,0.88) [l]
POH selection schemes

<ref> Improved Original (IO)

<ref> Improved Aggressive (IA)

<ref> Global-Local (GL) Pareto;

Operational characteristics for all twelve -type algorithmic variations on four “simple” GKLS-type classes

legend pos=north west,

title  = Operational characteristics,
xlabel = Function evaluations,
ytick distance=0.1,
xtick distance=10,
ylabel = Proportion of solved problems,
ylabel style=yshift=-0.5em,
legend style=font=,xshift=-0.5em,
legend cell align=left,
legend columns=1,
every axis plot/.append style=very thick,
[draw,fill=white] at (rel axis cs: 0.85,0.14) [l]
Partitioning  schemes

<ref> N-DTC

<ref> 1-DTC

<ref> 1-DBDP

<ref> 1-DTDV;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.06 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=DDA] data/Overallassw.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.07 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=DRA] data/Overallassw.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.08 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=BIA] data/Overallassw.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.09 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt,solid] ;,decorate,,sandstorm,line width=0.75pt,densely dashed] table[x=T,y=ADA] data/Overallassw.txt;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.1 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=DDO] data/Overallassw.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.11 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=DRO] data/Overallassw.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.12 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=BIO] data/Overallassw.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.13 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt] ;,decorate,,blue,line width=0.75pt] table[x=T,y=ADO] data/Overallassw.txt;

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.14 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=DDG] data/Overallassw.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.15 with [mark=square,draw=black,fill=yellow,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=DRG] data/Overallassw.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.16 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=BIG] data/Overallassw.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.17 with [regular 	polygon,regular polygon sides=3,draw=black,fill=psychedelicpurple,inner sep=1pt,solid] ;,decorate,,onyx,line width=0.75pt,densely dotted] table[x=T,y=ADG] data/Overallassw.txt;

[draw,fill=white] at (rel axis cs: 0.2,0.88) [l]
POH selection schemes

<ref> Improved Original (IO)

<ref> Improved Aggressive (IA)

<ref> Global-Local (GL) Pareto;

Operational characteristics for all twelve -type algorithmic variations on four “hard” GKLS-type classes

§ CONCLUSIONS AND FUTURE WORK

This paper presented an extensive experimental investigation of various candidate selection and partitioning techniques traditionally used in the -type algorithms.
Twelve -type algorithmic combinations were created by considering four well-known partitioning and three selection schemes.
In general, experimental results confirmed the well-known fact from “No free lunch theorems for optimization” [59] that no one particular optimization algorithm works best for every problem.

However, detailed experimental studies have helped identify particular -type algorithmic variations that work well in certain situations.
For example, our experimental findings in <Ref> revealed that what initially looks like a clear dominance case goes away with small domain perturbations.
This should remind us how dangerous it can be to generalize from limited test-function results.
Below, we emphasize when certain variations have performed best and make some recommendations based on that.

Investigation using  test problems showed that independently on the partitioning strategy, a two-step-based Pareto selection scheme (GL) ensures the best performance on more challenging optimization problems (higher-dimensionality, multi-modal, non-convex).
The two best algorithmic variations are when the (GL) selection scheme is combined with the 1-DTC and 1-DBDP partitioning approaches.
While the 1-DTDV-GL looks best for more straightforward problems (low-dimensional, uni-modal), the 1-DTC-GL, 1-DBDP-GL combination is more efficient in solving more challenging problems.
The worst results were obtained using various partitioning strategies combined with the (IO) selection scheme, which showed promising performance only when a given budget of function evaluations is small.

Moreover, regardless of the selection scheme, the 1-DTDV partitioning strategy has a signiﬁcant advantage when the most solution coordinates are on the boundary of the feasible region.
Additionally, the 1-DTDV partitioning approach has proven to be the most efficient in solving low-dimensional  test problems.
However, the combination based on the 1-DTDV partitioning scheme is very inefficient for higher dimensional test problems.
For such problems, the 1-DBDP partitioning approach seems much more appropriate.

Experimental investigation on 800 GKLS-type test problems showed contrasting results.
This study revealed that the (IO) scheme could be very efficient.
While on simple GKLS classes, the efficiency of -type algorithms based on (IO) and (GL) selection schemes are very similar.
However, better performance is explicitly achieved with (IO) for hard classes.
Let us recall that this selection scheme showed the worst results in the previous investigation.

To sum up, our study demonstrated that using already known techniques combined in new variations can create more efficient -type algorithms.
For example, efficient diagonal partition-based  can be further improved by replacing the original selection scheme with the GL selection (from the  algorithm), resulting in a more efficient algorithm (1-DBDP-GL).

As for further research, one possible direction could be improving the two-step-based (Global-Local) Pareto selection scheme (GL). Algorithms based on this scheme showed superior performance solving most complex optimization test problems but relatively poor efficiency on more straightforward problems.
One possible modification could be borrowing 's $\varepsilon$ parameter or similar technique to limit the size of selected POHs.
Optionally, instead of performing the selection enhancing the local search in every iteration, a specific rule could be added to specify when this selection is needed.

Finally, finding the solution efficiently should start by investigating the problem.
Then, considering this knowledge, the design or finding of a specific optimization algorithm is needed.
Thus, one of our nearest future work plans is to extend this idea by developing the automatic -type algorithm selection.

§ SOURCE CODE STATEMENT

All twelve introduced -type algorithms are implemented in  and are available in the most recent version of  (<https://github.com/blockchain-group/DIRECTGO/tree/v1.1.0>) and can be used under the MIT license.
We welcome contributions and corrections to it.

§ DATA STATEMENT

-  Global Optimization test problems Library is designed as a continuously-growing open-source GitHub repository to which anyone can easily contribute.
The exact data underlying this article from  can be accessed either on GitHub or at Zenodo:

* at GitHub: <https://github.com/blockchain-group/DIRECTGOLib/tree/v1.1>,

* at Zenodo: <https://doi.org/10.5281/zenodo.6491951>,

and used under the MIT license.
We welcome contributions and corrections to it.

Funding The research work of S. Stripinis was funded by a Grant (No. S-MIP-21-53) from the Research Council of Lithuania.

Acknowledgment The authors greatly thank the anonymous Reviewer for his valuable and constructive comments, which helped us significantly extend and improve the manuscript.

[1]
Baker, C.A., Watson, L.T., Grossman, B., Mason, W.H., Haftka, R.T.: Parallel
global aircraft configuration design space exploration.
In: A. Tentner (ed.) High Performance Computing Symposium 2000, pp.
54–66. Soc. for Computer Simulation Internat (2000)

[2]
Bartholomew-Biggs, M.C., Parkhurst, S.C., Wilson, S.P.: Using DIRECT to solve
an aircraft routing problem.
Computational Optimization and Applications 21(3), 311–323

[3]
Carter, R.G., Gablonsky, J.M., Patrick, A., Kelley, C.T., Eslinger, O.J.:
Algorithms for noisy problems in gas transmission pipeline optimization.
Optimization and Engineering 2(2), 139–157 (2001).

[4]
Clerc, M.: The swarm and the queen: Towards a deterministic and adaptive
particle swarm optimization.
In: Proceedings of the 1999 Congress on Evolutionary Computation, CEC
1999 (1999).

[5]
Cox, S.E., Haftka, R.T., Baker, C.A., Grossman, B., Mason, W.H., Watson, L.T.:
A comparison of global optimization methods for the design of a high-speed
civil transport.
Journal of Global Optimization 21(4), 415–432 (2001).

[6]
Di Serafino, D., Liuzzi, G., Piccialli, V., Riccio, F., Toraldo, G.: A
modified DIviding RECTangles algorithm for a problem in astrophysics.
Journal of Optimization Theory and Applications 151(1),
175–190 (2011).

[7]
Dixon, L., Szegö, C.: The global optimisation problem: An introduction.
In: L. Dixon, G. Szegö (eds.) Towards Global Optimization,
vol. 2, pp. 1–15. North-Holland Publishing Company (1978)

[8]
Finkel, D.E., Kelley, C.T.: An adaptive restart implementation of direct.
Technical report CRSC-TR04-30, Center for Research in Scientific
Computation, North Carolina State University, Raleigh  (2004)

[9]
Finkel, D.E., Kelley, C.T.: Additive scaling and the DIRECT algorithm.
Journal of Global Optimization 36(4), 597–608 (2006).

[10]
Gablonsky, J.M.: Modifications of the DIRECT algorithm.
Ph.D. thesis, North Carolina State University (2001)

[11]
Gablonsky, J.M., Kelley, C.T.: A locally-biased form of the DIRECT algorithm.
Journal of Global Optimization 21(1), 27–37 (2001).

[12]
Gavana, A.: Global optimization benchmarks and ampgo.
Online; accessed: 2021-07-22

[13]
Gaviano, M., Kvasov, D.E., Lera, D., Sergeyev, Y.D.: Algorithm 829: Software
for generation of classes of test functions with known local and global
minima for global optimization.
ACM Transactions on Mathematical Software (TOMS) 29(4),
469–480 (2003).

[14]
Grishagin, V.A.: Operating characteristics of some global search algorithms.
In: Problems of Stochastic Search, vol. 7, pp. 198–206. Zinatne,
Riga (1978).
In Russian

[15]
He, J., Verstak, A., Sosonkina, M., Watson, L.T.: Performance modeling and
analysis of a massively parallel DIRECT–Part 2.
The International Journal of High Performance Computing Applications
23(1), 29–41 (2009).

[16]
He, J., Verstak, A., Watson, L.T., Sosonkina, M.: Design and implementation of
a massively parallel version of direct.
Computational Optimization and Applications  (2008).

[17]
He, J., Verstak, A., Watson, L.T., Sosonkina, M.: Performance modeling and
analysis of a massively parallel DIRECT–part 1.
The International Journal of High Performance Computing Applications
23(1), 14–28 (2009).

[18]
He, J., Watson, L.T., Sosonkina, M.: Algorithm 897: VTDIRECT95: Serial and
Parallel Codes for the Global Optimization Algorithm DIRECT.
ACM Transactions on Mathematical Software  (2010).

[19]
Hedar, A.: Test functions for unconstrained global optimization.
Online; accessed: 2017-03-22

[20]
Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization.
Nonconvex Optimization and Its Application. Kluwer Academic
Publishers (1995)

[21]
Huyer, W., Neumaier, A.: Global Optimization by Multilevel Coordinate Search.
Journal of Global Optimization 14(4), 331–355 (1999).

[22]
John, H.: Adaptation in natural and artificial systems.
The University of Michigan Press, Ann Arbor  (1975)

[23]
Jones, D.R.: The Direct global optimization algorithm.
In: C.A. Floudas, P.M. Pardalos (eds.) The Encyclopedia of
Optimization, pp. 431–440. Kluwer Academic Publishers, Dordrect (2001)

[24]
Jones, D.R., Martins, J.R.R.A.: The DIRECT algorithm: 25 years Later.
Journal of Global Optimization 79(3), 521–566 (2021).

[25]
Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without
the Lipschitz constant.
Journal of Optimization Theory and Application 79(1),
157–181 (1993).

[26]
Kennedy, J., Eberhart, R.: Particle swarm optimization.
In Proceedings of the IEEE international conference on neural
networks IV pp. 1942–1948 (1995).

[27]
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated
Science  (1983).

[28]
Liu, H., Xu, S., Wang, X., Wu, X., Song, Y.: A global optimization algorithm
for simulation-based problems via the extended direct scheme.
Engineering Optimization 47(11), 1441–1458 (2015).

[29]
Liu, Q.: Linear scaling and the direct algorithm.
Journal of Global Optimization 56, 1233–1245 (2013).

[30]
Liu, Q., Zeng, J., Yang, G.: MrDIRECT: a multilevel robust DIRECT algorithm
for global optimization problems.
Journal of Global Optimization 62(2), 205–227 (2015).

[31]
Liuzzi, G., Lucidi, S., Piccialli, V.: A DIRECT-based approach exploiting
local minimizations for the solution of large-scale global optimization
Computational Optimization and Applications 45, 353–375

[32]
Mockus, J., Paulavičius, R., Rusakevičius, D., Šešok,
D., Žilinskas, J.: Application of Reduced-set Pareto-Lipschitzian
Optimization to truss optimization.
Journal of Global Optimization 67(1-2), 425–450 (2017).

[33]
Paulavičius, R., Chiter, L., Žilinskas, J.: Global optimization
based on bisection of rectangles, function values at diagonals, and a set of
Lipschitz constants.
Journal of Global Optimization 71(1), 5–20 (2018).

[34]
Paulavičius, R., Sergeyev, Y.D., Kvasov, D.E., Žilinskas, J.:
Globally-biased DISIMPL algorithm for expensive global optimization.
Journal of Global Optimization 59(2-3), 545–567 (2014).

[35]
Paulavičius, R., Sergeyev, Y.D., Kvasov, D.E., Žilinskas, J.:
Globally-biased BIRECT algorithm with local accelerators for expensive
global optimization.
Expert Systems with Applications 144, 11305 (2020).

[36]
Paulavičius, R., Žilinskas, J.: Analysis of different norms and
corresponding Lipschitz constants for global optimization.
Technological and Economic Development of Economy 36(4),
383–387 (2006).

[37]
Paulavičius, R., Žilinskas, J.: Analysis of different norms and
corresponding Lipschitz constants for global optimization in multidimensional
Information Technology and Control 36(4), 383–387 (2007)

[38]
Paulavičius, R., Žilinskas, J.: Improved Lipschitz bounds with the
first norm for function values over multidimensional simplex.
Mathematical Modelling and Analysis 13(4), 553–563 (2008).

[39]
Paulavičius, R., Žilinskas, J.: Global optimization using the
branch-and-bound algorithm with a combination of Lipschitz bounds over
Technological and Economic Development of Economy 15(2),
310–325 (2009).

[40]
Paulavičius, R., Žilinskas, J.: Simplicial Lipschitz optimization
without the Lipschitz constant.
Journal of Global Optimization 59(1), 23–40 (2013).

[41]
Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization.
SpringerBriefs in Optimization. Springer New York, New York, NY

[42]
Pintér, J.D.: Global optimization in action: continuous and Lipschitz
optimization: algorithms, implementations and applications, Nonconvex
Optimization and Its Applications, vol. 6.
Springer US (1996).

[43]
Piyavskii, S.A.: An algorithm for finding the absolute minimum of a function.
Theory of Optimal Solutions 2, 13–24 (1967).
In Russian

[44]
Rios, L.M., Sahinidis, N.V.: Derivative-free optimization: a review of
algorithms and comparison of software implementations.
Journal of Global Optimization 56(3), 1247–1293 (2007).

[45]
Sergeyev, Y.D., Kvasov, D.E.: Global search based on diagonal partitions and a
set of Lipschitz constants.
SIAM Journal on Optimization 16(3), 910–937 (2006).

[46]
Sergeyev, Y.D., Kvasov, D.E.: Diagonal Global Optimization Methods.
FizMatLit, Moscow (2008).
In Russian

[47]
Sergeyev, Y.D., Kvasov, D.E.: Lipschitz global optimization.
In: J.J. Cochran, L.A. Cox, P. Keskinocak, J.P. Kharoufeh, J.C. Smith
(eds.) Wiley Encyclopedia of Operations Research and Management Science (in 8
volumes), vol. 4, pp. 2812–2828. John Wiley & Sons, New York (2011)

[48]
Sergeyev, Y.D., Kvasov, D.E.: Deterministic Global Optimization: An
Introduction to the Diagonal Approach.
SpringerBriefs in Optimization. Springer (2017).

[49]
Shubert, B.O.: A sequential method seeking the global maximum of a function.
SIAM Journal on Numerical Analysis 9, 379–388 (1972).

[50]
Stripinis, L., Paulavičius, R.: DIRECTGO: A new DIRECT-type MATLAB
toolbox for derivative-free global optimization (2022).

[51]
Stripinis, L., Paulavičius, R.: DIRECTGO: A new DIRECT-type MATLAB
toolbox for derivative-free global optimization.
<https://github.com/blockchain-group/DIRECTGO> (2022)

[52]
Stripinis, L., Paulavičius, R., Žilinskas, J.: Improved scheme for
selection of potentially optimal hyper-rectangles in DIRECT.
Optimization Letters 12(7), 1699–1712 (2018).

[53]
Stripinis, L., Paulavičius, R., Žilinskas, J.: Penalty functions
and two-step selection procedure based -type algorithm for constrained
global optimization.
Structural and Multidisciplinary Optimization 59(6),
2155–2175 (2019).

[54]
Stripinis, L., Paulavičius, R.: DIRECTGOLib - DIRECT Global Optimization
test problems Library, v1.0 (2022).

[55]
Stripinis, L., Paulavičius, R.: DIRECTGOLib - DIRECT Global Optimization
test problems Library, v1.1 (2022).

[56]
Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex
Constraints: Sequential and Parallel Algorithms.
Kluwer Academic Publishers, Dordrecht (2000)

[57]
Surjanovic, S., Bingham, D.: Virtual library of simulation experiments: Test
functions and datasets.
<http://www.sfu.ca/ ssurjano/index.html> (2013).
Online; accessed: 2017-03-22

[58]
Watson, L.T., Baker, C.A.: A fully-distributed parallel global search
algorithm. engineering computations.
Engineering Computations 18(1/2), 155–169 (2001).

[59]
Wolpert, D., Macready, W.: No free lunch theorems for optimization.
IEEE Transactions on Evolutionary Computation 1(1), 67–82

§  LIBRARY

A summary of all used box-constrained optimization problems from  [55] and their properties are given in <Ref>.
Here, the main features are reported: problem number (#), name of the problem, source, dimensionality ($ n $), default optimization domain ($ D $), perturbed optimization domain ($\tilde{D}$), problem type, and the known minimum ($ f^* $).
The default domains are taken from the literature.
Whenever the global minimum point lies at the initial sampling points for at least one tested algorithm, the domain $D$ has been shifted by $22.5 \%$ to the right side.
These modified problems are marked with the beta sign $(^{\beta})$.
Here the sign “-” means that $\tilde{D}$ is the same as $D$.
Some of these test problems have several variants, e.g., Bohachevsky, Shekel, and some of them, like Alpine, Csendes, Griewank, etc., can be tested for varying dimensionality.

Key characteristics of the  [55] test problems for box-constrained global optimization
#     Name     Source     $n$       $ D $      $ \tilde{D} $     Type     No. of minima     $ f^* $

$1,2,3$        Ackley$^{\beta}$ 		    [19, 57] 		    $2,5,10$ 	    $[-15, 35]^n$     $[-18, 47]^n$ 			    		    non-convex     multi-modal     $0.0000$

$4,5,6$        Alpine$^{\alpha}$ 		    [12] 		   		    $2,5,10$ 	    $[0, 10]^n$       $[\sqrt[i]{2}, 8 + \sqrt[i]{2}]^n$  	    non-convex     multi-modal     $-2.8081^n$

$7$ 	       Beale      	 			    [19, 57] 		    $2$  		    $[-4.5, 4.5]^n$     $-$  	   		 		    non-convex     multi-modal     $0.0000$

$8$ 	       Bohachevsky$1^{\beta}$  	    [19, 57] 		    $2$  		    $[-100, 110]^n$     $[-55, 145]^n$   	   							    convex 	     uni-modal       $0.0000$

$9$ 	       Bohachevsky$2^{\beta}$ 	    [19, 57] 		    $2$  		    $[-100, 110]^n$     $[-55, 145]^n$   	   							    non-convex     multi-modal     $0.0000$

$10$ 	       Bohachevsky$3^{\beta}$  	    [19, 57] 		    $2$  		    $[-100, 110]^n$     $[-55, 145]^n$   	   							    non-convex     multi-modal     $0.0000$

$11$ 	       Booth          			    [19, 57] 		    $2$  		    $[-10, 10]^n$     $-$  	 	 						    convex 	     uni-modal       $0.0000$

$12$ 	       Branin          			    [19, 7] 		    $2$  		    $[-5, 10] \times [10,15]$     $-$ 					    non-convex     multi-modal     $0.3978$

$13$ 	       Bukin6           			    [57] 		  	 		    $2$  		    $[-15, 5] \times [-3,3]$     $-$  					    convex 	     multi-modal     $0.0000$

$14$ 	       Colville        			    [19, 57] 		    $4$  		    $[-10, 10]^n$     $-$           						    non-convex     multi-modal     $0.0000$

$15$ 	       Cross_in_Tray   		    [57] 		  	 		    $2$    	    $[0, 10]^n$     $-$           						    non-convex     multi-modal     $-2.0626$

$16$ 	       Crosslegtable   			    [12] 		  	 	    $2$    	    $[-10, 15]^n$     $-$           						    non-convex     multi-modal     $-1.000$

$17,18,19$     Csendes$^{\beta}$     	    [12] 		  	 	    $2,5,10$      $[-10, 21]^n$     $[-10, 25]^n$          	    convex 	     multi-modal     $0.0000$

$20$ 	       Damavandi   				    [12] 		  	 	    $2$    	    $[0, 14]^n$      $-$           						    non-convex     multi-modal     $0.0000$

$21,22,23$     Deb$01$$^{\beta}$    	    [12] 				    $2,5,10$      $[-1, 1]^n$     $[-0.55, 1.45]^n$         					    non-convex     multi-modal     $-1.0000$

$24,25,26$     Deb$02$$^{\beta}$   		    [12] 				    $2,5,10$      $[0, 1]^n$     $[0.225, 1.225]^n$ 							    non-convex     multi-modal     $-1.0000$

$27,28,29$     Dixon_and_Price   		    [19, 57] 		    $2,5,10$      $[-10, 10]^n$     $-$         						    convex 	     multi-modal     $0.0000$

$30$ 	       Drop_wave$^{\beta}$   	    [57] 		  	 		    $2$    	    $[-5.12, 6.12]^n$      $[-4, 6]^n$      								    non-convex     multi-modal     $-1.0000$

$31$ 	       Easom$^{\alpha}$     		    [19, 57] 		    $2$    	    $[-100, 100]^n$     $\left[\dfrac{-100}{i+1}, 100i \right]^n$ 	    non-convex     multi-modal     $-1.0000$

$32$ 	       Eggholder       			    [57] 		  	 		    $2$   	    $[-512, 512]^n$     $-$         						    non-convex     multi-modal     $-959.6406$

$33$ 	       Goldstein_and_Price$^{\beta}$     [19, 7]     $2$   	    $[-2, 2]^n$       $[-1.1, 2.9]^n$          						    non-convex     multi-modal     $3.0000$

$34,35,36$     Griewank$^{\alpha}$         [19, 57]     $2,5,10$     $[-600, 700]^n$     $\left[-\sqrt{600i}, \dfrac{600}{\sqrt{i}} \right]^n$     non-convex     multi-modal     $0.0000$

$37$ 	       Hartman$3$       			    [19, 57] 		    $3$    	    $[0, 1]^n$ 	    $-$              						    non-convex     multi-modal     $-3.8627$

$38$ 	       Hartman$6$        		    [19, 57] 		    $6$    	    $[0, 1]^n$      $-$            						    non-convex     multi-modal     $-3.3223$

$39$ 	       Holder_Table      		    [57] 			 		    $2$    	    $[-10, 10]^n$       $-$           						    non-convex     multi-modal     $-19.2085$

$40$ 	       Hump              		    [19, 57] 		    $2$    	    $[-5, 5]^n$     $-$           						    non-convex     multi-modal     $-1.0316$

$41$ 	       Langermann        		    [57] 			 		    $2$    	    $[0, 10]^n$       $-$           						    non-convex     multi-modal     $-4.1558$

$42,43,44$     Levy              		    [19, 57] 		    $2,5,10$      $[-5, 5]^n$     $-$             						    non-convex     multi-modal     $0.0000$

$45$ 	       Matyas$^{\beta}$             [19, 57] 		    $2$    	    $[-10, 15]^n$     $[-5.5, 14.5]^n$  	 						    convex 	     uni-modal       $0.0000$

$46$ 	       McCormick         		    [57] 	 		 		    $2$    	    $[-1.5, 4] \times [-3,4]$     $-$ 					    convex 	     multi-modal     $-1.9132$

$47$ 	       Michalewicz       		    [19, 57] 		    $2$    	    $[0, \pi]^n$     $-$            						    non-convex     multi-modal     $-1.8013$

$48$ 	       Michalewicz       		    [19, 57] 		    $5$    	    $[0, \pi]^n$     $-$          						    non-convex     multi-modal     $-4.6876$

$49$         Michalewicz       		    [19, 57] 		    $10$   	    $[0, \pi]^n$     $-$         	 						    non-convex     multi-modal     $-9.6601$

$50$ 	       Permdb$4$ 						    [19, 57] 	    $4$    	    $[-i, i]^n$     $[-i, i]^n$  									    non-convex     multi-modal     $0.0000$

$51,52,53$     Pinter$^{\beta}$     	    [12] 		  	 	    $2,5,10$      $[-10, 10]^n$     $[-5.5, 14.5]^n$      						    non-convex     multi-modal     $0.0000$

$54$ 	       Powell       				    [19, 57] 		    $4$    	    $[-4, 5]^n$     $-$             						    convex 	     multi-modal     $0.0000$

$55$ 	       Power_Sum$^{\alpha}$         [19, 57] 		    $4$    	    $[0, 4]^n$     $[1, 4 + \sqrt[i]{2}]^n$            			    convex 	     multi-modal       $0.0000$

$56,57,58$     Qing     	    			    [12] 		  	 	    $2,5,10$      $[-500, 500]^n$     $-$      	 						    non-convex     multi-modal     $0.0000$

$59,60,61$     Rastrigin$^{\alpha}$    	    [19, 57] 		    $2,5,10$      $[-6.12, 5.12]^n$     $[-5\sqrt[i]{2}, 7+\sqrt[i]{2}]^n$       		    non-convex     multi-modal     $0.0000$

$62,63,64$     Rosenbrock$^{\alpha}$   	    [19, 7]  		    $2,5,10$      $[-5, 10]^n$     $\left[-\dfrac{5}{\sqrt{i}}, 10\sqrt{i} \right]^n$     non-convex     uni-modal     $0.0000$

$65,66,67$     Rotated_H_Ellip$^{\beta}$     [57] 	 			    $2,5,10$      $[-65.536, 66.536]^n$     $[-35, 96]^n$   								    convex 	     uni-modal       $0.0000$

$68,69,70$     Schwefel$^{\alpha}$ 		    [19, 57] 		    $2,5,10$ 	    $[-500, 500]^n$ 	    $\left[-500 + \dfrac{100}{\sqrt{i}}, 500 - \dfrac{40}{\sqrt{i}} \right]^n$     non-convex     multi-modal     $0.0000$

$71$ 	       Shekel$5$  				    [19, 57] 		    $4$    	    $[0, 10]^n$ 		    $-$             						    non-convex     multi-modal     $-10.1531$

$72$ 	       Shekel$7$   				    [19, 57]	 	    $4$    	    $[0, 10]^n$ 		    $-$             						    non-convex     multi-modal     $-10.4029$

$73$ 	       Shekel$10$  				    [19, 57] 		    $4$    	    $[0, 10]^n$ 		    $-$             						    non-convex     multi-modal     $-10.5364$

$74$ 	       Shubert           		    [19, 57] 		    $2$    	    $[-10, 10]^n$ 	    $-$           						    non-convex     multi-modal     $-186.7309$

$75,76,77$     Sphere$^{\beta}$      	    [19, 57] 		    $2,5,10$      $[-5.12, 6.12]^n$     $[-2.75, 7.25]^n$      						    convex 	     uni-modal       $0.0000$

$78,79,80$     Styblinski_Tang$^{\alpha}$     [4] 			        $2,5,10$      $[-5, 5]^n$ 		    $[-5, 5+\sqrt[i]{3}]^n$       	    					    non-convex     multi-modal     $-39.1661n$

$81,82,83$     Sum_of_Powers$^{\beta}$     [57]		 			    $2,5,10$      $[-1, 2.5]^n$ 		    $[-0.55, 1.45]^n$      						    convex 	     uni-modal       $0.0000$

$84,85,86$     Sum_Square$^{\beta}$  	    [4] 			 		    $2,5,10$      $[-10, 15]^n$ 	    $[-5.5, 14.5]^n$        						    convex 	     uni-modal       $0.0000$

$87$ 	       Trefethen           		    [12] 				    $2$    	    $[-2, 2]^n$ 		    $-$           						    non-convex     multi-modal     $-3.3068$

$88,89,90$     Trid              		    [19, 57] 		    $2,5,10$      $[-100, 100]^n$  	    $-$           					    convex 	     multi-modal     $\vartheta$

$91,92,93$     Vincent           		    [4] 					    $2,5,10$      $[0.25, 10]^n$ 	    $-$          						    non-convex     multi-modal     $-n$

$94,95,96$     Zakharov$^{\beta}$     	    [19, 57] 		    $2,5,10$      $[-5, 11]^n$ 		    $[-1.625, 13.375]^n$      					    convex 	     multi-modal     $0.0000$

8l$\vartheta$ – $-\frac{1}{6}n^3 - \frac{1}{2}n^2 +  \frac{2}{3}n$

8l${\alpha}$ – domain $D$ was perturbed to avoid the dominance of certain partitioning schemes (see <Ref>)

8l${\beta}$ – domain $D$ was moved by $22.5 \%$ percent to the right side

8l${i = 1, ..., n}$