Lipschitz-inspired  Algorithm for Derivative-free Global Optimization

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

<EMAIL_ADDRESS>R. Paulavičius<EMAIL_ADDRESS>
This article considers a box-constrained global optimization problem for Lipschitz-continuous functions with an unknown Lipschitz constant.
Motivated by the famous  (DIviding RECTangles), a new  (HALving RECTangles) algorithm is introduced.
A new deterministic approach combines halving (bisection) with a new multi-point sampling scheme in contrast to trisection and midpoint sampling used in most existing -type algorithms.
A new partitioning and sampling scheme uses more comprehensive information on the objective function.
Four different strategies for selecting potentially optimal hyper-rectangles are introduced to exploit the objective function's information effectively.
The original algorithm  and other introduced  variations (twelve in total) are tested and compared with the other twelve recently introduced -type algorithms on $96$ box-constrained benchmark functions from , and $96$ perturbed their versions.
Extensive experimental results are advantageous compared to state-of-the-art -type global optimization.
New  approaches offer high robustness across problems of different degrees of complexity, varying from simple – uni-modal and low dimensional to complex – multi-modal and higher dimensionality.

65K05 74P99 78M50, 90C99 65K10

§ INTRODUCTION

Generally, global optimization approaches can be divided into two main classes: deterministic and stochastic [17, 38].
Deterministic algorithms theoretically guarantee that at least one global optimum can be found [9], while stochastic algorithms find the solution in the probability sense [21].

Various optimization problems in science and engineering (e.g., machine learning models [2], Boeing design [3], etc.) are black-box, i.e., the analytic information about the objective and constraints functions is unavailable.
Therefore, the development of derivative-free optimization has been forced by the need to optimize various and often increasingly complex problems in practice.

In this paper we consider a box-constrained potentially black-box global optimization problem

\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 real-valued Lipschitz-continuous function, i.e., there exists a positive constant $0 < L < \infty$, such that

\begin{equation}\label{eq:LipschitzCondition}
\abs{f(\mathbf{x}) - f(\mathbf{y})}  \le  L\| \mathbf{x} - \mathbf{y} \|, \quad \forall \mathbf{x}, \mathbf{y} \in D,
\end{equation}

and the feasible region 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\} $.
In a black-box optimization case, the objective function $f$ is unknown and any information can only be obtained by evaluating the function at feasible points.

The  algorithm, developed by Jones et al. [20], is a well-known and widely used sampling-based solution technique for derivative-free global optimization with limitations in the box.
An algorithm is an extension of classical Lipschitz optimization (e.g., [29, 30, 35, 36, 41, 43]), where the need to know the Lipschitz constant is eliminated.
The  algorithm has also been successfully extended to solve problems with various constraints.
Authors in [32] proposed an approach to tackle linearly constrained problems.
Other authors [5, 7, 18, 22, 33, 34, 49] introduced -type algorithm for generally constrained or even the for problems with hidden constraints [10, 25, 44].

In addition, -type algorithms appear more often in the parallel environment [14, 52, 50].

A decade-old comprehensive numerical benchmarking [37] showed the encouraging performance of -type algorithms among other derivative-free global optimization methods.
Our recent extensive study [50] revealed that new and potentially better -type algorithms are available today.
In [45], we also demonstrated that even better -type algorithms could be obtained by combining various already known candidate selection and partitioning techniques, leading to even more efficient -type algorithms.
Therefore, continuous design and development of efficient -type algorithms is important and motivated by practice needs.

Unfortunately, -type algorithms are not without their drawbacks.

Among them, two well-known ones are [11, 18, 19, 26, 28, 40]: i) delayed discovery of the globally optimal solution, especially for multi-modal and greater dimensionality problems, and ii) slow fine-tuning of the solution to high accuracy.
This limits  applicability mainly to lower-dimensionality global optimization problems [19].
The first drawback is possibly determined by the original sampling scheme based on one center point per hyper-rectangle.
If the hyper-rectangle containing the global solution has a bad objective value at the midpoint, it is undesirable for the selection, and his further subdivision is delayed.

To address this in [26, 39], the authors introduced two different diagonal sampling schemes using two points per hyper-rectangle.
In this way, new algorithms,  [26] and  [39], intuitively reduce the chance of this situation occurring.
It would require evaluating two bad points in the hyper-rectangle containing the global optimum.
In [18], the author observed that to reduce the curse of dimensionality, the division of hyper-rectangles along only one longest side instead of all has a very positive impact.
Moreover, various two-phase-based approaches (see, e.g., [27, 39]) and hybridized -type methods (see, e.g. [16, 18, 28, 49, 23, 24]) were proposed to address both these shortcomings.

This paper introduces a new  (HALving RECTangles) algorithm based on a new multi-point sampling scheme efficiently combined with halving (bisection).
Each hyper-rectangle is represented by considering up to $2n + 1$ sampling points and halved using bisection instead of just one sampled midpoint and trisection traditionally used in most -type algorithms.
Therefore, more comprehensive information about the objective function over each hyper-rectangle is captured, especially for higher-dimensionality problems, as more sampled points are considered in selecting potentially optimal hyper-rectangles.

The rest of the paper is organized as follows.
<Ref> reviews relevant existing -type modifications and summarizes the most common selection schemes and partitioning strategies used in state-of-the-art  algorithms.
A description of the new  algorithm and all its new variations is given in <Ref>.
The extensive numerical investigation of twelve  variations and comparison with twelve recently introduced -type algorithms [45] using $96$ box-constrained global optimization test problems and their perturbed versions from  [51] is provided in <Ref>.
Finally, we conclude the paper in <Ref>.

§ RELATED LITERATURE REVIEW

This section reviews some of the most relevant -type modifications.
We begin with a recap of the original algorithm.
Reviewing other -type algorithms, we mainly focus on the proposed candidate selection, sampling, and partitioning schemes.

§.§ Original  algorithm

The original  algorithm is designed for box-constrained global optimization problems.
Initially, the algorithm normalizes the feasible region $D = [\mathbf{a}, \mathbf{b}]$ to a unit hyper-rectangle $ \bar{D} = [0, 1]^n$ and only refers to the original space $D$ when evaluating the objective function $f$.
Therefore, throughout this paper, when it says that the value of the objective function is evaluated at $f(\mathbf{c})$, where the midpoint $\mathbf{c} \in \bar{D}$, it is understood that the corresponding midpoint of the original domain ($\mathbf{x} \in D$) is used, i.e.,

\begin{equation}
\label{eq:space_original}
f(\mathbf{c}) = f(\mathbf{x}), \text{where } x_j = (b_j - a_j) c_j + a_j, j=1,\dots,n.
%	\mathbf{x}^i = \| \mathbf{b} - \mathbf{a} \|  \mathbf{c}^i + \mathbf{a},
\end{equation}

In each iteration, certain hyper-rectangles are identified and selected as “potentially optimal hyper-rectangles” (POH) for further investigation.
samples and evaluates the objective function at the midpoint of each POH and subdivides them (into smaller hyper-rectangles) using the trisection strategy.
The selection, sampling, and subdivision procedures continue until some predefined limits have not been reached.
<Ref> illustrates this process, showing the initialization and the first two subsequent iterations of  for the two-variable Bukin6 test problem.

xlabel = $c_1$,
ylabel = $c_2$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.8,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=-0.01cm,
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!40,opacity=0.4,line width=0.3mm] (axis cs:0,0) rectangle (axis cs:1,1);
[only marks,mark=*, mark size=2pt,blue] coordinates (1/2, 1/2) node[yshift=-12pt] $\mathbf{c}^1$ node[yshift=12pt] $50.05$;

xlabel = $c_1$,

title=Iteration $1$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.8,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=-0.01cm,
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!40,,fill=blue!40,opacity=0.4,line width=0.3mm
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 (1/3, 0) (1/3, 1) (2/3, 1) (2/3, 0);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (1/3, 1/3) (1/3, 2/3) (2/3, 2/3) (2/3, 1/3);
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.3mm] (axis cs:2/3,0) rectangle (axis cs:1,1);
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 1/2) node[yshift=-12pt] $\mathbf{c}^1$ node[yshift=12pt] $50.05$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/6, 1/2) node[yshift=-12pt] $\mathbf{c}^2$ node[yshift=12pt] $116.68$;
[only marks,mark=*, mark size=2pt,blue] coordinates (5/6, 1/2) node[yshift=-12pt] $\mathbf{c}^3$ node[yshift=12pt] $16.78$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 1/6) node[yshift=-12pt] $\mathbf{c}^4$ node[yshift=12pt] $150.05$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 5/6) node[yshift=-12pt] $\mathbf{c}^5$ node[yshift=12pt] $132.33$;

xlabel = $c_1$,

title=Iteration $2$,
legend style=draw=none,
legend columns=1,
legend style=at=(0.85,-0.2),font=,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=-0.01cm,
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) ;
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (1/3, 0) (1/3, 1) (2/3, 1) (2/3, 0);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.3mm] coordinates (1/3, 1/3) (1/3, 2/3) (1, 2/3) (1, 1/3);
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.3mm] (axis cs:0, 0) rectangle (axis cs:1/3, 1);
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.3mm] (axis cs:2/3, 1/3) rectangle (axis cs:1, 2/3);
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 1/2) node[yshift=-12pt] $\mathbf{c}^1$ node[yshift=12pt] $50.05$;
[only marks,mark=*, mark size=2pt,blue] coordinates (1/6, 1/2) node[yshift=-12pt] $\mathbf{c}^2$ node[yshift=12pt] $116.68$;
[only marks,mark=*, mark size=2pt,blue] coordinates (5/6, 1/2) node[yshift=-12pt] $\mathbf{c}^3$ node[yshift=12pt] $16.78$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 1/6) node[yshift=-12pt] $\mathbf{c}^4$ node[yshift=12pt] $150.05$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 5/6) node[yshift=-12pt] $\mathbf{c}^5$ node[yshift=12pt] $132.33$;
[only marks,mark=o, mark size=2pt,black] coordinates (5/6, 1/6) node[yshift=-12pt] $\mathbf{c}^6$ node[yshift=12pt] $142.51$;
[only marks,mark=o, mark size=2pt,black] coordinates (5/6, 5/6) node[yshift=-12pt] $\mathbf{c}^7$ node[yshift=12pt] $140.55$;

Two-dimensional illustration of selection, central sampling, and trisection used in the original  algorithm [20] solving the Bukin6 test problem.

Regardless of the dimension, the first evaluation of the objective function is performed at the midpoint ($\mathbf{c}^1$).
Then, the  algorithm identifies and selects the POHs.
At initialization, the selection is trivial since only one hyper-rectangle $(\bar{D}^1)$ is available (see the left panel in <Ref>).
After selection,  samples new midpoints at positions

\begin{equation}
\mathbf{c}^1 \pm \frac{1}{3}d^{\rm max} \mathbf{e}_j, j \in M,
\end{equation}

where $d^{\rm max}$ is equal to the maximum side length, $M$ is a set of dimensions with the maximum side length, and $\mathbf{e}_j$ is the $j$th unit vector.

The algorithm uses $n$-dimensional trisection, with the property that the objective function is evaluated at each hyper-rectangle only once — at a midpoint.
The midpoint of the initial hyper-rectangle becomes the midpoint of the new smaller “middle” one.
Suppose the selected hyper-rectangle has more than one dimension with the maximum side length (as is the case for the initial hyper-rectangle).
In that case,  starts the trisection from the dimension with the lowest $w_j$ value

\begin{equation}
w_j = \min \{ f(\mathbf{c}^1 + \frac{1}{3}d^{\rm max}\mathbf{e}_j),  f(\mathbf{c}^1 - \frac{1}{3}d^{\rm max}\mathbf{e}_j) \},  j \in M,
\end{equation}

and continues to the highest [19, 20].
In this way, the lower function values are placed in larger hyper-rectangles (see the middle panel in <Ref>).
If all side lengths are equal, $2n + 1$ new smaller non-overlapping hyper-rectangles of $n$ distinct sizes are created.

Unlike initialization, in subsequent iterations, the selection of POHs is not trivial, as we have more than one candidate (see the middle and right panels in <Ref>).
Therefore, the selection procedure needs to be formalized.
Let the current partition in iteration $ k $ be defined as:

\begin{equation}\label{eq:partition_set}
\mathcal{P}_k = \{ \bar{D}^i_k : i \in \indexsett_k \},
\end{equation}

\begin{equation}\label{eq:rectangle}
\bar{D}^i_k = [\mathbf{a}_k^i, \mathbf{b}_k^i] = \{ \mathbf{x} \in \bar{D}: 0 \leq a_{k_j}^i \leq x_j \leq b_{k_j}^i \leq 1, j = 1,\dots, n, \forall i \in \indexsett_k \},
\end{equation}

and $ \indexsett_k $ is the index set that identifies 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 $.
At the first iteration ($k=0$), there is always only one candidate, $\mathcal{P}_0 = \{ \bar{D}^1_0 \}$, which is automatically potentially optimal.
The formal requirement of potential optimality in subsequent iterations is stated in <Ref>.

(Original selection)

Let $ \mathbf{c}^i $ denote the midpoint, $f(\mathbf{c}^i)$ objective function value $f(\mathbf{c}^i)$ obtained at the midpoint, and $ \delta^i_k $ be a measure (equivalently, sometimes called distance or size) of hyper-rectangle $ \bar{D}^i_k$.
Let $ \varepsilon > 0 $ be a positive constant and $f^{\min}$ be the best currently found objective function value.
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{c}^h) - \tilde{L}\delta^h_k & \leq & f(\mathbf{c}^i) - \tilde{L}\delta^i_k, \quad \forall i \in \indexsett_k, \label{eqn:potOptRect1} \\
f(\mathbf{c}^h) - \tilde{L}\delta^h_k & \leq & f^{\min} - \varepsilon \abs{f^{\min}}, \label{eqn:potOptRect2}
\end{eqnarray}

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

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

The hyper-rectangle $ \bar{D}^h_k $ is potentially optimal if the lower Lipschitz bound for the objective function computed on the left-hand side of (<ref>) is the lowest with some positive constant $\tilde{L}$ in the current partition $ \mathcal{P}_k $.
In (<ref>), the parameter $\varepsilon$ is used to protect against excessive refinement of the local minima [20, 27].
Therefore, the lower Lipschitz bound on POH must be lower than the current minimum value $(f^{\rm min})$ by a considerable amount $(\ge \varepsilon \abs{f^{\min}})$.
In [20], the authors obtained good performance using $\varepsilon$ values ranging from $10^{-3}$ to $10^{-7}$, and by default, the $\varepsilon = 10^{-4}$ value is suggested.

A geometrical interpretation of POH selection using <Ref> is illustrated in the right panel of <Ref>.
Here, each hyper-rectangle is represented as a dot whose horizontal coordinate is equal to the measure of the hyper-rectangle ($\delta^i_k$).
The vertical coordinate is equal to the value of the function at the midpoint $f(\mathbf{c}^i)$.
POHs satisfy both conditions of <Ref> and correspond to the lower-right convex hull of blue marked points in <Ref>.

legend style=draw=none,
legend columns=1,
legend style=at=(0.75,-0.15),font=,
xlabel = $c_1$,
ylabel = $c_2$,
title= sampling and partitioning,
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$,
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.3mm] (axis cs:0, 1/3) rectangle (axis cs:1/3, 7/9);
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.3mm] (axis cs:20/27, 4/9) rectangle (axis cs:21/27, 5/9);
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 1/2) node[yshift=-6pt, scale=0.5] $\mathbf{c}^1$ node[yshift=6pt, scale=0.5] $50.05$;
[only marks,mark=*, mark size=2pt,blue] coordinates (1/6, 1/2) node[yshift=-12pt] $\mathbf{c}^2$ node[yshift=12pt] $116.68$;
[only marks,mark=o, mark size=2pt,black] coordinates (5/6, 1/2) node[yshift=-6pt, scale=0.5] $\mathbf{c}^3$ node[yshift=6pt, scale=0.5] $16.78$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 1/6) node[yshift=-12pt] $\mathbf{c}^4$ node[yshift=12pt] $150.05$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 5/6) node[yshift=-12pt] $\mathbf{c}^5$ node[yshift=12pt] $132.33$;
[only marks,mark=o, mark size=2pt,black] coordinates (5/6, 1/6) node[yshift=-12pt] $\mathbf{c}^6$ node[yshift=12pt] $142.51$;
[only marks,mark=o, mark size=2pt,black] coordinates (5/6, 5/6) node[yshift=-12pt] $\mathbf{c}^7$ node[yshift=12pt] $140.55$;
[only marks,mark=o, mark size=2pt,black] coordinates (13/18, 1/2);
[only marks,mark=o, mark size=2pt,black] coordinates (17/18, 1/2) node[yshift=-6pt, scale=0.5] $\mathbf{c}^9$ node[yshift=6pt, scale=0.5] $39.02$;
[only marks,mark=o, mark size=2pt,black] coordinates (5/6, 7/18) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{10}$ node[yshift=6pt, scale=0.5] $83.45$;
[only marks,mark=o, mark size=2pt,black] coordinates (5/6, 11/18) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{11}$ node[yshift=6pt, scale=0.5] $80.04$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/6, 1/6) node[yshift=-12pt] $\mathbf{c}^{12}$ node[yshift=12pt] $183.35$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/6, 5/6) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{13}$ node[yshift=6pt, scale=0.5] $79.94$;
[only marks,mark=o, mark size=2pt,black] coordinates (13/18, 7/18) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{14}$ node[yshift=6pt, scale=0.5] $81.93$;
[only marks,mark=o, mark size=2pt,black] coordinates (13/18, 11/18) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{15}$ node[yshift=6pt, scale=0.5] $81.55$;
[only marks,mark=o, mark size=2pt,black] coordinates (7/18, 1/2) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{16}$ node[yshift=6pt, scale=0.5] $72.25$;
[only marks,mark=o, mark size=2pt,black] coordinates (11/18, 1/2) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{17}$ node[yshift=6pt, scale=0.5] $27.85$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 7/18) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{18}$ node[yshift=6pt, scale=0.5] $95.79$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/2, 11/18) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{19}$ node[yshift=6pt, scale=0.5] $64.59$;
[only marks,mark=o, mark size=2pt,black] coordinates (37/54, 1/2) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{20}$;
[only marks,mark=*, mark size=2pt,blue] coordinates (41/54, 1/2) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{21}$;
[only marks,mark=o, mark size=2pt,black] coordinates (13/18, 25/54);
[only marks,mark=o, mark size=2pt,black] coordinates (13/18, 29/54);
[only marks,mark=o, mark size=2pt,black] coordinates (11/18, 7/18) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{24}$ node[yshift=6pt, scale=0.5] $86.31$;
[only marks,mark=o, mark size=2pt,black] coordinates (11/18, 11/18) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{25}$ node[yshift=6pt, scale=0.5] $76.85$;
[only marks,mark=*, mark size=2pt,blue] coordinates (1/6, 13/18) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{26}$ node[yshift=6pt, scale=0.5] $16.68$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/6, 17/18) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{27}$ node[yshift=6pt, scale=0.5] $114.27$;
[only marks,mark=o, mark size=2pt,black] coordinates (1/18, 5/6) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{28}$ node[yshift=6pt, scale=0.5] $26.68$;
[only marks,mark=o, mark size=2pt,black] coordinates (5/18, 5/6) node[yshift=-6pt, scale=0.5] $\mathbf{c}^{29}$ node[yshift=6pt, scale=0.5] $105.26$;
[patch,mesh,draw,black,patch type=rectangle] coordinates
(0, 0) (1, 0) (1, 1) (0, 1)
(0, 1/3) (1, 1/3) (1, 2/3) (0, 2/3)
(1/3, 0) (1/3, 1) (2/3, 1) (2/3, 0)
(7/9, 1/3) (7/9, 2/3) (8/9, 2/3) (8/9, 1/3)
(4/9, 4/9) (4/9, 5/9) (8/9, 5/9) (8/9, 4/9)
(4/9, 1/3) (4/9, 2/3) (5/9, 2/3) (5/9, 1/3)
(1/9, 7/9) (1/9, 8/9) (2/9, 8/9) (2/9, 7/9)
(0, 7/9) (3/9, 7/9) (3/9, 8/9) (0, 8/9)
(19/27, 4/9) (19/27, 5/9) (20/27, 5/9) (20/27, 4/9)
(19/27, 13/27) (19/27, 14/27) (20/27, 14/27) (20/27, 13/27);

every axis/.append style=font=,
xlabel = $\delta^i_k$,
xtick distance=0.2,
ytick distance=40,
title=POH selection,
ylabel = $f(\mathbf{c}^i)$,
legend pos=north west,
ylabel style=yshift=-0.1cm,
xlabel style=yshift=-0.1cm,
[only marks,mark=o,mark size=3pt,black] table[x=Y,y=X] data/DPD.txt;
[mark=*,mark size=3pt,blue] table[x=T,y=Z] data/DPD.txt;
non-potentially optimal,potentially optimal;

Visualization of selected potentially optimal rectangles in the fifth iteration of the  algorithm solving two-dimensional Bukin6 test problem.

§.§ Brief review of candidate selection schemes

Typically, the -type algorithms include three main steps: selection (of POHs), sampling, and partitioning (subdivision).
At each iteration, a specific -type algorithm first selects the set of POHs before sampling and subdividing them.

In [45], we reviewed various improvements and new ideas introduced for the selection of POH proposed in the  literature.
The three most promising ones were extracted and used to construct new -type algorithms, combining them with four different sampling and partitioning techniques.
For consistency, we give a brief description and a summary (see  <Ref>) of the most often used selection schemes.
<Ref> briefly reviews sampling and partitioning techniques traditionally used in -type algorithms.

§.§.§ Improved original selection strategy

It was observed that the original candidate selection strategy could be very inefficient on symmetric and other specific problems.
There may be many POHs with the same diameter $\delta^i_k$ and objective value, leading to a drastic increase in selected POHs per iteration.
To overcome this, the authors of [11] proposed an improvement by selecting only one of these many “equivalent candidates”.
In [19], the authors showed that such modification could significantly increase the performance of the  algorithm.

§.§.§ Aggressive Selection strategy

In [1], the authors relaxed the selection criteria of POHs and proposed an aggressive version.
The main idea is to select and divide at least one hyper-rectangle from each group of different diameters $(\delta_k^i)$ with the lowest value of the function.
<Ref> formalizes the strategy for identifying an aggressive set of potentially optimal hyper-rectangles from the current partition.
(Aggressive selection)

Let $ \mathbf{c}^i $, $f(\mathbf{c}^i)$, and $ \delta^i_k $ be defined as in <Ref>.
Let $\mathbb{I}_k^i \subseteq \mathbb{I}_k$ be the subset of indices corresponding to hyper-rectangles having the same measure $(\delta_k^i)$.
The notation $\mathbb{I}^{\rm min}_k$ corresponds to the subset of hyper-rectangle indices that has the smallest measure $\delta_k^{\rm min}$, while $\mathbb{I}^{\rm max}_k $ has the largest measure $(\delta_k^{\rm max})$, and $\mathbb{I}_k =  \mathbb{I}^{\rm min}_k \cup \dots \cup \mathbb{I}^{\rm max}_k $.

Then for each subset, $ \mathbb{I}_k^i \ (\min \le i \le \max) $, find hyper-rectangle(s) $ \bar{D}^h_k, h \in \indexsett_k^i $ with the lowest function value among all of the same measure $ (\delta^i_k) $, i.e.,

\begin{eqnarray}
f(\mathbf{c}^h) & \leq & f(\mathbf{c}^l), \quad \forall l \in \indexsett_k^i. \label{eqn:potOptRectAggr}
\end{eqnarray}

For the situation presented in <Ref>, using <Ref>, two additional hyper-rectangles from the groups where the original selection (see <Ref>) does not consider are selected.
From the Lipschitz optimization point of view, such an approach may seem less favorable since it explores non-potentially optimal hyper-rectangles.
There is no such positive constant $\tilde{L}$ value, using which the lower Lipschitz bound would have the lowest values for these additional candidates selected by an aggressive strategy.

§.§.§ Improved aggressive selection strategy

In [14], the authors introduced an improvement to aggressive selection.
They showed that by limiting the refinement of the search space when the measure of hyper-rectangles $ (\delta^i_k )$ reached some prescribed limit $ \delta^{\rm limit} $, the memory usage might be reduced from $10 \%$ to $70 \%$.
Therefore, the improved aggressive version can run longer without memory allocation failure.
We note that in our experimental part (described in <Ref>), the limit parameter $ (\delta^{\rm limit}) $ for algorithms using this selection scheme was set to the measure of a hyper-rectangle that has been subdivided $ 50 n $ times (same as in [45]).

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

In our recent extension,  [48], we introduced a new two-step-based approach to identify the extended set of POHs, formally stated in <Ref>.

(Two-step Pareto selection)

Find all Pareto optimal hyper-rectangles that are non-dominated on size (the higher, the better) and center point function value (the lower, the better), and all non-dominated on size and distance from the current minimum point (the closer, the better).
Then take the unique union of these two identified sets of candidates.

Unlike the aggressive strategy (<Ref>), using <Ref>, hyper-rectangles from the groups where the minimum objective function value is higher than the minimum value from the larger groups are not selected.
Compared to the original selection (<Ref>), using <Ref>, the set of POHs is enlarged by adding more medium-sized hyper-rectangles.
In this sense, Pareto selection may be more global.
Additionally, in the second step, the hyper-rectangles that are non-dominated with respect to the size and distance from the current minimum point are selected.
Therefore, the set of POHs is enlarged with various size hyper-rectangles nearest the current minimum point.

Summary of selection schemes typically used in -type algorithms (in ascending order of the year of publication)

Notation $\&$ source     Identification of POH     Final selection of POH

OS (Jones et. al, 1993)     Original Selection strategy using <Ref>.     Selects all candidates which satisfies <Ref>.

AS (Baker et. al, 2000)     Aggressive Selection strategy using <ref>.     Selects all candidates which satisfies <Ref>.

IO (Gablonsky et. al, 2001)     Improved Original selection strategy using <Ref>.     Selects only one hyper-rectangle if there is a tie for the lowest function value in the same diameter group.

IA (He et. al, 2008)     Improved Aggressive selection strategy using <ref>, but limiting the selection of candidates to some prescribed limit $(\delta^{\rm limit})$.     Selects only one hyper-rectangle if there is a tie for the lowest function value in the same diameter group and $\delta^i_k \ge \delta^{\rm limit}$.

GL (Stripinis et. al, 2018)     Two-step-based (Global-Local) Pareto selection using <Ref>.     Selects only one hyper-rectangle if there is a tie for the lowest function value or distance from the current minimum point.

§.§ Brief review of sampling and partitioning schemes

This subsection briefly reviews some of the primary sampling and partitioning techniques proposed in the  literature.
A summary of them is given in <Ref>, including illustrative examples.

§.§.§ Hyper-rectangular partitioning based on 1-dimensional trisection and center sampling

In [18], Jones proposed a revised version of the original  algorithm.
One of the main algorithmic changes was made to the partitioning scheme.
The author suggested trisecting selected POHs only along the longest side (coordinate).
If there are several equal longest sides, the dimension that has been split the fewest times during the search procedure is selected.
If there is a tie on the latter criterion, the lowest indexed dimension is selected.
In [19], the authors experimentally justified that such modification can significantly improve the performance of the original  algorithm.

Summary of sampling and partitioning schemes typically used in the -type algorithms (in ascending order of the year of publication)

Notation & Source     Partitioning scheme     Sampling scheme     Illustrative example

N-DTC (Jones et. al, 1993)     Hyper-rectangular partitioning based on N-Dimensional Trisection.     Sampling points are located at the Center points of each hyper-rectangle.

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1) ;
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (1/3, 0) (1/3, 1) (2/3, 1) (2/3, 0);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (1/3, 1/3) (1/3, 2/3) (1, 2/3) (1, 1/3);
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.1mm] (axis cs:0, 0) rectangle (axis cs:1/3, 1);
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.1mm] (axis cs:2/3, 1/3) rectangle (axis cs:1, 2/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/2, 1/2);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1/6, 1/2);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (5/6, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/2, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/2, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 5/6);

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1) ;
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:0, 1/3) rectangle (axis cs:1, 2/3);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:7/9, 1/3) rectangle (axis cs:8/9, 2/3);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:7/9, 4/9) rectangle (axis cs:8/9, 5/9);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:1/3, 0) rectangle (axis cs:2/3, 1);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/2, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/6, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/2, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/2, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/6, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/6, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 11/18);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 7/18);
[only marks,mark=o, mark size=1.25pt,black] coordinates (17/18, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (13/18, 1/2);

1-DTC (Jones et. al, 2001)     Hyper-rectangular partitioning based on 1-Dimensional Trisection.     Sampling points are located at the Center points of each hyper-rectangle.

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:1/3, 0) rectangle (axis cs:2/3, 1);
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.1mm] (axis cs:0, 0) rectangle (axis cs:1/3, 1);
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.1mm] (axis cs:2/3, 1/3) rectangle (axis cs:1, 2/3);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:2/3, 1/3) rectangle (axis cs:1, 2/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/2, 1/2);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1/6, 1/2);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (5/6, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 5/6);

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1) ;
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:0, 1/3) rectangle (axis cs:1/3, 2/3);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:2/3, 1/3) rectangle (axis cs:1, 2/3);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:2/3, 4/9) rectangle (axis cs:1, 5/9);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:1/3, 0) rectangle (axis cs:2/3, 1);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/2, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/6, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/6, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/6, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 11/18);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 7/18);

1-DTDV (Sergeyev et. al, 2006)     Hyper-rectangular partitioning based on 1-Dimensional Trisection.     Sampling points are located at two Diagonal Vertices of each hyper-rectangle.

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:1/3, 0) rectangle (axis cs:2/3, 1);
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.1mm] (axis cs:0, 0) rectangle (axis cs:1/3, 1);
[black, thick, mark size=0.1pt, fill=blue!40,opacity=0.4,line width=0.1mm] (axis cs:2/3, 1/3) rectangle (axis cs:1, 2/3);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:2/3, 1/3) rectangle (axis cs:1, 2/3);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (0, 0);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1/3, 1);
[only marks,mark=o, mark size=1.25pt,black] coordinates (2/3, 0);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1, 1);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (2/3, 2/3);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1, 1/3);

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1) ;
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:0, 1/3) rectangle (axis cs:1/3, 2/3);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:2/3, 1/3) rectangle (axis cs:1, 2/3);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:7/9, 1/3) rectangle (axis cs:8/9, 2/3);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:1/3, 0) rectangle (axis cs:2/3, 1);
[only marks,mark=o, mark size=1.25pt,black] coordinates (0, 0);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/3, 1);
[only marks,mark=o, mark size=1.25pt,black] coordinates (2/3, 0);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1, 1);
[only marks,mark=o, mark size=1.25pt,black] coordinates (2/3, 2/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (0, 2/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/3, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (7/9, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (8/9, 2/3);

1-DTCS (Paulavišius et. al, 2014)     Simplicial partitioning based on 1-Dimensional Trisection.     Sampling points are located at the Center points of each Simplex.

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/3, 1/3) (1, 0) (2/3, 2/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/3, 1/3) (0, 1) (2/3, 2/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/3, 0) (2/3, 0) (1/3, 1/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (2/3, 2/3) (1, 0) (1, 1);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (1/3, 0) (1/3, 1/3);
[thick,black,fill=blue!40,opacity=0.4,line width=0.1mm] coordinates (2/3, 0) (1, 0) (1/3, 1/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (2/3, 0) (1, 0) (1/3, 1/3);
[thick,black,fill=blue!40,opacity=0.4,line width=0.1mm] coordinates (0, 0) (0, 1) (1/3, 1/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (0, 1) (1/3, 1/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (2/3, 2/3) (0, 1) (1, 1);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (2/3, 1/3);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1/3, 2/3);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (4/9, 1/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (8/9, 5/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (2/9, 1/9);
[only marks,mark=*, mark size=1.25pt,blue]   coordinates (6/9, 1/9);
[only marks,mark=*, mark size=1.25pt,blue]   coordinates (1/9, 4/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (5/9, 8/9);

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/3, 1/3) (1, 0) (2/3, 2/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/3, 1/3) (0, 1) (2/3, 2/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/3, 0) (2/3, 0) (1/3, 1/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (2/3, 2/3) (1, 0) (1, 1);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (1/3, 0) (1/3, 1/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (2/3, 0) (1, 0) (1/3, 1/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (0, 1) (1/3, 1/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (2/3, 2/3) (0, 1) (1, 1);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (0, 1/3) (1/3, 1/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 2/3) (0, 1) (1/3, 1/3);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (2/3, 0) (1, 0) (7/9, 1/9);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (2/3, 0) (5/9, 2/9) (1/3, 1/3);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (2/3, 1/3);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1/3, 2/3);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (4/9, 1/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (8/9, 5/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (2/9, 1/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (6/9, 1/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1/9, 4/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (5/9, 8/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1/9, 2/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1/9, 6/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (22/27, 1/27);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (14/27, 5/27);

1-DBVS (Paulavišius et. al, 2014)     Simplicial partitioning based on 1-Dimensional Bisection.     Sampling points are located at Vertices of each Simplex.

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[thick,black,fill=blue!40,opacity=0.4,line width=0.1mm] coordinates (0, 0) (1/2, 1/2) (0, 1);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/2, 1/2) (1, 1/2) (1, 1);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/2, 1/2) (0, 1) (1, 1);
[thick,black,fill=blue!40,opacity=0.4,line width=0.1mm] coordinates (0, 0) (1/2, 0) (1/2, 1/2);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/2, 0) (1, 0) (1/2, 1/2);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/2, 1/2) (1, 0) (1, 1/2);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (0, 1) (1/2, 1/2);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (1/2, 0) (1/2, 1/2);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (0, 0);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (0, 1);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1, 0);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1, 1);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1/2, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1, 1/2);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1/2, 0);

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/2, 1/2) (1, 1/2) (1, 1);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/2, 0) (1, 0) (1/2, 1/2);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (1/2, 1/2) (1, 0) (1, 1/2);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (0, 1) (1/2, 1/2);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (1/2, 0) (1/2, 1/2);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (0, 1/2) (1/2, 1/2);
[thick,patch,mesh,draw,black,line width=0.1mm] coordinates (0, 0) (1/2, 0) (1/4, 1/4);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (0, 0);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (0, 1);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1, 0);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1, 1);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1/2, 1/2);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1, 1/2);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1/2, 0);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (0, 1/2);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1/4, 1/4);

1-DBDP (Paulavišius et. al, 2016)     Hyper-rectangular partitioning based on 1-Dimensional Bisection.     Sampling points are located at two Diagonals Points equidistant between themselves and a diagonal's vertices.

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick,fill=blue!40,opacity=0.4, mark size=0.1pt,line width=0.1mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1/2);
[black, thick,fill=blue!40,opacity=0.4, mark size=0.1pt,line width=0.1mm] (axis cs:0, 1/2) rectangle (axis cs:1/4, 1);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:0, 0) rectangle (axis cs:1, 1/2);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:0, 1/2) rectangle (axis cs:1/4, 1);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1/3, 1/3);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1/6, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (2/3, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/3, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/12, 2/3);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1/12, 5/6);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1/6, 2/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (2/3, 2/3);

[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.1mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:0, 0) rectangle (axis cs:1, 1/2);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:0, 0) rectangle (axis cs:1/4, 1);
[black, thick, mark size=0.1pt,line width=0.1mm] (axis cs:0, 1/2) rectangle (axis cs:1/4, 3/4);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/3, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/6, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (2/3, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/3, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/12, 2/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/12, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/6, 2/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 5/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (2/3, 2/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/12, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/12, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/12, 7/12);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/6, 11/12);

§.§.§ Hyper-rectangular partitioning based on 1-dimensional trisection and sampling on diagonal vertices

Adaptive diagonal curves () based algorithm was proposed in [39].
Independently of the dimension,  evaluates the objective function $f(\mathbf{x})$ on two vertices of the main diagonals.
By sampling two points per hyper-rectangle, such a partitioning scheme reduces the chance that the algorithm samples two bad points in the same hyper-rectangle containing an optimal solution.
Thus, better performance could be expected, especially on more complex problems.
Moreover, such a scheme has a significant advantage over center sampling methods when most solution coordinates are located on the boundaries [45].
As in the revised version of  [18], each selected POH is trisected along just one of the longest sides.

§.§.§ Simplicial partitioning based on 1-dimensional trisection/bisection and sampling at center/vertices

In  [31], simplicial partitions are considered instead of hyper-rectangles.
At the initialization step, the unit hyper-rectangle $\bar{D}$ is partitioned into $n!$ simplices by the standard face-to-face simplicial division based on combinatorial vertex triangulation [31].
After this, all simplices share the diagonal of the feasible region and have equal hyper-volume.
In [31], two different sampling and partitioning strategies were proposed: i) evaluating the objective function at the geometric center point of the simplex and trisecting them (1-DTCS); ii) evaluating the objective function on all unique vertices of the simplex and bisecting them (1-DBVS).
While simplicial partitions are very promising for symmetric [31] and problems with linear constraints [32] for box-constrained, they are less appealing as the number of initial simplices increases speedily with the number of dimensions.

§.§.§ Hyper-rectangular partitioning based on 1-dimensional bisection and sampling at two diagonal points

One of the most recent proposals,  (secting angles) [26], is also motivated by the diagonal partitioning strategy [39, 40, 42].
However, the objective function is evaluated at two points on the diagonal that are equidistant between themselves and the vertices of the diagonal.
Such a sampling strategy enables the reuse of the sampling points in descendant hyper-rectangles.
Moreover, the bisection is used instead of the typical trisection for diagonal-based algorithms and most -type algorithms.

§ DESCRIPTION OF THE  ALGORITHM

Unlike most -type algorithms based on central sampling combined with trisection,  (HALving RECTangles) is based on a unique multi-point sampling technique combined with a halving (bisection).
We first give a high-level illustration of the sampling and partitioning techniques used in the  algorithm.
We illustrate them on a binary tree (see <Ref>).
Note that the value of the function was evaluated at more than one sampling point at each POH (except the initial hyper-rectangle).
The experimental part shows that much more comprehensive information about the objective function over hyper-rectangles can be exploited efficiently and positively impact the algorithm's performance.
In contrast to the authors of the original , who proposed trisection, bisection combined with central sampling can also be a very efficient combination.
In the following subsections, we detail the main steps of the  algorithm.

at (0,1.5) Initialization;
[draw,	minimum width=2cm, minimum height=2cm, line width=1pt] at (0,0) ;
[black] (0,0) circle (2pt);
[dashed, line width=1pt] (0,1) – (0,-1);
[draw,	minimum width=1cm, minimum height=2cm, line width=1pt] at (-3,-2) ;
[black] (-3,-2) circle (2pt);
[black] (-2.5,-2) circle (2pt);
[dashed, line width=1pt] (-3.5,-2) – (-2.5,-2);
[draw,	minimum width=1cm, minimum height=2cm, line width=1pt] at (3,-2) ;
[black] (3,-2) circle (2pt);
[black] (2.5,-2) circle (2pt);
[dashed, line width=1pt] (3.5,-2) – (2.5,-2);
[dashed, line width=1pt] (-5,-4.5) – (-5,-3.5);
[draw,	minimum width=1cm, minimum height=1cm, line width=1pt] at (-5,-4) ;
[draw,	minimum width=0.5cm, minimum height=1cm, line width=1pt] at (-5.25,-6) ;
[draw,	minimum width=0.5cm, minimum height=1cm, line width=1pt] at (-2.75,-6) ;
[draw,	minimum width=1cm, minimum height=1cm, line width=1pt] at (-1,-4) ;
[draw,	minimum width=1cm, minimum height=1cm, line width=1pt] at (5,-4) ;
[draw,	minimum width=1cm, minimum height=1cm, line width=1pt] at (1,-4) ;
[black] (-5.25,-6) circle (2pt);
[black] (-5,-6) circle (2pt);
[black] (-5,-5.5) circle (2pt);
[black] (-2.75,-6) circle (2pt);
[black] (-3,-6) circle (2pt);
[black] (-3,-5.5) circle (2pt);
[black] (-2.5,-5.5) circle (2pt);
[black] (-5,-4) circle (2pt);
[black] (-5,-3.5) circle (2pt);
[black] (-4.5,-3.5) circle (2pt);
[black] (-1,-4) circle (2pt);
[black] (-0.5,-4.5) circle (2pt);
[black] (-1,-4.5) circle (2pt);
[black] (5,-4) circle (2pt);
[black] (5,-4.5) circle (2pt);
[black] (4.5,-4.5) circle (2pt);
[black] (1,-4) circle (2pt);
[black] (0.5,-3.5) circle (2pt);
[black] (1,-3.5) circle (2pt);
[line width=1pt, ->] (-1,0) – node[anchor=south,yshift=-0.15cm] 26Iteration 1 (-2.9,-0.9);
[line width=1pt, ->] (1,0)  – node[anchor=south,yshift=-0.15cm] -26Iteration 1 (2.9,-0.9);
[line width=1pt, ->] (-2.5,-1.5) – node[anchor=south,xshift=0.15cm,yshift=-0.45cm] -53Iteration 2 (-1.1,-3.4);
[line width=1pt, ->] (-3.5,-2.5) – node[anchor=south,xshift=-0.1cm,yshift=-0.3cm] 33Iteration 2 (-4.9,-3.4);
[line width=1pt, ->] (3.5,-1.5) – node[anchor=south,xshift=0.15cm,yshift=-0.4cm] -53Iteration 3 (4.9,-3.4);
[line width=1pt, ->] (2.5,-2.5) – node[anchor=south,xshift=-0.15cm,yshift=-0.35cm] 33Iteration 3 (1.1,-3.4);
[line width=1pt, ->] (-4.5,-4) – node[anchor=south,xshift=0.2cm,yshift=-0.4cm] -38Iteration 3 (-2.65,-5.4);
[line width=1pt, ->] (-5.25,-4.5) – node[anchor=south,xshift=-0.6cm,yshift=-1cm] 90Iteration 3 (-5.25,-5.4);

Sampling and partitioning techniques used in the  algorithm illustrated as a binary tree

§.§ Initialization phase

Like others, the  algorithm begins by scaling the feasible region $D$ to an $n$-dimensional unit hyper-rectangle $\bar{D}_0^1$.
It only refers to the initial space $D$ when evaluating the objective function $f(\mathbf{x})$.
The selection of POH in the initialization phase is trivial, as only one candidate is available.
However, in the subsequent iterations, the selection of  POHs is not trivial, and <Ref> is devoted to formalizing this.

§.§ Partitioning and sampling scheme

Like other -type algorithms,  samples and evaluates the objective function at midpoints (in the initial phase at $\mathbf{c}^1 \in \bar{D}_0^1 $).
However, unlike most other algorithms,  uses bisection instead of trisection.
As a result, midpoints, after bisection, shift in different facets of the hyper-rectangle.

Moreover, all these sampling points can be involved in the POHs selection process.
This way, more detailed information about each hyper-rectangle is considered.
<Ref> illustrates the selection, sampling, and subdivision procedures in the initialization and the subsequent first two iterations of  for two- and three-dimensional test problems.

group style=

group size=3 by 1,

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

vertical sep=0pt,
horizontal sep=15pt,

xlabel = $c_1$,
ylabel = $c_2$,
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$,
[black, thick, mark size=0.1pt,fill=blue!40,opacity=0.4] (axis cs:0,0) rectangle (axis cs:1,1);
[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.5, 0.5)  node[yshift=-10pt] $\mathbf{c}^1$ ;
[patch,mesh,draw,black,patch type=rectangle] coordinates
(0,0) (1,0) (1,1) (0,1);
xlabel = $c_1$,
title=Iteration $1$,
ylabel style=yshift=-0.6cm,
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$,
[black, thick, mark size=0.1pt,fill=blue!40,opacity=0.4] (axis cs:0,0) rectangle (axis cs:0.5,1);
[only marks,mark=*,mark size=3pt,color=black] coordinates (0.5, 0.5)  node[xshift=10pt] $\mathbf{c}^1$ ;
[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.25, 0.5)  node[yshift=-10pt] $\mathbf{c}^2$ ;
[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.75, 0.5)  node[yshift=-10pt] $\mathbf{c}^3$ ;
[patch,mesh,draw,black,patch type=rectangle] coordinates
(0,0) (1,0) (1,1) (0,1)
(0,0) (0.5,0) (0.5,1) (0,1);
xlabel = $c_1$,
title=Iteration $2$,
ylabel style=yshift=-0.6cm,
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$,
[black, thick, mark size=0.1pt,fill=blue!40,opacity=0.4] (axis cs:1,0) rectangle (axis cs:0.5,1);
[black, thick, mark size=0.1pt,fill=blue!40,opacity=0.4] (axis cs:0,0) rectangle (axis cs:0.5,0.5);
[only marks,mark=*,mark size=3pt,color=black] coordinates (0.5, 0.5)  node[xshift=10pt] $\mathbf{c}^1$ ;
[only marks,mark=*,mark size=3pt,color=black] coordinates (0.25, 0.5)  node[yshift=-10pt] $\mathbf{c}^2$ ;
[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.75, 0.5)  node[yshift=-10pt] $\mathbf{c}^3$ ;
[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.25, 0.25)  node[yshift=-10pt] $\mathbf{c}^4$ ;
[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.25, 0.75)  node[yshift=-10pt] $\mathbf{c}^5$ ;
[patch,mesh,draw,black,patch type=rectangle] coordinates
(0,0) (1,0) (1,1) (0,1)
(0,0) (0.5,0) (0.5,1) (0,1)
(0,0) (0.5,0) (0.5,0.5) (0,0.5);

group style=

group size=3 by 1,

x descriptions at=edge bottom,

vertical sep=0pt,
horizontal sep=20pt,

xlabel = $c_1$,
ylabel = $c_2$,
zlabel = $c_3$,
xlabel style=xshift=0.2cm,yshift=0.2cm,
ylabel style=yshift=0.3cm,
zlabel style=yshift=-0.2cm,
ytick distance=1/6,
xtick distance=1/6,
ztick 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$,
zticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
3[patch,patch type=rectangle,fill=blue!20,opacity=0.4] coordinates
(0,0,0) (1,0,0) (1,1,0) (0,1,0)
(0,0,0) (1,0,0) (1,0,1) (0,0,1)
(1,0,0) (1,1,0) (1,1,1) (1,0,1)
(1,1,0) (1,1,1) (0,1,1) (0,1,0)
(0,1,0) (0,1,1) (0,0,1) (0,0,0)
(0,0,1) (1,0,1) (1,1,1) (0,1,1)
3[style=thick,mark=none,color=black] coordinates (0,0,0) (0,0,1) (0,1,1) (1,1,1) (1,1,0) (1,0,0) (0,0,0) (0,0,1) (1,0,1) (1,0,0) (1,0,1) (1,1,1);
3[style=dotted,style=thick,mark=none,color=black] coordinates (0,0,0) (0,1,0) (0,1,1) (0,1,0) (1,1,0);
3[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.5, 0.5, 0.5)  node[yshift=-10pt] $\mathbf{c}^1$;
title=Iteration $1$,

xlabel = $c_1$,
ylabel = $c_2$,
xlabel style=xshift=0.2cm,yshift=0.2cm,
ylabel style=yshift=0.3cm,
zlabel style=yshift=-0.2cm,
ytick distance=1/6,
xtick distance=1/6,
ztick 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$,
zticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
3[patch,patch type=rectangle,fill=blue!20,opacity=0.4] coordinates
(0,0,0) (0.5,0,0) (0.5,1,0) (0,1,0)
(0,0,0) (0.5,0,0) (0.5,0,1) (0,0,1)
(0.5,0,0) (0.5,1,0) (0.5,1,1) (0.5,0,1)
(0.5,1,0) (0.5,1,1) (0,1,1) (0,1,0)
(0,1,0) (0,1,1) (0,0,1) (0,0,0)
(0,0,1) (0.5,0,1) (0.5,1,1) (0,1,1)
3[style=thick,mark=none,color=black] coordinates
(0,0,0)   (0,0,1)   (0,1,1) (0.5,1,1)
(0.5,0,1) (0.5,0,0) (0.5,0,1) (0.5,1,1)
(1,1,1)   (1,1,0)   (1,0,0)   (0,0,0)
(0,0,1)   (1,0,1)   (1,0,0)   (1,0,1)
3[style=dotted,style=thick,mark=none,color=black] coordinates
(0,0,0)   (0,1,0)   (0,1,1)   (0,1,0)
(0.5,1,0) (0.5,0,0) (0.5,1,0) (0.5,1,1)
(0.5,1,0) (1,1,0);
3[only marks,mark=*,mark size=3pt,color=black] coordinates (0.5, 0.5, 0.5)  node[yshift=-10pt] $\mathbf{c}^1$;
3[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.25, 0.5, 0.5)  node[yshift=-10pt] $\mathbf{c}^2$;
3[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.75, 0.5, 0.5)  node[yshift=-10pt] $\mathbf{c}^3$;
title=Iteration $2$,

xlabel = $c_1$,
ylabel = $c_2$,
xlabel style=xshift=0.2cm,yshift=0.2cm,
ylabel style=yshift=0.3cm,
zlabel style=yshift=-0.2cm,
ytick distance=1/6,
xtick distance=1/6,
ztick 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$,
zticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
legend style=draw=none,
legend columns=4,
legend style=at=(0.9,-0.15),font=,
legend style=/tikz/every even column/.append style=column sep=0.5cm]
only marks,mark=*,mark size=3pt,color=blue
New sampling point
only marks,mark=*,mark size=3pt,color=black
Previous sampling point
area legend,fill=blue!40,opacity=0.4
Selected POH
area legend,black,fill=white,opacity=0.5
Unselected region
3[patch,patch type=rectangle,fill=blue!20,opacity=0.4] coordinates
(0,0,0) (0.5,0,0) (0.5,1,0) (0,1,0)
(0,0,0) (0.5,0,0) (0.5,0,0.5) (0,0,0.5)
(0.5,0,0) (0.5,1,0) (0.5,1,0.5) (0.5,0,0.5)
(0.5,1,0) (0.5,1,0.5) (0,1,0.5) (0,1,0)
(0,1,0) (0,1,0.5) (0,0,0.5) (0,0,0)
(0,0,0.5) (0.5,0,0.5) (0.5,1,0.5) (0,1,0.5)
3[patch,patch type=rectangle,fill=blue!20,opacity=0.4] coordinates
(0.5,0,0) (1,0,0) (1,1,0) (0.5,1,0)
(0.5,0,0) (1,0,0) (1,0,1) (0.5,0,1)
(1,0,0) (1,1,0) (1,1,1) (1,0,1)
(1,1,0) (1,1,1) (0.5,1,1) (0.5,1,0)
(0.5,1,0) (0.5,1,1) (0.5,0,1) (0.5,0,0)
(0.5,0,1) (1,0,1) (1,1,1) (0.5,1,1)
3[style=thick,mark=none,color=black] coordinates
(0,0,0)   (0,0,1)     (0,1,1)   (0.5,1,1)
(0.5,0,1) (0.5,0,0.5) (0,0,0.5) (0.5,0,0.5)
(0.5,0,0) (0.5,0,1)   (0.5,1,1) (1,1,1)
(1,1,0)   (1,0,0)     (0,0,0)   (0,0,1)
(1,0,1)   (1,0,0)     (1,0,1)   (1,1,1);
3[style=dotted,style=thick,mark=none,color=black] coordinates
(0,0,0)     (0,1,0)   (0,1,1)     (0,1,0.5)
(0,0,0.5)   (0,1,0.5) (0.5,1,0.5) (0.5,0,0.5)
(0.5,1,0.5) (0,1,0.5) (0,1,0)     (0.5,1,0)
(0.5,0,0)   (0.5,1,0) (0.5,1,1)   (0.5,1,0)

3[only marks,mark=*,mark size=3pt,color=black] coordinates (0.5, 0.5, 0.5)  node[yshift=-10pt] $\mathbf{c}^1$;
3[only marks,mark=*,mark size=3pt,color=black] coordinates (0.25, 0.5, 0.5)  node[yshift=-10pt] $\mathbf{c}^2$;
3[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.75, 0.5, 0.5)  node[yshift=-10pt] $\mathbf{c}^3$;
3[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.25, 0.5, 0.25)  node[yshift=-10pt] $\mathbf{c}^4$;
3[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.25, 0.5, 0.75)  node[yshift=-10pt] $\mathbf{c}^5$;

Illustration of selection, sampling and partitioning schemes used in the  algorithm on two-dimensional (upper part) and three-dimensional (lower part) test problems.

Now let us formalize the sampling and partitioning schemes used in .
In iteration $k$, the current partition ($\mathcal{P}_k$) and hyper-rectangle $(\bar{D}^i_k)$ are defined as in <ref>, where $ \indexsett_k$ is the index set of the current partition.
Additionally, for each hyper-rectangle, we define the representative sampling index set $\mathbb{H}^i_k$ storing the indices $(i)$ of all sampled points $(\mathbf{c}^i)$ within the hyper-rectangle at which the objective function has already been evaluated.
We note that initially sampled midpoints, after subdivision (bisection), change their position and later are located on facets of hyper-rectangles (see <Ref>).

Using these notations, at the initial $(k=0)$ and the first two iterations, the current partition ($\mathcal{P}_k$) and the representative sampling index sets $(\mathbb{H}^i_k)$ are

\begin{align*}
\mathcal{P}_0 &= \{ \bar{D}^1_0 \},  \mathbb{H}^1_0 = \{ 1 \},\\
\mathcal{P}_1 &= \{ \bar{D}^2_1,  \bar{D}^3_1\},  \mathbb{H}^2_1 = \{ 1, 2 \},  \mathbb{H}^3_1 = \{ 1, 3 \},\\
\mathcal{P}_2 &= \{ \bar{D}^3_2,  \bar{D}^4_2, \bar{D}^5_2 \},
\mathbb{H}^3_2 = \{ 1, 3 \}, \mathbb{H}^4_2 = \{ 1, 2, 4 \}, \mathbb{H}^5_2 = \{ 1, 2, 5 \}.
\end{align*}

Selected POHs (<ref> describes the selection process) are bisected only along one coordinate with the maximum side length.
<Ref> describes the procedure used in  to select the branching variable, i.e., coordinate index $(br \in \{1,...,n \})$.

Branching coordinate index selection
[1]

Selected POH $(\bar{D}^i_k)$, new sampling point $(\mathbf{c}^{i} \in \bar{D}^i_k)$, current minimum point $(\mathbf{c}^{\rm min})$;
Branching coordinate index $(br)$ ;
Find all the longest sides (indices of corresponding coordinates)

\begin{equation}
\lambda_1 = \argmax_{j=1,...,n} \left\{ d^i_j = \mid \bar{b}^i_j - \bar{a}^i_j \mid \right\}; \algorithmiccomment{\text{See~\cref{eq:rectangle}}}
\end{equation}

Find the furthest coordinate(s) from $\mathbf{c}^{i}$ to $\mathbf{c}^{\rm min}$

\begin{equation}
\lambda_2 = \argmax_{j \in \lambda_1} \left\{ \mid c^i_{j} - c^{\rm min}_{j} \mid \right\};
\end{equation}

Select the coordinate with the smallest index

\begin{equation}
br = \min_{j \in \lambda_2}{j}.
\end{equation}

Return $br$.

In <Ref>, an illustration of branching variable selection is given in the  algorithm moving from the second to the third iteration.
In the second iteration ($k = 2$), there are two POHs ($\bar{D}^3_2$ and $\bar{D}^4_2$).
For $\bar{D}^3_2$ there is only one longest side (coordinate $j = 2$ with the side length $d^3_2 = 1$), therefore <Ref> returns $br = 2$.
However, for $\bar{D}^3_2$, at Step 1 of <Ref>, both sides are equal, and therefore $\lambda_1 = \{ 1, 2\}$.
Since the midpoint $\mathbf{c}^{4}$ is also a current minimum point $(\mathbf{c}^{\rm min})$, after Step 2, the set $\lambda_2 = \{ 1, 2\}$.
Finally, the coordinate with the smallest index value ($br = 1$) is selected in the third step and returned.

group style=

group size=2 by 1,

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

vertical sep=0pt,
horizontal sep=30pt,

xlabel = $c_1$,
ylabel = $c_2$,
title=Iteration $2$,
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$,
[black, thick, mark size=0.1pt,fill=blue!40,opacity=0.4] (axis cs:1,0) rectangle (axis cs:0.5,1);
[black, thick, mark size=0.1pt,fill=blue!40,opacity=0.4] (axis cs:0,0) rectangle (axis cs:0.5,0.5);
[only marks,mark=*,mark size=3pt,color=black] coordinates (0.5, 0.5)  node[yshift=-10pt,xshift=10pt] $\mathbf{c}^1$;
[only marks,mark=*,mark size=3pt,color=black] coordinates (0.25, 0.5)  node[yshift=-10pt] $\mathbf{c}^{2}$ ;
[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.75, 0.5)  node[yshift=-10pt] $\mathbf{c}^3$ ;
[only marks,mark=*,mark size=3pt,color=brown] coordinates (0.25, 0.25)  node[yshift=-10pt] $\mathbf{c}^4$ ;
[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.25, 0.25)  ;
[only marks,mark=*,mark size=3pt,color=blue] coordinates (0.25, 0.75)  node[yshift=-10pt] $\mathbf{c}^5$ ;
[patch,mesh,draw,black,patch type=rectangle] coordinates
(0,0) (1,0) (1,1) (0,1)
(0,0) (0.5,0) (0.5,1) (0,1)
(0,0) (0.5,0) (0.5,0.5) (0,0.5);
xlabel = $c_1$,
ylabel = $c_2$,
title=Iteration $3$,
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$,
legend style=draw=none,
legend columns=3,
legend style=at=(1.25,-0.2),font=,
legend style=/tikz/every even column/.append style=column sep=0.5cm
only marks,mark=*,mark size=3pt,color=blue
New sampling point
only marks,mark=*,mark size=3pt,color=black
Previous sampling point
only marks,mark=*,mark size=3pt,color=brown
Current minimum $(\mathbf{c}^{\rm min})$
area legend,fill=blue!40,opacity=0.4
Selected POH
area legend,black,fill=white,opacity=0.5
Unselected region
[black, thick, mark size=0.1pt,fill=blue!40,opacity=0.4] (axis cs:0,0.5) rectangle (axis cs:0.5,1);
[black, thick, mark size=0.1pt,fill=blue!40,opacity=0.4] (axis cs:0.25,0) rectangle (axis cs:0.5,0.5);
[only marks,mark=*,mark size=3pt,color=black] coordinates (0.5, 0.5)     node[yshift=-10pt, xshift=10pt] $\mathbf{c}^1$ ;
[only marks,mark=*,mark size=3pt,color=black] coordinates (0.25, 0.5)    node[yshift=-10pt, xshift=10pt] $\mathbf{c}^{2}$ ;
[only marks,mark=*,mark size=3pt,color=black] coordinates (0.75, 0.5)    node[yshift=-10pt] $\mathbf{c}^3$ ;
[only marks,mark=*,mark size=3pt,color=brown] coordinates (0.25, 0.25)   node[yshift=10pt, xshift=10pt] $\mathbf{c}^4$ ;
[only marks,mark=*,mark size=3pt,color=black] coordinates (0.25, 0.25)  ;
[only marks,mark=*,mark size=3pt,color=blue]  coordinates (0.25, 0.75)   node[yshift=-10pt] $\mathbf{c}^5$ ;
[only marks,mark=*,mark size=3pt,color=blue]  coordinates (0.75, 0.25)   node[yshift=-10pt] $\mathbf{c}^6$ ;
[only marks,mark=*,mark size=3pt,color=blue]  coordinates (0.75, 0.75)   node[yshift=-10pt] $\mathbf{c}^7$ ;
[only marks,mark=*,mark size=3pt,color=blue]  coordinates (0.125, 0.25)  node[yshift=-10pt] $\mathbf{c}^8$ ;
[only marks,mark=*,mark size=3pt,color=blue]  coordinates (0.375, 0.25)  node[yshift=-10pt] $\mathbf{c}^9$ ;
[patch,mesh,draw,black,patch type=rectangle]  coordinates
(0,0) (1,0) (1,1) (0,1)
(0,0) (0.25, 0) (0.25,0.5) (0,0.5)
(0,0) (0.5,0) (0.5,1) (0,1)
(0,0) (0,0.5) (1,0.5) (1,0);

Illustration of sampling and partitioning schemes used in the  algorithm on a two-dimensional example moving from the second to the third iteration.

When the branching coordinate $(br)$ is identified, each POH $(\bar{D}^i_k)$ is bisected into two equal smaller hyper-rectangles $\bar{D}^{\rm left}_k$ and $\bar{D}^{\rm right}_k$.
The new midpoints ($\mathbf{c}^{\rm left} \in \bar{D}^{\rm left}_k$ and $\mathbf{c}^{\rm right} \in \bar{D}^{\rm right}_k$) are located at the following positions:

\begin{equation}
\label{eq:leftpoint}
\mathbf{c}^{\rm left} = ( c_1^i, ..., c_{br}^i - \frac{d^i_{br}}{4} ,...,c_n^i ),
\end{equation}

\begin{equation}
\label{eq:rightpoint}
\mathbf{c}^{\rm right} = ( c_1^i, ..., c_{br}^i + \frac{d^i_{br}}{4} ,...,c_n^i ),
\end{equation}

where $\mathbf{c}^i \in \bar{D}^i_k$.
We note that naming new hyper-rectangles and midpoints as the “left” and the “right” is only relative.

Continuing in the same vein, after bisection of $\bar{D}^3_2$, new midpoints are located at:

\[
\mathbf{c}^{\rm left} = \mathbf{c}^{6} = \left( c_1^3, c_{2}^3 - \frac{d^3_{2}}{4} \right) = \left( \frac{3}{4}, \frac{1}{4} \right),
\]

\[
\mathbf{c}^{\rm right} = \mathbf{c}^{7} = \left( c_1^3, c_{2}^3 + \frac{d^3_{2}}{4} \right) = \left( \frac{3}{4}, \frac{3}{4} \right).
\]

After bisection of $\bar{D}^4_2$, new sampling points are located at:

\[
\mathbf{c}^{\rm left} = \mathbf{c}^{8} = \left( c_{1}^4 - \frac{d^4_{1}}{4}, c_2^4 \right) = \left( \frac{1}{8}, \frac{1}{4} \right),
\]

\[
\mathbf{c}^{\rm right} = \mathbf{c}^{9} = \left( c_{1}^4 + \frac{d^4_{1}}{4}, c_2^4 \right) = \left( \frac{3}{8}, \frac{3}{4} \right).
\]

The illustration of sampled search space  after ten iterations using the  algorithm on Sum_of_Powers function is given in <Ref>.

xlabel = $c_1$,
ylabel = $c_2$,
title=2-dimensional case,
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$,
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.25mm] coordinates (0,0)(1,0)(1,1) (0,1);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.25,0.5)(0.75,0.5);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.25,0.75)(0.25,0.25);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.75,0.75)(0.75,0.25);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.865,0.75)(0.635,0.75);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.865,0.25)(0.635,0.25);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.625,0.365)(0.625,0.135);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.375,0.25)(0.125,0.25);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.365,0.75)(0.135,0.75);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.125,0.635)(0.125,0.865);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.125,0.365)(0.125,0.135);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.375,0.365)(0.375,0.135);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.3225,0.125)(0.4275,0.125);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.0725,0.125)(0.1775,0.125);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.0725,0.375)(0.1775,0.375);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.0625,0.0725)(0.0625,0.1775);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.1875,0.0725)(0.1875,0.1775);
[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.04125, 0.0625)(0.08375, 0.0625);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.5, 0.5);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.25, 0.5);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.75, 0.5);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.25, 0.25);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.25, 0.75);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.125, 0.25);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.375, 0.25);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.75, 0.25);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.75, 0.75);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.125, 0.75);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.375, 0.75);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.125, 0.125);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.125, 0.375);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.625, 0.25);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.875, 0.25);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.375, 0.125);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.375, 0.375);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.0625, 0.125);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.1875, 0.125);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.625, 0.75);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.875, 0.75);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.125, 0.625);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.125, 0.875);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.0625, 0.375);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.1875, 0.375);
[only marks,mark=*,mark size=2pt,color=black] coordinates (0.0625, 0.0625);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.0625, 0.1875);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.625, 0.125);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.625, 0.375);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.3125, 0.125);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.4375, 0.125);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.1875, 0.0625);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.1875, 0.1875);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.03125, 0.0625);
[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.09375, 0.0625);

title=3-dimensional case,
xlabel = $c_1$,
ylabel = $c_2$,
zlabel = $c_3$,
xlabel style=xshift=0.2cm,yshift=0.2cm,
ylabel style=yshift=0.3cm,
zlabel style=yshift=-0.2cm,
ytick distance=1/6,
xtick distance=1/6,
ztick 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$,
zticklabels=$0$, $0$,$\frac{1}{6}$, $\frac{1}{3}$, $\frac{1}{2}$, $\frac{2}{3}$, $\frac{5}{6}$, $1$,
3[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.4mm] coordinates
(0,0,0) (1,0,0) (1,1,0) (0,1,0)
(0,0,0) (1,0,0) (1,0,1) (0,0,1)
(1,0,0) (1,1,0) (1,1,1) (1,0,1)
(1,1,0) (1,1,1) (0,1,1) (0,1,0)
(0,1,0) (0,1,1) (0,0,1) (0,0,0)
(0,0,1) (1,0,1) (1,1,1) (0,1,1)
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.25,0.5,0.5) (0.75,0.5,0.5);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.25,0.5,0.25) (0.25,0.5,0.75);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.25,0.25,0.25) (0.25,0.71,0.25);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.75,0.25,0.5) (0.75,0.75,0.5);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.25, 0.25, 0.125) (0.25, 0.25, 0.365);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.75, 0.25, 0.25) (0.75, 0.25, 0.74);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.75, 0.75, 0.26) (0.75, 0.75, 0.74);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.125, 0.25, 0.125) (0.36, 0.25, 0.125);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.125, 0.125, 0.125) (0.125, 0.335, 0.125);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.125, 0.125, 0.0625) 	(0.125, 0.125, 0.1775);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.25, 0.25, 0.75) 	(0.25, 0.71, 0.75);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.25, 0.25, 0.635) 	(0.25, 0.25, 0.865);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.125, 0.0625, 0.0625) 	(0.125, 0.1875, 0.0625);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.0725, 0.0625, 0.0625) 	(0.1775, 0.0625, 0.0625);
3[thick,patch,mesh,draw,black,patch type=line,dashed,line width=0.25mm] coordinates (0.635, 0.25, 0.25) 	(0.865, 0.25, 0.25);
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.5, 0.5, 0.5) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.25, 0.5, 0.5) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.75, 0.5, 0.5) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.25, 0.5, 0.25) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.25, 0.5, 0.75) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.25, 0.25, 0.25) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.25, 0.75, 0.25) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.75, 0.75, 0.5) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.75, 0.25, 0.5) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.25, 0.25, 0.125) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.25, 0.25, 0.375) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.75, 0.25, 0.25) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.75, 0.25, 0.75) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.75, 0.75, 0.25) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.75, 0.75, 0.75) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.125, 0.25, 0.125) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.375, 0.25, 0.125) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.125, 0.125, 0.125) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.125, 0.375, 0.125) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.125, 0.125, 0.0625) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.125, 0.125, 0.1875) ;
3[only marks,mark=*,mark size=2pt,color=black] coordinates (0.25, 0.25, 0.75) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.25, 0.75, 0.75) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.25, 0.25, 0.625) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.25, 0.25, 0.875) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.125, 0.0625, 0.0625) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.125, 0.1875, 0.0625) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.0625, 0.0625, 0.0625) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.1875, 0.0625, 0.0625) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.625, 0.25, 0.25) ;
3[only marks,mark=*,mark size=2pt,color=blue] coordinates (0.875, 0.25, 0.25) ;

The illustration of sampled points after $10$ iterations of the  algorithm using two and three-dimensional Sum_of_Powers functions.

After subdivision, each POH $(\bar{D}^i_k)$ is removed, and two new ones are added to the list that describes the current partition:

\[
\mathcal{P}_{k + 1} = (\mathcal{P}_k \setminus \bar{D}^i_k ) \cup \bar{D}^{\rm left}_k \cup \bar{D}^{\rm right}_k.
\]

Therefore, moving from iteration two to three, hyper-rectangles $\bar{D}^{3}_2$ and $\bar{D}^{4}_2$ are removed from the partition $(\mathcal{P}_{2})$, and new ones are included:

\[
\mathcal{P}_{3} = \{\bar{D}^{5}_3, \bar{D}^{6}_3, \bar{D}^{7}_3, \bar{D}^{8}_3, \bar{D}^{9}_3 \}.
\]

New vectors of the representative index sets $\mathbb{H}^{\rm left}_k$ and $\mathbb{H}^{\rm right}_k$ are constructed based on the set $\mathbb{H}^i_k$ corresponding to the subdivided hyper-rectangle ($\bar{D}^i_k$).
The following rules are used to create them:

\begin{equation}
\label{eq:leftrep}
\mathbb{H}^{\rm left}_k = \{h \in \mathbb{H}^i_k : c_{br}^i \geq c_{br}^h \} \cup \{{\rm left}\},
\end{equation}

\begin{equation}
\label{eq:rightrep}
\mathbb{H}^{\rm right}_k = \{h \in \mathbb{H}^i_k : c_{br}^i \leq c_{br}^h \} \cup \{{\rm right}\}.
\end{equation}

Let us consider the subdivided hyper-rectangle $\bar{D}^{4}_2$, whose representative sampling index set $\mathbb{H}^{4}_2 = \{ 1, 2, 4\}$ (see <Ref>).
Then $\mathbb{H}^{\rm left}_3 $ and $\mathbb{H}^{\rm right}_3 $ consist of:

\[
\mathbb{H}^{\rm left}_3 = \mathbb{H}^{8}_3 = \left\{ h \in \mathbb{H}^4_2 : c_{1}^4 \geq c_{1}^h \right\} \cup \{8\} = \{ 2, 4, 8\},
\]

\[
\mathbb{H}^{\rm right}_3 = \mathbb{H}^{9}_3 = \left\{ h \in \mathbb{H}^4_2 : c_{1}^4 \leq c_{1}^h \right\} \cup \{9\} = \{ 1, 2, 4, 9\}.
\]

In the following subsection, we will show how these representative index sets $(\mathbb{H}^i_k)$ are used to select potentially optimal hyper-rectangles by taking into account up to $2 \times n+1$ objective function values over each hyper-rectangle.
But first we prove that the cardinality of $\mathbb{H}^i_k$ cannot exceed $2n + 1$.

The cardinality of any representative sampling index set $\mathbb{H}^i_k$ is less than or equal to $2 \times n+1$, i.e.,

\begin{equation}\label{eq:coroll}
\max_{i \in \indexsett_k, \forall k}{{\rm card}(\mathbb{H}^i_k) \leq 2 \times n+1}.
\end{equation}

In , selected POHs are bisected only along one coordinate with the maximum side length.
Without loss of generality, assume that $br = 1$, i.e., the branching (bisection) on the $x_1$ variable takes place.
As a result, the midpoint, after bisection, shifts on the “left” and on the “right” facet of two newly created hyper-rectangles (see the middle part for two and three-dimensional illustrations in <Ref>).
This way, each subdivided hyper-rectangle cuts off the old facet and replaces it with a new one.
Therefore, only one point can appear on one facet concerning the branching variable.

Throughout the search process (as the number of iterations $k$ increases), all this will be applied to other branching variables ($x_2, \dots, x_n$) too.
From this follows, that the set $\mathbb{H}^i_k$ is constructed only by points located in the hyper-rectangular facets and one midpoint.
As each hyper-rectangle contains $2 \times n$ facets, the maximal number of $2 \times n + 1$ points can be included in $\mathbb{H}^i_k$.

§.§ Selection of potentially optimal hyper-rectangles

Since the objective function in the  algorithm is evaluated at multiple points, more comprehensive information about the objective function values can be efficiently integrated into the selection scheme.
In <Ref>, we introduce four different selection schemes implemented in the new  algorithm,
where the main difference is how the value $\mathcal{F}^i_k$ is calculated (see <ref>).

( selection)

Let $ \mathbf{c}^i$ $\in \bar{D}^i_k$ denote the midpoint, $ \mathbf{c}^j \in \bar{D}^i_k, j \in \mathbb{H}^i_k$ denote all sampling points (including $ \mathbf{c}^i $) of hyper-rectangle $(\bar{D}^i_k)$, $ \textrm{card}( \mathbb{H}^i_k ) $ – the cardinality of $(\mathbb{H}^i_k)$, $ \delta^i_k $ be a measure of $ \bar{D}^i_k$, and $\mathcal{F}^i_k$ – aggregated value based on objective function values attained at sampling point(s) whose indices belong to $ \mathbb{H}^i_k $.
Let $ \varepsilon > 0 $ be a positive constant and $f^{\min}$ be the best currently found objective function value.
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}
\mathcal{F}^h_k - \tilde{L}\delta^h_k & \leq & \mathcal{F}^i_k - \tilde{L}\delta^i_k, \quad \forall i \in \indexsett_k, \label{eq:potOptRect1N} \\
\mathcal{F}^h_k - \tilde{L}\delta^h_k & \leq & f^{\min} - \varepsilon \abs{f^{\min}}, \label{eq:potOptRect2N}
\end{eqnarray}

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

\begin{equation}
\label{eq:distanceN}
%\delta^i_k = \frac{1}{2} \left\| {\mathbf{b}}_k^i - {\mathbf{a}}_k^i \right\|,
\delta^i_k = \left\| {\mathbf{b}}_k^i - {\mathbf{a}}_k^i \right\|,
\end{equation}

and $\mathcal{F}^i_k$ is defined in one of the following four ways

\begin{align}
\label{eq:eq1}
%\tag{Midpoint value}
\mathcal{F}^i_k &= f(\textcolor{blue}{\mathbf{c}^i})\\
\label{eq:eq2}
%\tag{Minimum value}
\mathcal{F}^i_k &= \min_{j \in \mathbb{H}^i_k} f(\mathbf{c}^j)\\
\label{eq:eq3}
%\tag{Mean value}
\mathcal{F}^i_k &= \dfrac{1}{\textrm{card}( \mathbb{H}^i_k )} \sum_{j=1}^{\textrm{card}( \mathbb{H}^i_k )} f(\mathbf{c}^j)\\
\label{eq:eq4}
%\tag{Midpoint and minimum value}
\mathcal{F}^i_k &= \frac{1}{2}\left( \min_{j \in \mathbb{H}^i_k} f(\mathbf{c}^j) +  f(\textcolor{blue}{\mathbf{c}^i}) \right)
\end{align}

§.§.§ Midpoint value based selection

<Ref> is typically used in most existing -type algorithmic modifications to select POHs.
Geometrical visualization of the selection scheme used in  was shown in <Ref>.
The same selection scheme could be directly applied using the new sampling and partitioning strategy proposed in , as the midpoint is always included in the sampling set.
It is obtained by using <ref> in <Ref>.

For the illustrative comparison of all selection schemes, we will use partitioned space in the seventh iteration of the  algorithm solving the two-dimensional Bukin6 test function.
The selected POHs using this selection scheme are shown in part  (a) on the right panel of <Ref>.
$Y$-axis shows the objective function values attained at the midpoints $f(\textcolor{blue}{\mathbf{c}^i})$ of hyper-rectangles belonging to the current partition.
These values can also be seen on the left panel of <Ref>.
The apparent drawback is that the midpoints of previously partitioned hyper-rectangles (see black dots on the left panel of <Ref>) are not involved in POH selection anymore.

legend style=draw=none,
legend columns=2,
legend style=at=(1.05,-0.175),font=,
xlabel = $c_1$,
ylabel = $c_2$,
title= partitioning scheme,
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=princetonorange,postaction=pattern=horizontal lines
Using <ref> in Def. <ref>
area legend,black,fill=brown,postaction=pattern=north west lines
Using <ref> in Def. <ref>
area legend,black,fill=sienna,postaction=pattern=north east lines
Using <ref> in Def. <ref>
area legend,black,fill=psychedelicpurple,postaction=pattern=vertical lines
Using <ref> in Def. <ref>
[princetonorange, thick, mark size=0.01pt,line width=0.01mm,postaction=pattern=horizontal lines,opacity=0.3] (axis cs:1/4, 0) rectangle (axis cs:1/2, 1/2);
[princetonorange, thick, mark size=0.01pt,line width=0.01mm,postaction=pattern=horizontal lines,opacity=0.4] (axis cs:1/4, 1/2) rectangle (axis cs:1/2, 3/4);

[brown, thick, mark size=0.01pt,line width=0.01mm,postaction=pattern=north west lines,opacity=0.3] (axis cs:1/4, 0) rectangle (axis cs:1/2, 1/2);
[brown, thick, mark size=0.01pt,line width=0.01mm,postaction=pattern=north west lines,opacity=0.4] (axis cs:1/2, 1/4) rectangle (axis cs:3/4, 1/2);

[sienna, thick, mark size=0.01pt,line width=0.01mm,postaction=pattern=north east lines,opacity=0.4] (axis cs:0, 3/4) rectangle (axis cs:1/4, 1);
[sienna, thick, mark size=0.01pt,line width=0.01mm,postaction=pattern=north east lines,opacity=0.4] (axis cs:5/8, 1/2) rectangle (axis cs:3/4, 5/8);
[sienna, thick, mark size=0.01pt,line width=0.01mm,postaction=pattern=north east lines,opacity=0.3] (axis cs:1/4, 0) rectangle (axis cs:1/2, 1/2);

[psychedelicpurple, thick, mark size=0.01pt,line width=0.01mm,postaction=pattern=vertical lines,opacity=0.4] (axis cs:3/4, 1/2) rectangle (axis cs:1, 3/4);
[psychedelicpurple, thick, mark size=0.01pt,line width=0.01mm,postaction=pattern=vertical lines,opacity=0.4] (axis cs:5/8, 1/2) rectangle (axis cs:3/4, 5/8);
[psychedelicpurple, thick, mark size=0.01pt,line width=0.01mm,postaction=pattern=vertical lines,opacity=0.3] (axis cs:1/4, 0) rectangle (axis cs:1/2, 1/2);

[only marks,mark=*,mark size=2pt,black] coordinates (1/2, 1/2) node[yshift=-7pt, xshift=13pt, font=]  $50.05$;
[only marks,mark=*,mark size=2pt,black] coordinates (1/4, 1/2) node[yshift=-7pt, xshift=14pt, font=]  $100.00$;
[only marks,mark=*,mark size=2pt,black] coordinates (3/4, 1/2) node[yshift=-7pt, xshift=13pt, font=]  $0.10$;
[only marks,mark=*,mark size=2pt,black] coordinates (3/4, 1/4) node[yshift=-7pt, font=]  $122.57$;
[only marks,mark=*,mark size=2pt,black] coordinates (3/4, 3/4) node[yshift=-7pt, xshift=13pt, font=]  $122.57$;
[only marks,mark=*,mark size=2pt,black] coordinates (5/8, 3/4) node[yshift=7pt, font=]  $119.97$;
[only marks,mark=*,mark size=2pt,black] coordinates (7/8, 3/4) node[yshift=7pt, font=]  $120.02$;
[only marks,mark=*,mark size=2pt,black] coordinates (1/4, 1/4) node[yshift=7pt, xshift=13pt, font=]  $158.11$;
[only marks,mark=*,mark size=2pt,black] coordinates (1/4, 3/4) node[yshift=-7pt, xshift=13pt, font=]  $70.71$;
[only marks,mark=*,mark size=2pt,black] coordinates (1/8, 3/4) node[yshift=7pt, font=]  $25.02$;
[only marks,mark=*,mark size=2pt,black] coordinates (3/8, 3/4) node[yshift=7pt, font=]  $96.84$;
[only marks,mark=*,mark size=2pt,blue] coordinates (1/8, 5/8) node[yshift=-7pt, font=]  $90.16$;
[only marks,mark=*,mark size=2pt,blue] coordinates (1/8, 7/8) node[yshift=7pt, font=]  $82.94$;
[only marks,mark=*,mark size=2pt,blue] coordinates (3/4, 1/8) node[yshift=-7pt, font=]  $150.10$;
[only marks,mark=*,mark size=2pt,black] coordinates (3/4, 3/8) node[yshift=7pt, xshift=-13pt, font=]  $86.70$;
[only marks,mark=*,mark size=2pt,blue] coordinates (5/8, 3/8) node[yshift=-7pt, font=]  $90.21$;
[only marks,mark=*,mark size=2pt,black] coordinates (7/8, 3/8) node[yshift=7pt, xshift=13pt, font=]  $90.26$;
[only marks,mark=*,mark size=2pt,blue] coordinates (26/32, 3/8) node[yshift=-7pt, font=]  $87.61$;
[only marks,mark=*,mark size=2pt,blue] coordinates (30/32, 3/8) node[yshift=-7pt, font=]  $94.51$;
[only marks,mark=*,mark size=2pt,black] coordinates (5/8, 5/8) node[yshift=7pt, xshift=-13pt, font=]  $82.99$;
[only marks,mark=*,mark size=2pt,blue] coordinates (5/8, 7/8) node[yshift=7pt, font=]  $147.97$;
[only marks,mark=*,mark size=2pt,blue] coordinates (1/8, 1/4) node[yshift=-7pt, font=]  $175.02$;
[only marks,mark=*,mark size=2pt,blue] coordinates (3/8, 1/4) node[yshift=-7pt, font=]  $143.63$;
[only marks,mark=*,mark size=2pt,blue] coordinates (7/8, 5/8) node[yshift=-7pt, font=]  $83.04$;
[only marks,mark=*,mark size=2pt,blue] coordinates (7/8, 7/8) node[yshift=7pt, font=]  $148.02$;
[only marks,mark=*,mark size=2pt,blue] coordinates (18/32, 5/8) node[yshift=-7pt, font=]  $78.12$;
[only marks,mark=*,mark size=2pt,black] coordinates (22/32, 5/8) node[yshift=-7pt, font=]  $85.78$;
[only marks,mark=*,mark size=2pt,blue] coordinates (22/32, 18/32) node[yshift=-7pt, font=]  $60.03$;
[only marks,mark=*,mark size=2pt,blue] coordinates (22/32, 22/32) node[yshift=7pt, font=]  $105.41$;
[only marks,mark=*,mark size=2pt,blue] coordinates (3/8, 5/8) node[yshift=-7pt, font=]  $43.32$;
[only marks,mark=*,mark size=2pt,blue] coordinates (3/8, 7/8) node[yshift=7pt, font=]  $129.92$;
[patch,mesh,draw,black,patch type=rectangle] coordinates
(0, 0) (1, 0) (1, 1) (0, 1)
(0, 1/2) (1, 1/2) (1, 0) (0, 0)
(1/2, 0) (1/2, 1) (1, 1) (1, 0)
(1/4, 0) (1/4, 1) (0, 1) (0, 0)
(1/4, 3/4) (1/4, 1) (0, 1) (0, 3/4)
(1/4, 3/4) (1/4, 1) (1/2, 1) (1/2, 3/4)
(3/4, 1/4) (3/4, 3/4) (1/2, 3/4) (1/2, 1/4)
(5/8, 1/2) (5/8, 3/4) (3/4, 3/4) (3/4, 1/2)
(5/8, 1/2) (5/8, 5/8) (3/4, 5/8) (3/4, 1/2)
(1, 1/4) (1, 3/4) (1/2, 3/4) (1/2, 1/4)
(3/4, 3/4) (3/4, 1) (1/2, 1) (1/2, 3/4)
(7/8, 1/4) (7/8, 1/2) (1, 1/2) (1, 1/4);

group style=

group size=2 by 2,

x descriptions at=edge bottom,

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

xtick distance=0.15,
ytick distance=50,
ylabel = $f(\textcolor{blue}{\mathbf{c}}^i)$,
ylabel style=yshift=-0.1cm,
[only marks,mark=*,mark size=2.5pt,black!50] coordinates (-0.1,-0.1) ;

[mark=*,mark size=2.5pt,princetonorange] coordinates (-0.1,-0.1) ;

[only marks,mark=*,mark size=2.5pt,black!50] table[x=T,y=Xa] data/POH.txt;
[mark=*,mark size=2.5pt,princetonorange] coordinates (0.5590, 143.6391) (0.3536, 43.3263);
[draw,fill=white] at (rel axis cs: 0.5, 0.875) [l]
Using <ref> in Def. <ref>:

<ref> non-POH <ref> POH ;
[fill=white] at (rel axis cs: 0.1, 0.1) [l] (a) ;
xtick distance=0.15,
ytick distance=50,
ylabel = $\displaystyle\min_{l \in \mathbb{H}^i_k} f(\mathbf{c}^l)$,
ylabel near ticks, yticklabel pos=right,
[mark=*,mark size=2.5pt,brown] coordinates (-0.1,-0.1) ;

[only marks,mark=*,mark size=2.5pt,black!50] table[x=T,y=Xb] data/POH.txt;
[mark=*,mark size=2.5pt,brown] coordinates (0.5590, 50.0500) (0.3536, 0.1000);
[draw,fill=white] at (rel axis cs: 0.5, 0.875) [l]
Using <ref> in Def. <ref>:

<ref> non-POH <ref> POH ;
[fill=white] at (rel axis cs: 0.1, 0.1) [l] (b) ;
xtick distance=0.15,
ytick distance=50,
xlabel = $\delta^i_k$,
ylabel = $\dfrac{1}{\textrm{card}( \mathbb{H}^i_k )} \displaystyle\sum_{l=1}^{\textrm{card}( \mathbb{H}^i_k )} f(\mathbf{c}^l)$,
ylabel style=yshift=0.1cm,
xlabel style=yshift=0.1cm,
[mark=*,mark size=2.5pt,sienna] coordinates (-0.1,-0.1) ;

[only marks,mark=*,mark size=2.5pt,black!50] table[x=T,y=Xc] data/POH.txt;
[mark=*,mark size=2.5pt,sienna] coordinates (0.5590, 112.9507) (0.3536, 59.5588) (0.1768, 57.2273);
[draw,fill=white] at (rel axis cs: 0.5, 0.875) [l]
Using <ref> in Def. <ref>:

<ref> non-POH <ref> POH ;
[fill=white] at (rel axis cs: 0.1, 0.1) [l] (c) ;
xtick distance=0.15,
ytick distance=50,
xlabel = $\delta^i_k$,
ylabel = $\frac{1}{2}\left( \displaystyle\min_{l \in \mathbb{H}^i_k} f(\mathbf{c}^l) +  f(\textcolor{blue}{\mathbf{c}^i}) \right)$,
ylabel near ticks, yticklabel pos=right,
xlabel style=yshift=0.1cm,
[mark=*,mark size=2.5pt,psychedelicpurple] coordinates (-0.1,-0.1) ;

[only marks,mark=*,mark size=2.5pt,black!50] table[x=T,y=Xd] data/POH.txt;
[mark=*,mark size=2.5pt,psychedelicpurple] coordinates (0.5590, 96.8445) (0.3536, 41.5703) (0.1768, 30.0677);
[draw,fill=white] at (rel axis cs: 0.5, 0.875) [l]
Using <ref> in Def. <ref>:

<ref> non-POH <ref> POH ;
[fill=white] at (rel axis cs: 0.1, 0.1) [l] (d) ;

(title) at ($(group c1r1.center)!0.5!(group c2r1.center)+(0,2.75cm)$) Selection of POH using IO on different models;

Two-dimensional illustration (in the seventh iteration of  on Bukin6 test problem) of four different POH selection scheme variations (see <Ref>) implemented in the  algorithm and controlled by <ref>.

§.§.§ Minimum value based selection

The second selection scheme in  is motivated by the   algorithm [26].
Instead of objective function evaluation at midpoints, the sampling and evaluation on the diagonal points equidistant between themselves and the endpoints of a diagonal are used.
Then, in the selection of POHs, the minimum of these two points is used.
In the  case, the best (minimum) function value is used at all the points sampled in the hyper-rectangle $(\bar{D}^i_k)$.
It is obtained by using <ref> in <Ref>.

As more sampling points are used in the lower Lipschitz bound calculation, more information about the objective function is exploited for POH identification, likely to result in faster convergence.
Therefore, on the vertical $y$-axis, instead of function values obtained at the current midpoints, the minimum values attained at all sampled points over a hyper-rectangle $(\min_{j \in \mathbb{H}^i_k} f(\mathbf{c}^j))$ are used (see part (b) on the right side of <Ref>).

For each hyper-rectangle $ \bar{D}^i_k $ the following condition holds

\begin{equation}\label{eq:coroll2}
\min_{j \in \mathbb{H}^i_k} f(\mathbf{c}^j) \le f(\textcolor{blue}{\mathbf{c}^i})
\end{equation}

It follows directly from the definition of $\mathbb{H}^i_k$ (see <Ref>).

§.§.§ Mean value based selection scheme

The third selection scheme implemented in  is motivated by the mean value obtained at diagonal sampling points and proposed in [39].
In the  case, the mean function value is calculated from all sampled points on the hyper-rectangle $(\bar{D}^i_k)$.
It is obtained by using <ref> in <Ref>.
Using this selection scheme, on the vertical $y$-axis, the mean values calculated from objective function values attained at all sampled points over a hyper-rectangle are used (see part (c) on the right side of <Ref>).

§.§.§ Midpoint and minimum values based selection scheme

The final selection scheme (see <ref>) implemented in  combines ideas used in <ref> and <ref> and takes the mean of these two values.
On the vertical $y$-axis, the mean values calculated for each hyper-rectangle using two values: i) the midpoint value $f(\textcolor{blue}{\mathbf{c}^i})$, and ii) the minimum value $\min_{j \in \mathbb{H}^i_k} f(\mathbf{c}^j)$ are used (see part (d) on the right side of <Ref>).

The impact of these four selection schemes on the performance of  is explored in <Ref>.

§.§.§ Reducing the set of selected POHs

It was stated in <Ref> that sometimes, e.g., using <Ref> on symmetric problems, there might exist many POHs with the same measure $\delta_k$ and objective function value, leading to a significant increase of selected “equivalent” POHs per iteration.
This situation can also arise in , mainly when <ref> is used.
Then a good objective function value attained at the vertex can be shared up to $2^n$ hyper-rectangles.

Many authors (see, e.g., [18, 19, 11, 45, 50]) observed that selecting only one from many “equivalent” candidates can significantly increase the performance of  -type algorithms.
Some authors (see, e.g., [1, 11, 18]) did not specify how the only candidate should be selected, while in [48, 50], the authors selected a hyper-rectangle with the largest index value among them.
In the  algorithm, as more sampling points per hyper-rectangle are available, we use a unique strategy to select “the most promising candidate”.
Specifically, we sort in ascending order the objective function values attained at the points belonging to the hyper-rectangle.
Then, if there are two hyper-rectangles of the same size with the same minimum value, we compare the second smallest values and choose the hyper-rectangle with the smaller value.
If the second smallest values are equal, we compare the subsequent ones.

§.§ Algorithmic steps

The complete description of the  algorithm is shown in Algorithm <ref>.
The inputs for the algorithm are the problem ($f$), optimization domain ($D$), and one (or few) stopping criteria: required tolerance ($\varepsilon_{\rm pe}$), the maximal number of function evaluations ($\texttt{M}_{\rm max}$), and the maximal number of iterations ($\texttt{K}_{\rm max}$).
After termination,  returns the value of the objective function found $(f^{\min})$ and the solution point $(\mathbf{x}^{\min})$ together with algorithmic performance measures: final tolerance – percent error $(pe)$, the number of function evaluations $(m)$, and the number of iterations $(k)$.

The  algorithm
[1]
Problem $f$, search domain $D$, and adjustable algorithmic parameters $opt$: tolerance ($\varepsilon_{\rm pe}$), the maximal number of function evaluations ($\texttt{M}_{\rm max}$) and the maximal number of iterations ($\texttt{K}_{\rm max}$);
The best objective function value $f^{\min}$, minimum point $\mathbf{c}^{\min}$, and algorithmic performance measures $pe$, $k$, $m$;

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

Initialize: $\mathbf{c}^1 = (\frac{1}{2},\dots,\frac{1}{2})$, $k=1$, $m=1$ and $pe$;  pe defined in <ref>

Evaluate $f^1 = f(\mathbf{c}^1)$, and set $f^{\min} = f^1$, $\mathbf{c}^{\min} = \mathbf{c}^1$, $\mathbb{H}^1_1 = \{ 1\}$;

$pe > \varepsilon_{\rm pe}$ and $m < \texttt{M}_{\rm max}$ and $k < \texttt{K}_{\rm max}$

Identify the set $S_k \subseteq \mathcal{P}_k$ of POHs applying <ref>;
$\bar{D}^j_k \in {S}_k$
Find the branching coordinate index $(br)$ using <ref>;

Bisect $\bar{D}^j_k$ into two new  hyper-rectangles $\bar{D}^{m+1}_k$ and $\bar{D}^{m+2}_k$;
Create new midpoints $\mathbf{c}^{m+1}$ and $\mathbf{c}^{m+2}$; see <ref>
Construct $\mathbb{H}^{m+1}, \mathbb{H}^{m+2}$; see <ref>

Update the partition set: $\mathcal{P}_k = \mathcal{P}_k \setminus \bar{D}^j_k \cup \bar{D}^{m+1}_k \cup \bar{D}^{m+2}_k$;

$f(\mathbf{c}^{m+1}) \leq f^{\min}$ or $f(\mathbf{c}^{m+2}) \leq f^{\min}$
Update $f^{\min}, \mathbf{c}^{\min}$;

Update performance measures: $k$, $m$ and $pe$;

Return $f^{\min}, \mathbf{c}^{\min}$, and algorithmic performance measures: $k$, $m$ and $pe$.

Like almost all -type algorithms,  performs initialization: normalization of the feasible region, initial evaluation of the objective function at the midpoint, setting initial values for performance measures, and specifying stopping conditions (see Algorithm <ref>, lines <ref>–<ref>).
The main while loop (see Algorithm <ref>, lines <ref>–<ref>) is executed until any specified stopping condition is satisfied.
At the beginning of each iteration, the  algorithm identifies the set of POHs (see Algorithm <ref>, line <ref>).
As noted in the previous section, the  algorithm uses four different approaches controlled by <ref>.
Then, the  algorithm bisects all POHs, samples at new midpoints of created hyper-rectangles and updates performance measures.
In the end, the solution is found, and the performance measures are returned.

§.§ Convergence properties of the  algorithm

The convergence properties of -type algorithms are broadly reviewed and investigated (see, e.g., [8, 20, 26, 27, 39]).
Typically, they belong to the class of “divide the best” methods and have the “everywhere-dense” type of convergence, that is, convergence to each point of the feasible region.
The continuity of the objective function (at least in the neighborhood of global minima) is the only assumption required to ensure convergence.

The convergence of  follows from a logic similar to that of other -type algorithms.
Let us state it formally in <Ref>, when the maximal allowed number of generated trial points, or the maximal number of function evaluations, $\texttt{M}_{\rm max} \rightarrow \infty$.

For any global minima $\mathbf{x}^* \in \bar{D}$ and any $\epsilon > 0$ there exists an iteration number $k_{\epsilon} \ge 1$ and a sampling point $ \mathbf{c}^j \in \bar{D}^{i^{*}}_k \subseteq \bar{D}$, such that

\begin{equation}
\label{theorem_eq}
\max_{j \in \mathbb{H}^{i^{*}}_k}{ \{ \| \mathbf{c}^j - \mathbf{x}^* \| \} } \leq \epsilon.
\end{equation}

In the selection scheme developed in  (see <Ref>), every iteration $(k)$ always selects at least one hyper-rectangle $\bar{D}^{\max}_k \in {S}_k \subseteq \mathcal{P}_k$ from the group of hyper-rectangles with the most extensive measure $\delta_k^{\rm max}$ (see the right panel of <Ref>)

\begin{equation}
\label{theorem_eqau}
\delta_k^{\rm max} = \max_{i \in \indexsett_k}{\{\delta^i_k  \}}.
\end{equation}

From <ref> follows, the hyper-rectangle $\bar{D}^{\max}_k$ with the largest measure $\delta_k^{\rm max}$ will be bisected through the longest coordinate (see <Ref>) in each  iteration.
Since each group $\delta_k$ of distinct measures contains only a finite number of hyper-rectangles, all hyper-rectangles of the group $\delta_k^{\rm max}$ will be partitioned after a sufficient number of iterations.

The procedure will be repeated with a new group of the largest hyper-rectangles.
As a result, after the finite number of iterations, the current partition $\mathcal{P}_k, k \ge k_{\epsilon}$ will have only hyper-rectangles measured $\delta_k^{\rm max} \le \epsilon$, i.e.,

\begin{equation}
\label{theorem_eqaus}
\| \mathbf{b}_k^{i^{\max}} - \mathbf{a}_k^{i^{\max}} \| \leq \epsilon.
\end{equation}

From <ref> follows, the measure $\delta_k^{i^{*}}$ of the hyper-rectangle containing the global minimum $\mathbf{x}^* \in \bar{D}_k^{i^{*}}$ also does not exceed $\epsilon$

\begin{equation}
\label{theorem_eqs}
\| \mathbf{b}_k^{i^{*}} - \mathbf{a}_k^{i^{*}} \| \leq \epsilon.
\end{equation}

Moreover, it is clear, that

\begin{equation}
\label{theorem_eqs2}
\max_{j \in \mathbb{H}^{i^{*}}_k}{ \{ \| \mathbf{c}^j - \mathbf{x}^* \| \} } \leq \delta_k^{i^{*}}.
\end{equation}

Thus, from <ref> follows <ref>.

§ EXPERIMENTAL RESULTS

This section describes the numerical experiments conducted to evaluate the performance of the newly introduced  algorithm and all its modifications by comparing them with other well-known and relevant -type approaches.

In total, we examine twelve variations of .
We compared them with twelve recently introduced -type algorithms [45] available in the most recent version of  [46] using $96$ box-constrained global optimization test problems and their perturbed versions from  [47, 51]  (listed in <Ref> in Appendix <ref>).

In our recent study [45], we stress that the optimization domains $(D)$ for certain test problems were redesigned to eliminate the dominance of particular partitioning schemes.
The exact modified domains are also considered in this paper.
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 the problems and algorithms used in this section are implemented in the Matlab R2022a environment.
All computations were performed using an Intel R Core$^\textit{TM}$ i5-10400 @ 2.90GHz processor and $16$ GB RAM.
All 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^* $, one of the used stopping criteria is based on the percent error:

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

where $ f^* $ is the known global optimum.
Thus if not specified differently, tested algorithms were stopped when the percent error became smaller than the prescribed value equal to $\varepsilon_{\rm pe} = 10^{-2}$ or when the number of function evaluations exceeded the prescribed limit of $10^6$.

Testing results shown in this article are also available in digital form in the  directory of the GitHub repository [46].
The  directory of the same GitHub repository [46] provides the  script for cycling through all  test problems used in this article.
The script can reproduce the results presented here.
In addition, they can be used to compare and evaluate newly developed algorithms.

§.§ Comparison of different selection strategies in

In this section, the impact and comparison of three different selection schemes: Lipschitz-based (using <Ref>), improved aggressive (using <Ref>), and two-step based Pareto (using <Ref>), and four different strategies to obtain an aggregated objective function information over hyper-rectangles (controlled by <ref>) in the performance of  is investigated.
In total, twelve different variations of  are compared.

The results obtained on the entire set of $96$  test problems are summarized in <Ref>.
The best results are highlighted in bold.
In the upper part of this table, the performance of  is given using four strategies to obtain the aggregated information about the objective function ($\mathcal{F}^i_k$).
As can be seen, there is no single superior strategy.
The best average results are obtained with the first strategy based on a single midpoint value (see <ref>).
However, the overall lowest number of unsolved problems (7/96) was obtained with the second strategy.
It is based on the minimum value attained at all sampled points belonging to a certain hyper-rectangle (see <ref>).
Moreover, it performed significantly better on average than the other strategies on low-dimensional $(n \le 4)$ problems.
It can also be seen that the third strategy, based on the mean value (see <ref>), was the worst for practically all summarized  cases.
The best median results were obtained with the fourth strategy (see <ref>), which combines all three strategies, using the arithmetic mean of the estimates used in the first two strategies.

Our recent work [45] showed that combining existing partition and selection schemes into -type algorithms could lead to more efficient ones.
Motivated by this, we have created two different  algorithmic versions,  and , where the original partition strategy is used, but the selection scheme is changed.
Specifically, in , the original Lipschitz lower bounds-based selection scheme (<Ref>) is replaced with the improved aggressive selection (<Ref>) using newly introduced <ref> for the information about the objective function.
Similarly, in , the original  selection scheme is replaced with a two-step-based (Global-Local) Pareto selection (<Ref>).
Consequently, the results obtained on the same testbed are summarized in the middle and bottom parts of <Ref>.
Comparing the influence of <ref> on the performance of three different versions of , we observe that for both  and , the best results for practically all cases are obtained when <ref> is used.
However, in the case of  and , we no longer observe that <ref> is always the worst, as was the case for .
Comparing , , and , we observe that the lowest number of unsolved problems ($2/96$) is obtained using .
It was the best for almost all criteria, except for the median value, where  with <ref> performed the best.

Comparison of  versions based on three different selection schemes: Lipschitz-based (used in ), improved aggressive (used in ), and two-step based Pareto (used in ) and four different strategies to obtain an aggregated objective function information (controlled by <ref>). The performance measured as the number of function evaluations. The best results are marked in bold.
Alg.     Criteria     $\#$ of cases     <ref>     <ref>     <ref>     <ref>

9*90     $\#$ of failed problems	    $96$     $8$     $\mathbf{7}$     $15$     $12$

Median results     $96$     $1,419$     $2,119$     $3,581$     $\mathbf{976}$

Average results     $96$     $\mathbf{127,562}$     $143,909$     $216,933$     $142,403$

Average ($n \leq 4$)     $51$     $30,792$     $\mathbf{7,248}$     $31,456$     $48,456$

Average ($n > 4$)     $45$     $\mathbf{237,918}$     $298,952$     $427,839$     $249,953$

Average (convex)     $30$     $93,018$     $167,616$     $236,137$     $\mathbf{83,835}$

Average (non-convex)     $66$     $143,263$     $\mathbf{133,133}$     $208,204$     $169,024$

Average (uni-modal)     $15$     $62,774$     $159,110$     $221,099$     $\mathbf{60,046}$

Average (multi-modal)     $81$     $142,513$     $\mathbf{140,401}$     $215,972$     $161,408$

9*90     $\#$ of failed problems     $96$     $9$     $9$     $15$     $\mathbf{5}$

Median results     $96$     $1,826$     $1,880$     $2,737$     $\mathbf{1,581}$

Average results     $96$     $114,222$     $124,552$     $194,832$     $\mathbf{62,874}$

Average ($n \leq 4$)     $51$     $43,203$      $10,634$     $13,223$     $\mathbf{3,762}$

Average ($n > 4$)     $45$     $195,668$     $253,895$     $400,948$     $\mathbf{129,952}$

Average (convex)     $30$     $105,963$     $139,058$     $234,394$     $\mathbf{51,166}$

Average (non-convex)     $66$     $117,975$     $117,958$     $176,849$     $\mathbf{68,197}$

Average (uni-modal)     $15$     $65,698$     $127,693$     $250,054$     $\mathbf{62,332}$

Average (multi-modal)     $81$     $125,419$     $123,827$     $182,084$     $\mathbf{63,000}$

9*90     $\#$ of failed problems     $96$     $5$     $7$     $5$     $\mathbf{2}$

Median results     $96$     $\mathbf{1,404}$     $2,564$     $2,185$     $1,520$

Average results     $96$     $64,275$     $107,127$     $65,271$     $\mathbf{41,061}$

Average ($n \leq 4$)     $51$     $25,847$     $10,831$     $4,360$     $\mathbf{3,301}$

Average ($n > 4$)     $45$     $108,401$     $216,503$     $134,399$     $\mathbf{83,929}$

Average (convex)     $30$     $40,343$     $79,374$     $13,521$     $\mathbf{7,055}$

Average (non-convex)     $66$     $75,153$     $119,742$     $88,793$     $\mathbf{56,519}$

Average (uni-modal)     $15$     $24,714$     $116,545$     $65,538$     $\mathbf{18,646}$

Average (multi-modal)     $81$     $73,405$     $104,953$     $65,209$     $\mathbf{46,234}$

Additionally, the operational characteristics [13, 53] using all $96$ test problems from  are reported in <Ref>.

Operational characteristics provide the proportion of test problems that can be solved within a given budget of function evaluations.
<Ref> reveals that all  algorithms based on three different selection schemes and four different strategies for $\mathcal{F}^i_k$ (<ref>) perform similarly when the budget given for the evaluations of objective functions is relatively small ($m \leq 1,000$).
Within this budget, all versions of  could solve approximately half of the test problems.
However, as the number of function evaluations increases (as more complex problems are considered), the dominance of <ref> based versions (especially ) begins to emerge.
At the same time, the worst results come from versions based on <ref>.

legend pos=north west,

title  = Operational characteristics,
xlabel = Function evaluations,
ytick distance=0.1,
xtick distance=10,
ylabel = Proportion of solved problems,

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=brown, 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.25) [l]

<ref> <ref>

<ref> <ref>

<ref> <ref>

<ref> <ref>;

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

[postaction=decoration=markings,mark=between positions 0 and 1 step 0.09 with [circle,draw=black,fill=princetonorange,inner sep=1.5pt,solid] ;,decorate,,princetonorange,line width=0.75pt, loosely dashed] table[x=T,y=DDO] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.09 with [mark=square,draw=black,fill=brown,inner sep=1.5pt,solid] ;,decorate,,brown,line width=0.75pt, loosely dashed] table[x=T,y=DRO] data/Overallass.txt;
[postaction=decoration=markings,mark=between positions 0 and 1 step 0.09 with 	[diamond,draw=black,fill=sienna,inner sep=1.5pt,solid] ;,decorate,,sienna,line width=0.75pt, loosely dashed] table[x=T,y=BIO] 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,,psychedelicpurple,line width=0.75pt, loosely dashed] table[x=T,y=ADO] data/Overallass.txt;

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

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

[line width=0.75pt, loosely dashed, black] coordinates (0.1,0.1) ;

[line width=0.75pt, loosely dotted, black] coordinates (0.1,0.1) ;

[draw,fill=white] at (rel axis cs: 0.15,0.8) [l]

<ref> ;

Operational characteristics of , ,  algorithms based on <ref> (used in the selection scheme) on the whole set of  test problems.

§.§ Comparison of three  variations vs. twelve recent -type algorithms

Based on the results presented in the previous section, the three most promising variations of  algorithms (all based on <ref>) are considered and  compared with twelve different -type global optimization variations introduced in [45].
These twelve -type algorithms have been created by newly combining three known selection schemes: i) Improved Original (IO), ii) Improved Aggressive (IA), and iii) two-step-based (Global-Local) Pareto (GL) (see <Ref>), and four partitioning techniques: i) Hyper-rectangular partitioning based on N-Dimensional Trisection and objective function evaluations at Center points (N-DTC), ii)
Hyper-rectangular partitioning based on 1-Dimensional Trisection and objective function evaluations at Center points (1-DTC), iii) Hyper-rectangular partitioning based on 1-Dimensional Trisection and objective function evaluations at two Diagonal Vertices (1-DTDV), and iv)  Hyper-rectangular partitioning based on 1-Dimensional Bisection and objective function evaluations at two Diagonal Points (1-DBDP) (see <Ref>).

<ref> shows the summarized comparative results on the whole set of $96$ box-constrained test problems from .
In <Ref>, each column corresponds to a -type algorithm based on a different partitioning scheme.
Since each partition scheme was run on $96$ problems using $3$ different selection methods (rows of <Ref>), each -type algorithm based on a certain partition scheme was involved in solving $3 \times 96 = 288$ problems.
As previously, the best results are marked in bold.
We note that the original  algorithm does not have the purpose of adapting the IO scheme designed to reduce the number of “equivalent” hyper-rectangles.
As described in <ref>, the  algorithm internally uses an innovative approach to deal with such cases.

Regardless of the chosen POH selection scheme (IO, IA, GL), the smallest number of unsolved problems was achieved using the  partitioning scheme-based algorithms (, , ).
Summing the results,  partitioning scheme-based algorithms did not solve ($19/288$) of the test cases, while the second and third best partitioning schemes (1-DBDP and N-DTC) based algorithms did not solve ($28/288$) and ($29/282$) cases accordingly.
Naturally, a higher number of solved problems leads to better performance of the  partitioning scheme-based algorithms.

Consequently, the three  partitioning scheme-based algorithms required approximately $31 \%$ and $36 \%$ evaluations of fever functions in comparison to the other two algorithms based on the best partition schemes (1-DBDP and N-DTC) based algorithms.
The most notable difference in the  partitioning scheme was observed when the IA selection scheme was used.
The  algorithm required approximately $57 \%$ and $61 \%$ compared to the two best algorithms (1-DBDP-IA and 1-DTC-IA).

The number of function evaluations and the execution time (in seconds) of three  versions based on <ref> vs. twelve -type algorithms (introduced in [45]) on  test problems. The best results are marked in bold.

2*Criteria / Algorithms     2*$\#$ of cases     5cFunction evaluations        5cExecution time (in seconds)

N-DTC-IO     1-DTC-IO     1-DBDP-IO     1-DTDV-IO            N-DTC-IO     1-DTC-IO     1-DBDP-IO     1-DTDV-IO

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

Average results     $96$     $142,403$     $\mathbf{142,277}$     $211,463$     $146,133$     $227,455$         $ 652.97 $     $ \mathbf{184.77} $     $ 435.49 $     $ 306.43 $     $ 9,533.28 $

Average ($n \leq 4$)     $51$     $48,456$     $43,832$     $42,633$     $\mathbf{41,602}$     $41,990$         $ 317.96 $     $ 180.41 $     $ 321.23 $     $ \mathbf{169.54} $     $ 1,730.39 $

Average ($n > 4$)     $45$     $\mathbf{249,953}$     $254,819$     $403,749$     $265,522$     $438,574$         $ 1,039.72 $     $ \mathbf{193.73} $     $ 572.13 $     $ 465.33 $     $ 18,414.99 $

Average (convex)     $30$     $83,835$     $111,817$     $170,675$     $\mathbf{80,490}$     $171,868$         $ 105.17 $     $ 99.51 $     $ 292.37 $     $ \mathbf{89.43} $     $ 7,204.96 $

Average (non-convex)     $66$     $169,024$     $\mathbf{156,122}$     $230,004$     $175,971$     $252,722$         $ 901.97 $     $ \mathbf{223.53} $     $ 500.55 $     $ 405.06 $     $ 10,591.60 $

Average (uni-modal)     $15$     $60,046$     $60,100$     $\mathbf{57,360}$     $62,016$     $111,547$         $ 55.23 $     $ \mathbf{27.32} $     $ 100.38 $     $ 62.29 $     $ 4, 800.28 $

Average (multi-modal)     $81$     $161,408$     $\mathbf{161,240}$     $247,026$     $165,545$     $254,203$         $ 790.91 $     $ \mathbf{221.11} $     $ 512.83 $     $ 362.77 $     $ 10, 625.50 $

Median results     $96$     $976$     $\mathbf{771}$     $1,198$     $953$     $847$         $ 0.68 $     $ \mathbf{0.17} $     $ 0.27 $     $ 0.30 $     $ 0.75 $

Criteria / Algorithms     $\#$ of cases          N-DTC-IA     1-DTC-IA     1-DBDP-IA     1-DTDV-IA             N-DTC-IA     1-DTC-IA     1-DBDP-IA     1-DTDV-IA

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

Average results     $96$     $\mathbf{62,874}$     $172,805$     $160,691$     $146,887$     $202,694$         $ \mathbf{18.67} $     $ 21.43 $     $ 69.06 $     $ 33.59 $     $8,580.81$

Average ($n \leq 4$)     $51$     $\mathbf{3,762}$     $25,968$     $23,638$     $45,643$     $9,785$         $ \mathbf{1.09} $     $ 2.74 $     $ 4.10 $     $ 14.03 $     $16.80$

Average ($n > 4$)     $45$     $\mathbf{129,952}$     $339,791$     $316,541$     $262,640$     $421,539$         $ \mathbf{38.61} $     $ 42.67 $     $ 142.76 $     $ 56.07 $     $18,287.05$

Average (convex)     $30$     $\mathbf{51,166}$     $149,711$     $126,030$     $109,374$     $153,594$         $ 19.06 $     $ \mathbf{17.65} $     $ 51.27 $     $ 24.62 $     $7,204.24$

Average (non-convex)     $66$     $\mathbf{68,197}$     $183,302$     $176,446$     $163,939$     $225,012$         $ \mathbf{18.49} $     $ 23.15 $     $ 77.14 $     $ 37.67 $     $9,206.52$

Average (uni-modal)     $15$     $\mathbf{62,332}$     $108,068$     $78,226$     $73,957$     $111,805$         $ 20.90 $     $ \mathbf{9.61} $     $ 30.50 $     $ 15.28 $     $4,800.43$

Average (multi-modal)     $81$     $\mathbf{63,000}$     $187,744$     $179,722$     $163,717$     $223,668$         $ \mathbf{18.15} $     $ 24.15 $     $ 77.95 $     $ 37.82 $     $9,453.20$

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

Criteria / Algorithms     $\#$ of cases          N-DTC-GL     1-DTC-GL     1-DBDP-GL     1-DTDV-GL             N-DTC-GL     1-DTC-GL     1-DBDP-GL     1-DTDV-GL

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

Average results     $96$     $\mathbf{41,061}$     $71,488$     $62,475$     $65,442$     $71,319$         $ 16.31 $     $ \mathbf{9.10} $     $ 38.12 $     $ 21.25 $     $ 3,907.79 $

Average ($n \leq 4$)     $51$     $\mathbf{3,301}$     $9,675$     $7,073$     $41,300$     $5,772$         $ \mathbf{0.63} $     $ 1.08 $     $ 1.09 $     $ 14.33 $     $ 10.68 $

Average ($n > 4$)     $45$     $\mathbf{83,929}$     $141,753$     $125,417$     $93,714$     $145,733$         $ 34.09 $     $ \mathbf{18.21} $     $ 80.11 $     $ 29.41 $     $ 8,324.75 $