GENDIRECT: a GENeralized DIRECT-type algorithmic framework for derivative-free global optimization

GENDIRECT: A generalized DIRECT-type algorithmic framework for DFGO

Linas Stripinis Remigijus Paulavičius

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

R. Paulavičius

Over the past three decades, numerous articles have been published discussing the renowned  algorithm (DIvididing RECTangles).
These articles present innovative ideas to enhance its performance and adapt it to various types of optimization problems.
To consolidate and summarize this progress, we have recently introduced —a comprehensive collection featuring more than fifty deterministic, derivative-free algorithmic implementations based on the  framework.
empowers users to conveniently employ diverse -type algorithms, enabling efficient solutions to practical optimization problems.
Despite their variations, -type algorithms share a common algorithmic structure and typically differ only at certain steps.

Recognizing this, we take further steps in generalization within this paper and propose —eralized -type framework that encompasses and unifies -type algorithms under a single generalized approach.
offers a practical alternative to the creation of yet another “new” -type algorithm that closely resembles existing ones. Instead,  allows the efficient generation of known or novel -type optimization algorithms by assembling different algorithmic components.
This approach provides considerably more flexibility compared to both the  toolbox and individual -type algorithms.
In general,  allows the creation of approximately a few hundred thousand combinations of -type algorithms, facilitating user-friendly customization and the incorporation of new algorithmic components for further advancements.

By modifying specific components of five highly promising -type algorithms found in the existing literature using , the significant potential of  has been demonstrated.
The resulting newly developed improved approaches exhibit greater efficiency and enhanced robustness in dealing with problems of varying complexity.

90C26 65K10

§ INTRODUCTION

Optimization problems encountered in scientific and engineering domains often involve objective functions that can only be obtained through “black-box” methods or simulations, lacking derivative information.
For example, Google's internal services frequently employ black-box optimization techniques with automated parameter tuning engines [10].
Furthermore, objective function evaluations are becoming more computationally expensive as applications grow in size and complexity [22].
Consequently, calculating derivatives is often infeasible or impractical.
As a result, there is a growing emphasis on the development of derivative-free global optimization (DFGO) methods.
These methods are specifically designed to address the growing complexity and diversity of optimization problems, where derivative information is neither available nor practical to compute.
This active development of DFGO methods addresses the need for efficient optimization techniques in scenarios where derivatives cannot be utilized.

This paper considers a box-constrained single-objective 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 potentially “black-box” Lipschitz-continuous objective function with an unknown Lipschitz constant, and $\mathbf{x} \in \mathbb{R}^n$ is the input vector of control variables.
Moreover, $f$ can be non-linear, multi-modal, non-convex, and non-differentiable.
We assume that $f$ can only be computed at any point of the feasible region, which is a $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\}.
\]

However, there is no access to additional information on the objective function $f(\mathbf{x})$, such as gradients and the Hessian, as is typical for a “black-box” case.

Among the solution techniques available for a given problem (<ref>), population-based meta-heuristic methods have gained widespread popularity.
Numerous approaches have been proposed and developed within this category [2].
For global optimization problems that involve costly evaluations, model-based optimization algorithms are commonly employed.
Among these algorithms, Bayesian optimization [18] and various surrogate models[21] stand out as the leading state-of-the-art methods for optimizing expensive "black-box" functions.

[17] presents an alternative specifically tailored for “black-box” global optimization by extending the classical Lipschitz optimization [36, 38, 39, 41], eliminating the requirement of knowing the Lipschitz constant.
In contrast to the stochastic methods discussed above, the -type algorithms adhere to a deterministic pattern.
A recent comprehensive numerical benchmark study involving various derivative-free global optimization solvers[45] highlighted that particularly for problems with lower dimensions, -type algorithms can significantly outperform stochastic approaches.
Furthermore, certain combinations of hybrid local search algorithms based on -type methods and finite differences [42] demonstrated exceptional efficiency in solving high-dimensional problems.
Consequently, designing and developing efficient -type algorithms is crucial and driven by practical needs.

Inspired by these observations, we have recently introduced , a  toolbox dedicated to DFGO.
The latest release of  includes a comprehensive collection of 52 distinct algorithmic implementations based on the  framework.
However, recent empirical studies [50, 51] have highlighted that even more efficient -type algorithms can be achieved by innovatively combining existing algorithmic steps.
It seems that many authors may not spend enough time exploring the most suitable algorithmic framework when developing and publishing new algorithms of type .

Therefore, this study introduces a novel framework called , which offers a eralized -type approach to derivative-free global optimization.
enables the construction of any known or previously unexplored -type algorithm.
Instead of developing yet another “new” -type algorithm,  provides a rapid and effective way of combining different components to create customized -type algorithms.

Using , users can identify and utilize the most suitable -type algorithm for a given optimization problem based on the latest advances in the field.
Compared to the  toolbox and individual -type algorithms, the  framework offers a significantly higher level of flexibility.
In fact,  allows the design of a few hundred thousand combinations of -type algorithms and facilitates user-friendly experimentation with new algorithmic components.

is implemented as a separate extension of , complemented by a dedicated graphical user interface (GUI).
This GUI provides easy access to all the features and capabilities of , ensuring a seamless user experience.

The capability of  is showcased by selecting five highly promising -type algorithms from the existing literature, as identified in [45, 52].
By leveraging , specific components that were identified as weaknesses in these algorithms are modified.
As a result, some of these algorithms demonstrate significantly improved efficiency, showcasing the potential of  in optimizing and refining -type algorithms using the most recent .

This work makes several significant contributions, including

* Introduction of a novel framework called , which represents a eralized -type algorithmic framework.

*  provides an efficient and innovative approach to generate -type optimization algorithms, whether they are existing algorithms or entirely novel ones, by combining different algorithmic components.

*  allows for the creation of a few hundred thousand combinations of -type algorithms, facilitating user-friendly experimentation and enabling new developments in optimization.

* Description of the implementation of  as an evolution of , complete with a separate graphical user interface (GUI) that ensures easy access to all its features. This implementation is free and open for anyone to use.

* Demonstration of the potential of  by enhancing the efficiency of five chosen -type algorithms through modifications. These modifications showcase the ability of  to improve algorithmic performance further.

In summary, this work contributes to the derivative-free global optimization field by introducing , a versatile framework that enables efficient algorithm generation, offers extensive customization options, and shows improved efficiency in established -type algorithms.

The remainder of the paper is organized as follows.
<Ref> presents a concise overview of key advancements in the realm of -type algorithms.
<Ref> introduces and elaborates on the  framework.
The experimental results of the newly developed algorithms and performance evaluation utilizing  are analyzed in <Ref>.
Lastly, <Ref> offers concluding remarks and outlines potential avenues for future exploration in this field.

§ BACKGROUND FOR

§.§ General structure of -type algorithms

The  algorithm was originally designed to solve global optimization problems with box constraints (<ref>).
Despite numerous proposals, most follow a similar algorithmic structure and involve three primary steps: selection, sampling, and partitioning (see <Ref>).
However, at first, -type algorithms typically transform a feasible region $D = [\mathbf{a}, \mathbf{b}]$ into a unit hyper-rectangle $ \bar{D} = [0, 1]^n$ referring to the original space $(D)$ solely to evaluate the objective function $f$ (as depicted in  <Ref>, Lines <ref>–<ref>).

The selection, partitioning, and sampling operations are executed within a normalized search domain $ \bar{D} $.
During each iteration, specific regions are identified as potentially optimal candidates (POC) and chosen for further investigation (see <Ref>, Line <ref>).
In -type algorithms, the objective function is sampled and evaluated at various points within each POC, which are then subdivided into smaller sub-regions (see Algorithm <ref>, Lines <ref> and <ref>).
This selection, sampling, and subdivision process continues until a predefined limit is reached.

The subsequent subsections provide an overview of the primary techniques proposed for each step.
Although the selection step precedes sampling and partitioning, we will initially focus on the latter because the selection step relies directly on the strategies employed in sampling and partitioning.

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

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

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

Evaluate $f$ at initial sampling point(s) and set:

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

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

Initialize performance measures: $k=1$, $m=1$ ;

$f^{\rm goal} < f^{\min}$ $m < \Mmax$ $k < \Kmax$
Selection step: Identify the set $S_k$ of POCs

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

Partitioning step: Subdivide $\bar{D}^j_k$

Run local search procedure;*[f]only in hybrid version

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

Return $f^{\min}, \mathbf{x}^{\min}$, and performance measures $(k, m)$.
Main steps of -type algorithms

§.§ Summary of sampling and partitioning schemes

In this section, we present a brief summary of seven primary sampling and partitioning approaches that have been proposed in existing literature  [17, 16, 40, 37, 33, 52] and implemented within the  framework.
<Ref> provides an overview of these schemes, including illustrative examples from the initial iterations.
Blue-colored sub-regions indicate the POCs in the current partition.

Although each of the seven schemes possesses distinct characteristics, they demonstrate significant similarities.
Particularly, these schemes involve sampling new points and subdividing larger regions into smaller, non-overlapping sub-regions.
In cases where there is more than one longest side, two primary strategies for division emerge:

* Subdivision along all dimensions with the maximum side length.

* Subdivision along a single dimension with maximum side length.

It is worth mentioning that the original  algorithm proposed subdividing along all dimensions.
However, extensive experimentation has indicated that this approach does not consistently yield effective results.

Summary of sampling and partitioning schemes commonly utilized in -type algorithms implemented within  (in ascending order of the year of publication)

Notation & Source     Partitioning and sampling scheme     An example of the initialization and two subsequent iterations

DTC [16]      A hyper-rectangular partition based on one-Dimensional Trisection, and sampling points located at Centers.

[group style=group size=3 by 1,horizontal sep=3pt]            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick, mark size=0.1pt, fill=blue!30,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1) ;
[only marks,mark=*, mark size=1.25pt,black] coordinates (1/2, 1/2);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick, mark size=0.1pt, fill=blue!30,line width=0.2mm] (axis cs:2/3, 0) rectangle (axis cs:1, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1) ;
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (1/3, 0) (1/3, 1) (2/3, 1) (2/3, 0);
[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=*, mark size=1.25pt,blue]  coordinates (5/6, 1/2);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick, mark size=0.1pt, fill=blue!30,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/3, 1);
[black, thick, mark size=0.1pt, fill=blue!30,line width=0.2mm] (axis cs:2/3, 1/3) rectangle (axis cs:1, 2/3);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1) ;
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (1/3, 0) (1/3, 1) (2/3, 1) (2/3, 0);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (2/3, 1/3) (2/3, 2/3) (1, 2/3) (1, 1/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);

DTDV [40]     A hyper-rectangular partition based on one-Dimensional Trisection, and sampling points located at two Diagonal Vertices.

[group style=group size=3 by 1,horizontal sep=2.5pt]            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick, mark size=0.1pt, fill=blue!30,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (0, 0);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1, 1);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick, mark size=0.1pt, fill=blue!30,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/3, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick, mark size=0.1pt,line width=0.2mm] (axis cs:1/3, 0) rectangle (axis cs:2/3, 1);
[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);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick, mark size=0.1pt, fill=blue!30,line width=0.2mm] (axis cs:1/3, 0) rectangle (axis cs:2/3, 1);
[black, thick, mark size=0.1pt, fill=blue!30,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/3, 1/3);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1) ;
[black, thick, mark size=0.1pt,line width=0.2mm] (axis cs:0, 1/3) rectangle (axis cs:1/3, 2/3);
[black, thick, mark size=0.1pt,line width=0.2mm] (axis cs:1/3, 0) rectangle (axis cs:2/3, 1);
[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=*, mark size=1.25pt,blue] 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 (0, 2/3);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/3, 1/3);

DTCS [37]     A simplicial partition based on one-Dimensional Trisection, and sampling points located at Centers of Simplices.

[group style=group size=3 by 1,horizontal sep=3pt]            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[thick,black,fill=blue!30,line width=0.2mm] coordinates (0, 0) (0, 1) (1, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0,0)(1,0)(1,1)(0,1);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (0, 0) (0, 1) (1, 1);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (2/3, 1/3);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (1/3, 2/3);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[thick,black,fill=blue!30,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1);
[thick,black,fill=blue!30,line width=0.2mm] coordinates (0, 0) (0, 1) (1/3, 1/3);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0,0)(1,0)(1,1)(0,1);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (1/3, 1/3) (0, 1) (2/3, 2/3);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (0, 0) (0, 1) (1, 1);
[only marks,mark=*, mark size=1.25pt,blue]  coordinates (2/3, 1/3);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (1/3, 2/3);
[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); [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[thick,black,fill=blue!30,line width=0.2mm] coordinates (0, 0) (1/3, 1/3) (1, 0);
[thick,black,fill=blue!30,line width=0.2mm] coordinates (0, 0) (1/3, 1/3) (0, 1/3);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0,0)(1,0)(1,1)(0,1);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (1/3, 1/3) (0, 1) (2/3, 2/3);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (1/3, 1/3) (1, 0) (2/3, 2/3);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (0, 0) (0, 1) (1, 1);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (0, 1/3) (1/3, 1/3) (0, 2/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=*, mark size=1.25pt,blue]  coordinates (4/9, 1/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (8/9, 5/9);
[only marks,mark=*, mark size=1.25pt,blue]  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 (1/9, 4/9);
[only marks,mark=o, mark size=1.25pt,black]  coordinates (5/9, 8/9);

DBVS [37]     A simplicial partition based on one-Dimensional Bisection, and sampling points located at Vertices of Simplices.

[group style=group size=3 by 1,horizontal sep=2.5pt]            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[thick,black,fill=blue!30,line width=0.2mm] coordinates (0, 0) (0, 1) (1, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (0, 0) (0, 1) (1, 1);
[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=*, mark size=1.25pt,blue] coordinates (1, 1);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[thick,black,fill=blue!30,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1);
[thick,black,fill=blue!30,line width=0.2mm] coordinates (0, 0) (0, 1) (1/2, 1/2);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (0, 0) (0, 1) (1, 1);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (0, 0) (0, 1) (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=*, mark size=1.25pt,blue] coordinates (1, 0);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/2, 1/2);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[thick,black,fill=blue!30,line width=0.2mm] coordinates (0, 0) (1, 0) (1/2, 1/2);
[thick,black,fill=blue!30,line width=0.2mm] coordinates (0, 0) (0, 1/2) (1/2, 1/2);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (0, 0) (0, 1) (1, 1);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (0, 0) (0, 1) (1, 0);
[thick,patch,mesh,draw,black,line width=0.2mm] coordinates (0, 0) (0, 1/2) (1/2, 1/2);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (0, 0);
[only marks,mark=o, mark size=1.25pt,black] coordinates (0, 1);
[only marks,mark=*, mark size=1.25pt,blue] 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=*, mark size=1.25pt,blue] coordinates (0, 1/2);

DBDP [33]     A hyper-rectangular partition based on one-Dimensional Bisection, and sampling points located at two Diagonal Points equidistant between themselves and a diagonal's vertices.

[group style=group size=3 by 1,horizontal sep=3pt]            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/3, 1/3);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (2/3, 2/3);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/3, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (2/3, 2/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (5/6, 1/3);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/6, 2/3);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:1/2, 0) rectangle (axis cs:1, 1);
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1/2);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/3, 1/3);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (2/3, 2/3);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (5/6, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/6, 2/3);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/6, 1/6);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/3, 5/6);

DBVD [4]     A hyper-rectangular partition based on one-Dimensional Bisection, and sampling points located at one Vertice and one Diagonal point with a 2:3 diagonal distance from the sampling vertice.

[group style=group size=3 by 1,horizontal sep=2.5pt]            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/3, 1/3);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1, 1);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/3, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1, 1);
[only marks,mark=o, mark size=1.25pt,black] coordinates (2/3, 1/3);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (0, 1);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:1/2, 0) rectangle (axis cs:1, 1);
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1/2);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/3, 1/3);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (2/3, 1/3);
[only marks,mark=o, mark size=1.25pt,black] coordinates (0, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (0, 0);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/3, 2/3);

DBC [52]     A hyper-rectangular partition based on one-Dimensional Bisection, and sampling points located at Center points.

[group style=group size=3 by 1,horizontal sep=3pt]            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/2, 1/2);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/2, 1/2);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/4, 1/2);
[only marks,mark=o, mark size=1.25pt,black] coordinates (3/4, 1/2);            [width=0.25,height=0.25,ytick=,xtick=,enlargelimits=0]
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:1/2, 0) rectangle (axis cs:1, 1);
[black, thick,fill=blue!30, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1/2);
[thick,patch,mesh,draw,black,patch type=rectangle,line width=0.2mm] coordinates (0, 0) (1, 0) (1, 1) (0, 1);
[black, thick, mark size=0.1pt,line width=0.2mm] (axis cs:0, 0) rectangle (axis cs:1/2, 1);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/2, 1/2);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/4, 1/2);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (3/4, 1/2);
[only marks,mark=*, mark size=1.25pt,blue] coordinates (1/4, 1/4);
[only marks,mark=o, mark size=1.25pt,black] coordinates (1/4, 3/4);

§.§ Selection schemes

Initially, selecting POCs is straightforward since only one candidate is available, the entire feasible region.
However, to introduce selection schemes in subsequent iterations, we must first establish the concept of the current partition $(\mathcal{P}_k)$, which in iteration $k$, is defined as

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

where $ \bar{D}^i_k $ are hyper-rectangles (or simplices) and $ \indexsett_k $ is the index set identifying the current partition $ \mathcal{P}_k $.
Then, the next partition, $\mathcal{P}_{k+1}$, is obtained by subdividing the selected POCs from the current partition $ \mathcal{P}_k $.

When identifying POCs, two crucial aspects come into play: the $\bar{D}^i_k$ measure $(\bar{\delta}_k^i)$ and the general quality based on the function values attained at the sample points.

§.§.§ Evaluating goodness of candidates

The values of the objective function obtained from the sampled points $\mathbb{H}^i_k$ are utilized to assess the overall quality of the candidate.
We refer to this value as the aggregated function value $(\mathcal{F}_k^i)$, which represents the goodness of $ \bar{D}_k^i$.
In summary, four strategies have been presented to evaluate $\mathcal{F}_k^i$ in the literature [52] as defined in <Ref>.

(Aggregated function values)

* $\bar{\delta}_k^i $ is a measure of $ \bar{D}_k^i$;

* $\mathbf{x}_{\rm m}^i$ is a midpoint of $ \bar{D}_k^i$;

* $\mathbf{x}^{\rm min}$ is a currently best found minimum point;

* $\mathbb{H}^i_k$ is a representative sampling index set of all sample points within $\bar{D}^i_k$;

* $\textrm{card}(\mathbb{H}^i_k)$ is the cardinality of a set $\mathbb{H}^i_k$.

* Midpoint value based aggregated function value:

\begin{equation}
\label{eq:eq1}
\mathcal{F}^i_k = f(\mathbf{x}_{\rm m}^i),
\end{equation}

* Minimum value based aggregated function value:

\begin{equation}
\label{eq:eq2}
\mathcal{F}^i_k = \min_{j \in \mathbb{H}^i_k} f(\mathbf{x}^j)
\end{equation}

* Mean value based aggregated function value:

\begin{equation}
\label{eq:eq3}
\mathcal{F}^i_k = \dfrac{1}{\textrm{card}( \mathbb{H}^i_k )} \sum_{j=1}^{\textrm{card}( \mathbb{H}^i_k )} f(\mathbf{x}^j)
\end{equation}

* Midpoint and minimum values based aggregated function value:

\begin{equation}
\label{eq:eq4}
\mathcal{F}^i_k = \frac{1}{2}\left( \min_{j \in \mathbb{H}^i_k} f(\mathbf{x}^j) +  f(\mathbf{x}_{\rm m}^i) \right)
\end{equation}

The use of the $\mathcal{F}_k^i$ evaluation strategy depends on the specific sampling strategy being utilized.
For example, in the case of the DTC and DTCS schemes, the midpoint value-based $\mathcal{F}_k^i$ is adopted since sampling is performed solely at a single midpoint.

However, when there are multiple sampling points per candidate, alternative strategies have been shown to have a significant influence, as shown in previous work [47].

§.§.§ Measuring candidates

Depending on the sampling strategy, basically only two different ways have been proposed to measure POCs:

\begin{eqnarray}
%\bar{\delta}_k^i &=& \max_{j \in \mathbb{H}^i_k} \| \mathbf{x}^i_{\rm m} - \mathbf{x}^{j} \|_2,\label{eq:diagonal}\\
\bar{\delta}_k^i &=& \lambda d_k^i, \label{eq:diagonal}\\
\bar{\delta}_k^i &=& \max_{j, l \in \mathbb{H}^i_k} \| \mathbf{x}^{j} - \mathbf{x}^{l} \|_2.\label{eq:longside}
\end{eqnarray}

where $\lambda \in [0, 1]$ and $d_k^i$ represents the Euclidean length of the diagonal of $\bar{D}^i_k$ diagonal.
A couple of significant points should be emphasized in this regard.
First, instead of relying solely on the Euclidean norm, alternative norms (e.g., $\| \cdot \|_{\infty}$) have been observed to yield favorable results, as noted in the work [8].
Second, different partitioning schemes have employed various values for $\lambda$.
For example, some schemes use $\lambda = 1$, which corresponds to the full length of the diagonal, as seen in [52], while others adopt $\lambda = 2/3$, as demonstrated in [33].
However, since $\lambda$ applies uniformly to all partition elements $\bar{D}^i_k$ and serves solely to counterbalance the selection of POC, the choice of $\lambda$ does not affect the performance of algorithms of type .

§.§.§ Summary of POC selection schemes

To address the identified limitations of -type algorithms, various POC selection schemes have been proposed.
<Ref> defines the four most widely used and implemented selection schemes in , while a summary of them is given in <Ref>.

(Selection schemes)

* $\mathcal{F}_k^i$ denotes the aggregated function value for $ \bar{D}_k^i$;

* $\bar{\delta}_k^i $ is a measure of $ \bar{D}_k^i$;

* $\mathbb{I}_k^i \subseteq \mathbb{I}_k$ represents a subset of indices that correspond to elements of $\mathcal{P}_k$ sharing the same measure ($\bar{\delta}_k^i$). Additionally, $\mathbb{I}_k^{\rm min}$ contains the indices of elements with the smallest measure, $\bar{\delta}_k^{\rm min}$, while $\mathbb{I}_k^{\rm max}$ — with the largest.

* Original selection: A candidate $ \bar{D}_k^j, j \in \indexsett_k $ is said to be potentially optimal if there exists some rate-of-change (Lipschitz) constant $ \tilde{L} > 0$ such that

\begin{equation}
\label{eqn:potOptRect1}
\mathcal{F}_k^j - \tilde{L}\delta_k^j \leq \mathcal{F}_k^i - \tilde{L}\delta_k^i, \quad \forall i \in \indexsett_k,
\end{equation}

* Aggresive selection: For each $ \mathbb{I}_k^i \ (\min \le i \le \max) $ select $ \bar{D}^j_k, j \in \indexsett_k^i $ with the lowest $\mathcal{F}_k^j$, i.e.,

\begin{equation}
\label{eqn:potOptRectAggr}
\mathcal{F}^j_k \leq \mathcal{F}^l_k, \quad \forall l \in \indexsett_k^i.
\end{equation}

* Pareto selection: Select all candidates $\bar{D}_k^i, i \in \indexsett_k$ who are not dominated, which means that there is no other candidate $\bar{D}_k^j, j \in \indexsett_k$ that satisfies the condition:

\begin{equation}
\label{eq:pareto}
(\delta_k^j \geq \delta_k^i \wedge \mathcal{F}_k^j < \mathcal{F}_k^i) \vee (\delta_k^j > \delta_k^i \wedge \mathcal{F}_k^j \leq \mathcal{F}_k^i).
\end{equation}

* Reduced Pareto selection: Select $ \bar{D}_k^i$ with the lowest $\mathcal{F}_k^i$ and $ \bar{D}_k^j$ with the most extensive measure $\delta_k^j$, breaking ties in favor of a lower value of the aggregate function.

In summary, aggressive selection aims to choose a comprehensive set of candidates, ensuring that at least one candidate is selected from each group with different diameters $(\delta_k^i)$ while prioritizing candidates with the lowest aggregated function value.
Then, the number of candidates selected through Pareto-based criteria tends to exceed the original selection strategy.
However, this approach, which emphasizes exploring candidates of intermediate sizes, can lead to slower convergence, particularly when dealing with less complex optimization problems.
Therefore, the primary motivation behind introducing a reduced set of Pareto-optimal candidates was to address this issue.

It is important to note that when multiple equally good POC exist with the same $\delta_k^i$ and $\mathcal{F}^i_k$, two distinct selection strategies are available:

* Select all equally good POC;

* Select only one with the highest index number.

Furthermore, selection schemes can integrate additional conditions to enhance the balance between local and global directions.
The subsequent subsection provides a detailed examination of these conditions.

Summary of selection schemes implemented in

Notation & Source     Description     Illustration of POCs selection (blue points) using  on the same sample

Original [17]     Original selection strategy. Selects POCs based on the lower Lipschitz bound estimates for all possible Lipschitz constant values.

width=0.465,height=0.3,every axis/.append style=font=,
ymin=-0.05,ymax=0.4,xmin=0,xmax=0.6,ytick distance=0.1,xtick distance=0.15,
ylabel style=yshift=-0.1cm,xlabel style=yshift=0.2cm,clip=false,enlargelimits=0.04,
xlabel=$\delta^i_k$,xlabel style=at=(1.075,-0.075),ylabel=$\mathcal{F}_k^i$,
[only marks,mark=o,mark size=2pt,black!60,domain y=0:0.5] table[x=D,y=F] ddr1.txt;
[only marks,mark=*,mark size=2pt,blue] table[x=DO,y=FO] ddr1.txt;

Aggressive [3]     Aggressive selection strategy. Selects  at least one candidate from each group of different diameters.

width=0.465,height=0.3,every axis/.append style=font=,
ymin=-0.05,ymax=0.4,xmin=0,xmax=0.6,ytick distance=0.1,xtick distance=0.15,
ylabel style=yshift=-0.1cm,xlabel style=yshift=0.2cm,clip=false,enlargelimits=0.04,
xlabel=$\delta^i_k$,xlabel style=at=(1.075,-0.075),ylabel=$\mathcal{F}_k^i$,
[only marks,mark=o,mark size=2pt,black!60,domain y=0:0.5] table[x=D,y=F] ddr1.txt;
[only marks,mark=*,mark size=2pt,blue] table[x=DA,y=FA] ddr1.txt;

Pareto [29]     Pareto selection strategy. Selects all candidates that are non-dominated on size (the higher, the better) and aggregated function value (the lower, the better).

width=0.465,height=0.3,every axis/.append style=font=,
ymin=-0.05,ymax=0.4,xmin=0,xmax=0.6,ytick distance=0.1,xtick distance=0.15,
ylabel style=yshift=-0.1cm,xlabel style=yshift=0.2cm,clip=false,enlargelimits=0.04,
xlabel=$\delta^i_k$,xlabel style=at=(1.075,-0.075),ylabel=$\mathcal{F}_k^i$,
[only marks,mark=o,mark size=2pt,black!60,domain y=0:0.5] table[x=D,y=F] ddr1.txt;
[only marks,mark=*,mark size=2pt,blue] table[x=DP,y=FP] ddr1.txt;

Reduced Pareto [30]     Reduced Pareto selection strategy. Selects only two candidates, the first and the last point on the Pareto front.

width=0.465,height=0.3,every axis/.append style=font=,
ymin=-0.05,ymax=0.4,xmin=0,xmax=0.6,ytick distance=0.1,xtick distance=0.15,
ylabel style=yshift=-0.1cm,xlabel style=yshift=0.2cm,clip=false,enlargelimits=0.04,
xlabel=$\delta^i_k$,xlabel style=at=(1.075,-0.075),ylabel=$\mathcal{F}_k^i$,
[only marks,mark=o,mark size=2pt,black!60,domain y=0:0.5] table[x=D,y=F] ddr1.txt;
[only marks,mark=*,mark size=2pt,blue] table[x=DR,y=FR] ddr1.txt;

§.§.§ Additional approaches for improved local and global POC selection.

Excessive local refinement reduction techniques.
To protect the algorithm against excessive refinement around current local minima $f^{\rm min}$, the authors in the  literature [17, 6, 25] proposed incorporating one of the following conditions along with Eq. (<ref>) in the original selection scheme:

\begin{eqnarray}
\mathcal{F}_k^j - \tilde{L}\delta_k^j &\leq& f^{\rm min} - \varepsilon|f^{\rm min}|,\label{eqn:min}\\
\mathcal{F}_k^j - \tilde{L}\delta_k^j &\leq& f^{\rm min} - \varepsilon|f^{\rm min} - f^{\rm median}|,\label{eqn:median}\\
\mathcal{F}_k^j - \tilde{L}\delta_k^j &\leq& f^{\rm min} - \varepsilon|f^{\rm min} - f^{\rm average}|\label{eqn:average}.
\end{eqnarray}

Therefore, the lower Lipschitz bound of the POC must be lower than the current minimum value $(f^{\rm min})$ to at least some extent.
The parameter $\varepsilon$ plays a crucial role in determining the adjustment of the lower Lipschitz bound.
In the study conducted by [17], favorable results were achieved using values of $\varepsilon$ ranging from $10^{-3}$ to $10^{-7}$, and a default value of $\varepsilon = 10^{-4}$ is suggested.
To reduce the sensitivity of the objective function to additive scaling, subtraction of the median value $(f^{\rm median})$ or the average $(f^{\rm average})$ value (as shown in Eqs. (<ref>) and (<ref>)) was proposed.

Restart technique for the $\varepsilon$ parameter. In [5], an adaptive scheme is introduced for the parameter $\varepsilon$ to prevent wasteful function evaluations in minor regions $\bar{D}^i_k$ where negligible improvements are expected.
The restart technique begins with $\varepsilon = 0$ and is maintained until an improvement is observed.
However, if there is no improvement for five consecutive iterations, it suggests a potential stagnation at a local optimum.
To address this, the algorithm switches to $\varepsilon = 0.01$.
Within 50 iterations, the restart technique returns to $\varepsilon = 0$ if an improvement is found or no progress is made.
If another 50 iterations pass without improvement, this indicates a possible discovery of the global minimum, requiring further refinement.

Multi-level candidate selection using different $\varepsilon$ values. In [26, 24], two alternative multi-level techniques are proposed for the candidate selection procedure, involving three different levels:

* Level 2: The -type algorithm is executed with the usual settings, employing $\varepsilon = 10^{-5}$.

* Level 1: The selection is limited to $90\%$ of $\bar{D}^k_i \in \mathcal{P}^k$, excluding $10\%$ of the candidates with the largest measure. In this level, $\varepsilon = 10^{-7}$ is used.

* Level 0: The selection is limited to $10\%$ of the candidates with the largest measure, disregarding those excluded at level 1. Here, $\varepsilon = 0$ is used.

Both strategies are recommended in the study cycle through these levels using a combination of the “W-cycle”: $21011012$.
One of the methods [26] employs a fixed $\varepsilon = 10^{-4}$ value at all levels, while the other [24] adheres to the rules mentioned above.

Globally-biased selection. In the works [34, 35], a two-phase approach with global bias was introduced.
The algorithm effectively determines the adequacy of exploring a local optimum by employing the globally biased scheme.
It terminates the local phase (referred to as the “usual” phase) to prevent wasteful function evaluations by excessive local refinement.
Upon stopping the usual phase, the algorithm seamlessly transitions into a global phase, wherein the hyper-rectangles chosen for further exploration must meet a minimum size requirement.
This globally biased phase continues until a better minimum point is discovered or a maximum number of “global iterations” is reached.
Subsequently, the algorithm reverts back to the usual phase.
The search process alternates between these two phases, namely, the usual phase and the globally-biased phase, until a specified stopping condition is fulfilled.

Two-phase (Global-Local) selection. In the work [46], a two-phase selection approach has been introduced.
This approach expands the set of previously obtained POCs by incorporating additional candidates based on their proximity to the current best minimum point $\mathbf{x}^{\rm min}$.
This expansion is performed by conducting a selection process using calculated distances (instead of aggregated function values) between the current best minimum point and all other candidates:

\begin{equation}
\label{eq:eq5}
\mathcal{F}^i_k = \| \mathbf{x}_{\rm m}^i - \mathbf{x}^{\rm min} \|_2.
\end{equation}

By including candidates that are closer to the current minimum point, this step facilitates faster and more extensive exploration around the current minimum point.

§.§ Acceleration through hybridization techniques

To our knowledge, three hybridization strategies have been proposed for -type algorithms [16, 27, 14, 35].

The first strategy, originally suggested by the author of the original  [16], was later refined and improved in a work [35].
The concept behind this strategy involves performing a local search only when the algorithm achieves an improvement in the best current solution value, denoted $f^{\rm min}$.
The best current solution $f^{\rm min}$ can be updated using a local search method or a more suitable direct-type algorithm that enables faster local refinement.

The second strategy [14] operates similarly to the first one.
However, instead of performing a local search from a single starting point, this strategy employs a clustering algorithm to identify multiple appropriate starting points.
The following steps are executed within this suggested method:

* The -type algorithm is run for a fixed number of function evaluations, typically set at $100n + 1$ as the default.

* The sampled points are analyzed using an adaptive clustering algorithm to determine the optimal number of clusters. Subsequently, a local search is performed from the best point within each cluster.

* Additionally, the -type algorithm is run again.

* If the -type algorithm improves $f^{\rm min}$, a final local search is performed from the best point.

In the third, aggressive strategy [27], initiate a local search from the midpoint of each POC.
However, this approach has faced significant criticism for potentially generating excessive local searches, as many starting points may converge to the same local optimum.

§  OPTIMIZATION SOFTWARE

This section describes the generalized algorithmic framework .
<Ref>, illustrates the main architecture of the developed .
Specifically, there are three large boxes in <Ref>, which represent the construction of the main -type algorithmic steps within :

* The construction of partitioning and sampling scheme.

* The construction of the selection scheme.

* The construction of a hybridization scheme.

[node distance=1.5cm]
(p2) [scheme] DTC;
(p3) [scheme, right of=p2,xshift=0.15cm] DTDV;
(p4) [scheme, right of=p3,xshift=0.15cm] DTCS;
(p5) [scheme, right of=p4,xshift=0.15cm] DBVS;
(p6) [scheme, right of=p5,xshift=0.15cm] DBDP;
(p7) [scheme, right of=p6,xshift=0.15cm] DBVD;
(p8) [scheme, right of=p7,xshift=0.15cm] DBC;
[fit=(p2)(p3)(p4)(p5)(p6)(p7)(p8),myfit] (myfit1) ;
[mytitle] at (myfit1.north west) Select partitioning and sampling scheme:;

(v1) [dimens, below of=p2,yshift=-0.5cm,xshift=2.6cm] All dimensions with the maximum side length;
(v2) [dimens, right of=v1,xshift=3.25cm] One dimension with the maximum side length;
[fit=(v1)(v2),myfit] (myfit2) ;
[mytitle] at (myfit2.north west) Divide POC $(\bar{D}^i_k)$ along:;

[fit=(myfit1)(myfit2),myfits] (myfit66) ;
[mytitles] at (myfit66.north) Designing partitioning and sampling;

(f1) [aggreg, below of=v1,xshift=1.3cm,yshift=-1.7cm] Eq. (<ref>);
(f2) [aggreg, left of=f1, xshift=0.2cm] Eq. (<ref>);
(f3) [aggreg, left of=f2, xshift=0.2cm] Eq. (<ref>);
(f4) [aggreg, left of=f3, xshift=0.2cm] Eq. (<ref>);
[fit=(f1)(f2)(f3)(f4),myfit] (myfit4) ;
[mytitle] at (myfit4.south west) Select $\mathcal{F}^i_k$:;

(d1) [diamet, right of=f1,xshift=1.4cm] Using Eq. (<ref>);
(d2) [diamet, right of=d1,xshift=1.1cm] Using Eq. (<ref>);
[fit=(d1)(d2),myfit] (myfit3) ;
[mytitle] at (myfit3.north west) Calculate $\delta_k^i$:;

(s1) [select, below of=f4,yshift=-0.5cm, xshift=0.6cm] Original selection;
(s2) [select, right of=s1,xshift=1.4cm] Aggressive selection;
(s3) [select, right of=s2,xshift=1.4cm] Pareto selection;
(s4) [select, right of=s3,xshift=1.4cm] Reduced Pareto selection;
[fit=(s1)(s2)(s3)(s4),myfit] (myfit6) ;
[mytitle] at (myfit6.south west) Select identification of POC strategy:;

(e1) [selegh, below of=s1,yshift=-0.6cm,xshift=1.3cm] Select all equally good POC;
(e2) [selegh, right of=e1,xshift=4.6cm] Select only the one with the highest index number;
[fit=(e1)(e2),myfit] (myfit7) ;
[mytitle] at (myfit7.south west) If several equally good POC exist (the same $\delta_k^i$ and $\mathcal{F}^i_k$):;

(r1) [aggregg, below of=e1,yshift=-1cm,xshift=6.2cm] Eq. (<ref>);
(r2) [aggregg, right of=r1] Eq. (<ref>);
(r3) [aggregg, below of=r1,yshift=0.4cm] Eq. (<ref>);
(r4) [aggregg, right of=r3] none;
[fit=(r1)(r2)(r4)(r3),myfitd] (myfit8) ;
[mytitless] at (myfit8.north west) Select method:;

(r5) [aggregg, left of=r1,xshift=-0.85cm] Restart method;
(r6) [aggregg, below of=r5,yshift=0.4cm] none;
(r7) [aggregg, left of=r5] Multi-level $1$;
(r8) [aggregg, left of=r6] Multi-level $2$;
[fit=(r5)(r6)(r7)(r8),myfitd] (myfit9) ;
[mytitless] at (myfit9.north west) For $\epsilon$ control:;

[fit=(myfit8)(myfit9),myfit] (myfit10) ;
[mytitle] at (myfit10.south west) Use an excessive local refinement reduction technique:;

(g1) [aggreg, left of=r7,xshift=-1.4cm,yshift=0.4cm] no;
(g2) [aggreg, left of=g1] yes;
[fit=(g1)(g2),myfit] (myfit11) ;
[mytitle] at (myfit11.north west) Globally-biased?;

(l1) [aggreg, below of=g1, yshift=-0.4cm] no;
(l2) [aggreg, below of=g2, yshift=-0.4cm] yes;
[fit=(l1)(l2),myfit] (myfit5) ;
[mytitle] at (myfit5.south west) Two-phase step?;

[fit=(myfit6)(myfit10)(myfit3)(myfit4),myfits] (myfit13) ;
[mytitles] at (myfit13.north west) Designing POC selection;

(vv1) [diamest, below of=l1,yshift=-1.65cm,xshift=-0.95cm] Best point;
(vv3) [diamest, below of=vv1,yshift=0.5cm] Each POC;
(vv4) [diamest, right of=vv1,xshift=1.5cm] None;
(vv2) [diamest, below of=vv4,yshift=0.5cm] Each best cluster point;
[fit=(vv1)(vv2)(vv3)(vv4),myfit] (myfit222) ;
[mytitle] at (myfit222.south west) Run local search starting from the:;

(vvv1) [diamest, right of=vv4,xshift=2.15cm] Interior-point;
(vvv2) [diamest, right of=vvv1,xshift=1cm] Sqp;
(vvv3) [diamest, right of=vv2,xshift=2.15cm] Sqp-legacy;
(vvv4) [diamest, right of=vvv3,xshift=1cm] Active-set;
[fit=(vvv1)(vvv2)(vvv3)(vvv4),myfit] (myfit2222) ;
[mytitle] at (myfit2222.south west) Select local search algorithm:;

[fit=(myfit222)(myfit2222),myfits] (myfit21) ;
[mytitles] at (myfit21.north west) Designing hybridization;

[arrow,blue, line width=1pt] (myfit1.south-|myfit2.north) – (myfit2.north);
[arrow,blue, line width=1pt] (myfit11.south) – (myfit5.north);
[arrow,blue, line width=1pt] (myfit4.east) – (myfit3.west);
[arrow,blue, line width=1pt] (myfit3.south) – (myfit6.north-|myfit3.north);
[arrow,blue, line width=1pt] (myfit6) – (myfit7);
[arrow,blue, line width=1pt] (myfit7.south-|myfit8.north) – (myfit10.north-|myfit8.north);
[arrow,blue!40, line width=1pt] (myfit8) – (myfit9);
[arrow,blue, line width=1pt] (myfit11.west-|myfit10.west) – (myfit11.east);
[arrow,black, line width=2pt] (myfit66.south-|s4.north) – (myfit13.north-|s4.north);
[arrow,black, line width=2pt] (myfit13.south) – (myfit21.north);
[arrow,blue, line width=1pt] (myfit222.east) – (myfit2222.west);

A flowchart for constructing -type algorithm in .

The following subsections will provide a detailed exploration of how to effectively utilize  using the  command line interface and the dedicated graphical user interface (GUI).

§.§ Utilizing  through the command line interface.

With , users can swiftly and effectively establish and solve global optimization problems by constructing a -type algorithm via the  command line interface.
All relevant problem information is consolidated into a unified  structure, which is then passed to the solver to extract the required data.

For the  format, the solution process begins by generating the following structure:
alg = GENDIRECT();

The algorithm takes in a structured input that includes the optimization problem, dimension, lower and upper bounds, and a target value (if applicable).
Here is an example code snippet illustrating how these parameters can be set:
alg.Problem.f     = 'objfun';
alg.Problem.n     = n;
alg.Problem.x_L   = zeros(n, 1);
alg.Problem.x_U   = ones(n, 1);
alg.Problem.fgoal = 0.01;
alg.Problem.info  = false;

If the  parameter is set to `true', the algorithm retrieves all the relevant information about the objective function from the `objfun' problem.

As we utilize test problems provided by  [49], the stored information encompasses both the problem structure and the objective function.
Consequently, the algorithms automatically extract all essential details from the given problem, including:

* The dimensionality of the problem;

* The lower and upper bounds for each variable;

* The objective function value of the known solution;

* The solution point.

For further guidance on the utilization of , additional information can be found in references [44, 47].

Users who want to customize the default algorithmic settings should utilize the  structure:
alg.optParam.maxevals = 100;
alg.optParam.maxits   = 100;
alg.optParam.showits  = true;

The next step involves constructing the algorithm using the procedures described in <Ref>.

The parameters of  used to construct -type algorithms, with default values highlighted in blue.

Step     Parameter     Description

Specify partitioning and sampling scheme (see <Ref>): , , , , , , or .

Specify subdivision strategy for multiple longest sides (see <Ref>):   or .

Specify strategy for a aggregated function value:  (Eq. (<ref>)),  (Eq. (<ref>)),  (Eq. (<ref>)) or  (Eq. (<ref>)).

Specify strategy for a measure:  (Eq. (<ref>)), or  (Eq. (<ref>)).

Specify selection scheme (see <Ref>): , , , or .

4*90Selection          Specify behavior for equally good POC:  or .

Specify excessive local refinement reduction technique:  (Eq. (<ref>)),  (Eq. (<ref>)),  (Eq. (<ref>)) or .

Specify the value for $\varepsilon$ (Eqs. (<ref>), (<ref>), (<ref>)): $10^{-4}$.

Specify control technique for $\varepsilon$ (see <Ref>): , ,  or .

Enable globally-biased POC selection (see <Ref>):  or .

Enable two-phase selection of POC using  (Eq. (<ref>))(see <Ref>):  or .

Specify hybridization strategy (see <Ref>): , ,  or .

Specify derivative-free local search subroutine: , ,  or .

Specify the maximum iteration limit for a single local search subroutine call: $1000$.

Specify the maximum function evaluation limit for a single local search subroutine call: $3000$.

After completing these steps, the algorithm is ready to solve the given problem using the following line of code:
Results = alg.solve;

Once the algorithm completes its computations, it returns the  structure, which contains the optimization outcomes.

The subsequent subsections will outline the process of constructing -type algorithmic steps.

§.§.§ Designing partitioning and sampling scheme

To create a combination of -type algorithms, the user needs to integrate components that determine the division and sampling strategy of the optimization domain.
The core framework for constructing the partitioning and sampling strategy is illustrated in the top block of <Ref>.
The subsequent command lines illustrate how to configure the partitioning strategy of the original  algorithm:
alg.Partitioning.Strategy = 'DTC';
alg.Partitioning.SubSides = 'All';

As a result of the given partitioning and sampling scheme in <Ref>, there are $14$ possible combinations in .

§.§.§ Designing the selection scheme

Once the partitioning and sampling strategy has been established, the subsequent task is to determine the POC selection scheme.
Here is an example that illustrates the parameter values required for performing POC selection introduced in the original  algorithm:
alg.Selection.AggrFuncVal = 'Midpoint';
alg.Selection.CandMeasure = 'Diagonal';
alg.Selection.Strategy = 'Original';
alg.Selection.EqualCand = 'All';
alg.Selection.SolRefin = 'Min';
alg.Selection.Ep = 0.0001;
alg.Selection.ControlEp = 'Off';
alg.Selection.GloballyBased = 'Off';
alg.Selection.TwoPhase = 'Off';

When the two-phase selection step is enabled, as demonstrated in the following code snippet:
alg.Selection.TwoPhase = 'On';

the algorithm uses the designed selection scheme ('alg.Selection') to expand the set of promising candidate solutions (POC) based on the calculated distances obtained using Eq. (<ref>).
It is easy to calculate in <Ref>, there are $4096$ different combinations for the selection steps of POC in .

§.§.§ Designing hybridization scheme

In the third block of <Ref>, users are required to select the desired hybridization technique.
There are only $13$ possible combinations available in this block.

For example, to specify a hybridization scheme that utilizes a strategy calling an SQP local search (parameter ) subroutine only when an improvement in the best current solution is achieved (parameter ), the following code can be used:
alg.Hybridization.Strategy = 'Single';
alg.Hybridization.LocalSearch = 'sqp';

§.§ Utilizing  through the graphical user interface

is also accessible through the graphical user interface (GUI) of .
This GUI enables users to use  without requiring prior programming or algorithmic knowledge.
To access the  tool, users can navigate to the  APPS menu on the toolbar.
Within , the generalized  algorithm () can be selected from the algorithm drop-down menu.

The graphical interface of the main toolbox window  is depicted in <Ref>.
The  window is centrally located in the GUI and facilitates the construction of the  algorithm by providing user-friendly functionalities.
For more comprehensive details of , see [47].

A snapshot of the graphical user interface (GUI) of  in the  software package.

§.§ Remarks regarding the extension of

comprises two primary components, as illustrated in <Ref>.
Firstly, a function block encompasses various implementations of the steps involved in -type algorithms.
Secondly, the control structure ensures the seamless connection of algorithm components, facilitating the execution of the algorithm.

If a researcher intends to integrate a newly proposed step into , the function should be added to the function block.
Ensuring that the implemented function adheres to the existing code's style is important.
Subsequently, in the control function of , the newly created function should be incorporated accordingly, allowing  to utilize it effectively.

[node distance=1cm]
(p1) [startstop] Start;
(p2) [aggreg, right of=p1,xshift=3cm,yshift=-0.5cm] *.m;
(p4) [aggreg, below of=p2] *.m;
(p5) [aggreg, below of=p4] *.m;
(p12) [aggreg, right of=p2,xshift=0.9cm] *.m;
(p14) [aggreg, right of=p4,xshift=0.9cm] *.m;
(p15) [aggreg, right of=p5,xshift=0.9cm] *.m;
[fit=(p2)(p4)(p5)(p12),myfits] (myfit1) ;
[mytitles] at (myfit1.north west) Block of functions;
(c1) [dimensss, below of=p1,yshift=-0.5cm] Function responsible for controlling and executing ;
(c2) [startstop, below of=c1,yshift=-0.5cm] End;

[arrow,black, line width=1pt] (p1) – (c1);
[arrow,black, line width=1pt] (c1) – (c2);
[<->,black, line width=2pt] (myfit1.west) – (c1);

The framework of the generalized  algorithm system ()

§ SIMULATION RESULTS AND IN-DEPTH ANALYSIS

This section presents an analysis of the experimental results for newly developed improved algorithms and their performance evaluation using .

§.§ An overview of benchmark test problems

We employed a comprehensive set of $324$ benchmark test functions to thoroughly evaluate the newly proposed  algorithm.
These test problems were sourced from the latest version of the  library [43], which is built within the  environment.
The  integrates ten libraries and collections of well-established and recently developed test problems.

In <Ref>, we present a summary of  and its constituent libraries.
The table provides essential details, including references, publication years, the pool of problems, and the counts of scalable, separable, and multi-modal problems.
Specifically, the table comprises $136$ test problems with fixed dimensions and $188$ test benchmarks that can be adjusted to any dimension size ($n$).
For these test problems, we consider instances with variables set at $n = 2, 5,$ and $10$.
However, it is worth noting that some functions, such as certain CEC functions [23, 55], are not applicable in all dimensions.

In our study, we thoroughly examined a total of $634$ test problems available in  to ensure comprehensive and robust evaluations of the proposed algorithmic framework .

Compilation of test problems from various libraries in the latest version of the  for box-constrained global optimization.

2*Source     2*Year     4cProblems

Total     Scalable     Seperable     Multi-modal

Hedar, [12]     $2005$     $31$     $17$     $8$     $23$

Hansen et al.,[11]     $2009$     $24$     $24$     $5$     $14$

Jamil et al.,[15]     $2013$     $167$     $69$     $49$     $127$

Gavana, [9]     $2013$     $193$     $76$     $64$     $156$

Surjanovic et al., [53]     $2013$     $50$     $23$     $11$     $40$

Liang et al., [23]     $2014$     $27$     $27$     $5$     $24$

Wu et al., [55]     $2017$     $20$     $20$     $0$     $19$

Oldenhuis, [32]     $2020$     $41$     $12$     $5$     $33$

Layeb, [1]     $2022$     $18$     $18$     $2$     $16$

Kudela et al., [20]     $2022$     $8$     $8$     $8$     $8$

Stripinis et al., [43]     $2023$     $324$     $188$     $97$     $261$

In order to ensure that the global minimum point does not coincide with the initial sampling point in any tested algorithm, we employ shift operations.
In other words, we randomly shift the solutions in the $X$-space.
This involves transforming a given point $\mathbf{x}$ into $\hat{\mathbf{x}}$ using the following equation:

\begin{equation}
\label{eq:shift}
\hat{x}_j = \min \left\{ \max \left\{ x_j - \rho_j \lambda \vec{x}_j, a_j \right\}, b_j \right\},~j = 1,...,n.
\end{equation}

Here, $\vec{\mathbf{x}}$ is a randomly distributed random direction vector generated using the Mersenne-Twister pseudorandom generator, and $\lambda$ is a step size that serves two important purposes:

* It prevents the global optima from moving outside of the feasible region.

* It allows for a more efficient placement of the solution within the problem domain, considering that different problems may have significantly different domain sizes.

The value of $\lambda$ is calculated by solving the following linear programming problem:

\begin{equation}
\label{eq:shiftlp}
\begin{aligned}
\max \,\,    & \lambda \\
\text{s.t. } & \mathbf{x}^* + \lambda \vec{\mathbf{x}} \geq \mathbf{a}\\
& \mathbf{x}^* + \lambda \vec{\mathbf{x}} \leq \mathbf{b}\\
\end{aligned}
\end{equation}

The shift operation introduces the possibility of regions outside the original feasible range $[\mathbf{a},\mathbf{b}]$ where, in certain instances, points with lower function values than the global optimum within the original feasible range may exist.
To tackle this issue, the transformed vector $\hat{\mathbf{x}}$ (<ref>) is restricted to lie within the range $[\mathbf{a},\mathbf{b}]$ using min-max functions.

Nevertheless, one drawback of this approach is that the functions become “flat” in areas where the min-max restriction is applied.
These flat regions increase in size as the value of $\lambda$ increases.
To address this concern, we opted to limit the range of the randomly generated shift vector by assigning a uniformly distributed random multiplication rate $\rho_j \in [0, 0.1]$ to each dimension $j = 1,...,n$.

For convenient access to all test problems utilized in this paper and to replicate the random shift vectors, we created a dedicated  script in the “Scripts/MPC” directory of the GitHub repository (<https://github.com/blockchain-group/DIRECTGO>).
These scripts serve as valuable tools for reproducing the findings presented in this investigation and for comparing and evaluating newly developed algorithms.

§.§ Setup and fundamental basis for algorithm comparison

All computations were executed on an Intel(R) Core$^\textit{TM}$ i5-10400 @ 2.90GHz Processor running  R2023a. The algorithms' solutions were compared with the globally optimal solution for each problem, and we considered the solver successful when the objective function value of a solution was within $0.01 \%$ of the global optimum.

For all analytical test cases with a known global optimum $f^*$, we employed a stopping criterion based on the percent error $(pe)$, as defined below:

\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}

The algorithms were terminated under the following conditions:

* When the $(pe)$ became smaller than $\varepsilon_{\rm pe} = 0.01$.

* When the number of function evaluations exceeded the prescribed limit $M_{\rm max} = n \times 10^5$.

* When the execution time exceeded $T_{\rm max} = 30$ CPU minutes. In such cases, the final result was set to $n \times 10^5$ to facilitate further processing of the result.

§.§ Algorithm design in

Considering that the developed  software allows for a large number of combinations, identifying the most effective ones may require a substantial amount of time and effort.
Therefore, we cannot guarantee that the algorithms presented are the most efficient within .
Furthermore, the benchmark set includes numerous distinct problems, such as discontinuous, non-differentiable, multi-modal, non-symmetric, and plateau functions.
It is improbable that a single combination will be the most efficient for all of these diverse problem types.

According to the no-free lunch theorem for optimization [54], there exists no universal optimization algorithm that performs optimally on all types of optimization problems.
As a result, certain modifications and additions to specific algorithms may not enhance performance on all problems and could even lead to a decline in performance in certain cases.
Therefore, the most optimal approach would involve leveraging machine learning-enhanced automated algorithm selection techniques [19] to generate algorithms tailored to specific problems.
However, this avenue remains a part of our future work and has yet to be explored.

To showcase the benefits of  software, we conducted an experiment involving five existing -type algorithms:  [51],  [45],  [26],  [35], and  [28].
Our aim was to improve their average performance across a designated set of test problems by introducing new algorithmic steps or substituting existing ones.

In <Ref>, we present five variants for each of the five selected algorithms, with their improved versions.
For pure algorithms of -type, which are characterized by slow solution refinement, enhancing their performance was achieved by incorporating local search techniques.
On the other hand, for hybrid methods, we made different adjustments to improve their performance.
Specifically, for the  algorithm, our goal was to increase the number of evaluations per iteration through enhancements, while for the  algorithm, we pursued the opposite approach.

Description of used parameters for each selected algorithm and their improved versions in . The blue color indicates the parameter that has been substituted or has been added.

Original algorithm parameters

$'\texttt{DTC}'$     $'\texttt{DBC}'$     $'\texttt{DTC}'$     $'\texttt{DBDP}'$     $'\texttt{DTC}'$

$'\texttt{One}'$     $'\texttt{All}'$     $'\texttt{All}'$     $'\texttt{One}'$     $'\texttt{All}'$

$'\texttt{Midpoint}'$     $'\texttt{MidMin}'$     $'\texttt{Midpoint}'$     $'\texttt{Min}'$     $'\texttt{Midpoint}'$

$'\texttt{Diagonal}'$     $'\texttt{Diagonal}'$     $'\texttt{Diagonal}'$     $'\texttt{Diagonal}'$     $'\texttt{Diagonal}'$

$'\texttt{Pareto}'$     $'\texttt{Aggressive}'$     $'\texttt{Original}'$     $'\texttt{Original}'$     $'\texttt{Original}'$

$'\texttt{One}'$     $'\texttt{One}'$     $'\texttt{All}'$     $'\texttt{One}'$     $'\texttt{All}'$

$'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{Min}'$     $'\texttt{Min}'$     $'\texttt{Min}'$

$-$     $-$     $0.0001$     $0.0001$     $0.0001$

$'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{MultiLevel1}'$     $'\texttt{Off}'$     $'\texttt{Off}'$

$'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{On}'$     $'\texttt{Off}'$

$'\texttt{On}'$     $'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{Off}'$

$'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{Single}'$     $'\texttt{Aggressive}'$

$-$     $-$     $-$     $'\texttt{interior-point}'$     $'\texttt{interior-point}'$

$-$     $-$     $-$     $1000$     $1000$

$-$     $-$     $-$     $3000$     $3000$

Improved algorithm parameters

$'\texttt{DTC}'$     $'\texttt{DBC}'$     $'\texttt{DTC}'$     $'\texttt{DBDP}'$     $'\texttt{DTC}'$

$'\texttt{One}'$     $'\texttt{All}'$     $'\texttt{All}'$     $'\textcolor{blue}{\texttt{All}}'$     $'\texttt{All}'$

$'\texttt{Midpoint}'$     $'\texttt{MidMin}'$     $'\texttt{Midpoint}'$     $'\texttt{Min}'$     $'\texttt{Midpoint}'$

$'\texttt{Diagonal}'$     $'\texttt{Diagonal}'$     $'\texttt{Diagonal}'$     $'\texttt{Diagonal}'$     $'\textcolor{blue}{\texttt{LongSide}}'$

$'\texttt{Pareto}'$     $'\texttt{Aggressive}'$     $'\texttt{Original}'$     $'\textcolor{blue}{\texttt{Pareto}}'$     $'\texttt{Original}'$

$'\texttt{One}'$     $'\texttt{One}'$     $'\texttt{All}'$     $'\texttt{One}'$     $'\textcolor{blue}{\texttt{One}}'$

$'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{Min}'$     $'\texttt{Min}'$     $'\textcolor{blue}{\texttt{Median}}'$

$-$     $-$     $0.0001$     $0.0001$     $0.0001$

$'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{MultiLevel1}'$     $'\texttt{Off}'$     $'\texttt{Off}'$

$'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{On}'$     $'\texttt{Off}'$

$'\texttt{On}'$     $'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{Off}'$     $'\texttt{Off}'$

$'\textcolor{blue}{\texttt{Single}}'$     $'\textcolor{blue}{\texttt{Aggressive}}'$     $'\textcolor{blue}{\texttt{Clustering}}'$     $'\texttt{Single}'$     $'\texttt{Aggressive}'$

$'\textcolor{blue}{\texttt{sqp}}'$     $'\textcolor{blue}{\texttt{sqp}}'$     $'\textcolor{blue}{\texttt{sqp}}'$     $'\textcolor{blue}{\texttt{sqp}}'$     $'\texttt{interior-point}'$

$\textcolor{blue}{1000}$     $\textcolor{blue}{1000}$     $\textcolor{blue}{1000}$     $1000$     $1000$

$\textcolor{blue}{3000}$     $\textcolor{blue}{3000}$     $\textcolor{blue}{3000}$     $3000$     $3000$

It is essential to note that the construction of the original algorithms within  may not always produce identical results to the implementations provided in  [48].
The discrepancy in the results can be attributed to the numerical tolerances used in the implementations, which play a critical role in the outcome.
For instance, authors might employ rounding on hyper-rectangle measure sizes, enabling them to group extremely small hyper-rectangles together.
Additionally, they might consider two function values identical if their difference is below a certain threshold.
These variations in the implementations can significantly impact the selection of POCs.

§.§ Results and discussions

In this section, we conduct a performance evaluation of ten -type algorithms, five of which are newly generated with .
The experimental results presented in this evaluation can also be accessed digitally in the “Results/MPC” directory of the GitHub repository, available at <https://github.com/blockchain-group/DIRECTGO>.

§.§.§ Comparison of success rates and function evaluations utilization

<Ref> provides an overview of the success rates achieved by the ten -type approaches considered on various subsets of the  test problems.
In particular, improvements that effectively improve the performance of the original algorithm are highlighted in green, while those that lead to deteriorating results are marked in red.
The most remarkable enhancements in success rates were observed in the case of the algorithm that performed worst in this study () after applying the improvements.
Its enhanced version yielded a remarkable increase in the success rate of $15.78 \%$.
Moreover, the most significant improvements were evident in the resolution of uni-modal problems, where the pure  version failed to locate the desired solutions within the allocated evaluation budget in $32.41 \%$ fewer instances.

Comparison of the success rates of different algorithms in solving test problems with various characteristics.

3*Algorithm     7cPercentage of solved problems

2*Overall     2cSeparability     2cMulti-modality     2cScalability

$+$     $-$     $+$     $-$     $+$     $-$

Impr.     $\textcolor{green}{82.18}$     $91.71$     $\textcolor{green}{77.62}$     $\textcolor{green}{77.30}$     $\textcolor{green}{98.62}$     $\textcolor{green}{78.92}$     $94.12$

Orig.     $80.60$     $91.71$     $75.29$     $75.66$     $97.24$     $76.91$     $94.12$

Impr.     $\textcolor{green}{78.08}$     $\textcolor{green}{87.32}$     $\textcolor{green}{73.66}$     $\textcolor{green}{72.19}$     $\textcolor{green}{97.93}$     $\textcolor{green}{73.69}$     $\textcolor{green}{94.12}$

Orig.     $67.35$     $76.59$     $62.94$     $62.58$     $83.45$     $62.45$     $85.29$

Impr.     $\textcolor{green}{64.20}$     $\textcolor{green}{78.05}$     $\textcolor{green}{57.58}$     $\textcolor{green}{55.42}$     $\textcolor{green}{93.79}$     $\textcolor{green}{59.84}$     $\textcolor{green}{80.15}$

Orig.     $48.42$     $65.85$     $40.09$     $44.58$     $61.38$     $43.17$     $67.65$

Impr.     $\textcolor{green}{75.08}$     $\textcolor{green}{83.90}$     $\textcolor{green}{70.86}$     $\textcolor{green}{68.30}$     $\textcolor{green}{97.93}$     $\textcolor{green}{70.68}$     $91.17$

Orig.     $70.66$     $82.43$     $65.03$     $63.60$     $94.48$     $65.06$     $91.17$

Impr.     $\textcolor{red}{76.34}$     $\textcolor{red}{84.39}$     $\textcolor{red}{72.49}$     $\textcolor{red}{70.34}$     $96.55$     $\textcolor{red}{71.28}$     $94.85$

Orig.     $77.76$     $84.88$     $74.36$     $72.19$     $96.55$     $73.09$     $94.85$

Among the pure -type algorithms, the  algorithm exhibited the lowest increase in success rates.
When considering the allocated budget for function evaluations, the improved algorithm  failed to provide a solution to the $113$ problems, while the original version struggled with the $123$ problems.
An important observation is that the original algorithm  performed quite well, surpassing the overall performance of the improved versions of other less efficient algorithms.

The enhancements in the hybrid algorithms resulted in increased success rates only for the  algorithm, whereas the success rates for the  algorithms exhibited a slight deterioration in most of the subsets considered.
Despite the improvement achieved in the  algorithm, it still remained outperformed by both versions of the  algorithm in almost all cases.

<Ref> presents a box plot that compares algorithms based on function evaluations per dimension on all test problems.
An important distinction between pure and hybrid algorithms is that pure algorithms generally require more function evaluations, even for relatively simple optimization problems.
On the contrary, hybrid algorithms demonstrate the ability to solve such problems quickly and efficiently.
Among the algorithms, almost all hybrid algorithms achieved similar lowest first-quartile values, indicating that these methods could solve at least $25\%$ of the test problems faster than pure algorithms.
Specifically, four algorithms (original and improved , improved , and improved ) were in the lowest first quartile.
On the contrary, the original  and original  algorithms exhibited the worst first-quartile performance, each requiring approximately nine and six times more function evaluations, respectively, than the best-performing algorithm, .

[group style=group size=1 by 5,x descriptions at=edge bottom,y descriptions at=edge left,vertical sep=11pt,horizontal sep=0pt,,]
title=,title style=yshift=-2ex, height=0.215,width=,
xmin=1,xmax=100000, xtick distance=10,enlarge x limits=0.01, xmode=log, ytick=1,2,
yticklabels=Original, Improved,
yticklabel style = font=,enlarge y limits=0.15,
xticklabel style = font=,
grid=both,grid style=line width=.1pt, draw=gray!15,
boxplot/draw direction=x,boxplot/whisker extend=0.5,
boxplot/every median/.style=red, thick, line width=1pt,
boxplot/every whisker/.style=black, ultra thick, dotted, line width=1pt,
boxplot/every box/.style=thick,boxplot/box extend=0.8,
every boxplot/.style=mark=+,every mark/.append style=mark size=2pt, mark options=draw=red
in 0,...,1
+[boxplot, fill=none, draw=black, solid, line width=.2pt] table[y index=] boxpl_fevals.txt;

title=,title style=yshift=-2ex, height=0.215,width=,
xmin=1,xmax=100000, xtick distance=10,enlarge x limits=0.01, xmode=log, ytick=1,2,
yticklabels=Original, Improved,
yticklabel style = font=,enlarge y limits=0.15,
xticklabel style = font=,
grid=both,grid style=line width=.1pt, draw=gray!15,
boxplot/draw direction=x,boxplot/whisker extend=0.5,
boxplot/every median/.style=red, thick, line width=1pt,
boxplot/every whisker/.style=black, ultra thick, dotted, line width=1pt,
boxplot/every box/.style=thick,boxplot/box extend=0.8,
every boxplot/.style=mark=+,every mark/.append style=mark size=2pt, mark options=draw=red
in 2,...,3
+[boxplot, fill=none, draw=black, solid, line width=.2pt] table[y index=] boxpl_fevals.txt;

title=,title style=yshift=-2ex, height=0.215,width=,
xmin=1,xmax=100000, xtick distance=10,enlarge x limits=0.01, xmode=log, ytick=1,2,
yticklabels=Original, Improved,
yticklabel style = font=,enlarge y limits=0.15,
xticklabel style = font=,
grid=both,grid style=line width=.1pt, draw=gray!15,
boxplot/draw direction=x,boxplot/whisker extend=0.5,
boxplot/every median/.style=red, thick, line width=1pt,
boxplot/every whisker/.style=black, ultra thick, dotted, line width=1pt,
boxplot/every box/.style=thick,boxplot/box extend=0.8,
every boxplot/.style=mark=+,every mark/.append style=mark size=2pt, mark options=draw=red
in 4,...,5
+[boxplot, fill=none, draw=black, solid, line width=.2pt] table[y index=] boxpl_fevals.txt;

title=,title style=yshift=-2ex, height=0.215,width=,
xmin=1,xmax=100000, xtick distance=10,enlarge x limits=0.01, xmode=log, ytick=1,2,
yticklabels=Original, Improved,
yticklabel style = font=,enlarge y limits=0.15,
xticklabel style = font=,
grid=both,grid style=line width=.1pt, draw=gray!15,
boxplot/draw direction=x,boxplot/whisker extend=0.5,
boxplot/every median/.style=red, thick, line width=1pt,
boxplot/every whisker/.style=black, ultra thick, dotted, line width=1pt,
boxplot/every box/.style=thick,boxplot/box extend=0.8,
every boxplot/.style=mark=+,every mark/.append style=mark size=2pt, mark options=draw=red
in 6,...,7
+[boxplot, fill=none, draw=black, solid, line width=.2pt] table[y index=] boxpl_fevals.txt;

title=,title style=yshift=-2ex, height=0.215,width=,
xmin=1,xmax=100000, xtick distance=10,enlarge x limits=0.01, xmode=log,
xlabel=Function evaluations / dimension, ytick=1,2,
yticklabels=Original, Improved,
yticklabel style = font=,enlarge y limits=0.15,
xticklabel style = font=,
grid=both,grid style=line width=.1pt, draw=gray!15,
boxplot/draw direction=x,boxplot/whisker extend=0.5,
boxplot/every median/.style=red, thick, line width=1pt,
boxplot/every whisker/.style=black, ultra thick, dotted, line width=1pt,
boxplot/every box/.style=thick,boxplot/box extend=0.8,
every boxplot/.style=mark=+,every mark/.append style=mark size=2pt, mark options=draw=red
in 8,...,9
+[boxplot, fill=none, draw=black, solid, line width=.2pt] table[y index=] boxpl_fevals.txt;

Box plot graphical comparison of algorithms performance based on function evaluations per dimension across all test problems.

The improved algorithm  demonstrated the best median value, while its pure counterpart, the original version , had the third worst median value in these studies.
The addition of the local search procedure to the  algorithm reduced the median value by nearly eight times, resulting in a significant improvement in its performance.
Interestingly, the median value of the original algorithm  is equal to the maximum number of function evaluation budgets ($M_{\rm max}$), indicating that the algorithm could not solve more than half of the test problems.
However, its improved version exhibited a significantly higher median value.
When comparing the third-quartile values, four algorithms reached the $M_{\rm max}$ value in the third quartile, suggesting that these algorithms could not solve more than $25\%$ of the problems.
Only six algorithms achieved values lower than the maximum evaluation budget.
Among these, the improved algorithm  achieved the lowest third-quartile value, approximately half that of the second-best pure algorithm, the original algorithm .

§.§.§ Analysis of results across different subsets of problems

[group style=group size=2 by 2,x descriptions at=edge bottom,y descriptions at=edge left,vertical sep=11pt,horizontal sep=5pt,,]
title=Seperable problem set,title style=yshift=-2.5ex,
ymin=0,ymax=1,ytick distance=0.1,enlarge y limits=0.025,
ylabel=Fraction of problems solved,ylabel shift = -5pt,
yticklabel style = font=,
xmin=1,xmax=100000,xtick distance=10,enlarge x limits=0.03,xmode=log,
grid=both,grid style=line width=.1pt, draw=gray!15,
tick label style=font=,height=0.45,width=0.5,
[s_dc]	table[x=T,y=b1]	overall.txt;
[s_dci]	table[x=T,y=b2]	overall.txt;
[s_hl]	table[x=T,y=b3]	overall.txt;
[s_hli]	table[x=T,y=b4]	overall.txt;
[s_mr]	table[x=T,y=b5] overall.txt;
[s_mri]	table[x=T,y=b6]	overall.txt;
[s_bm]	table[x=T,y=b7]	overall.txt;
[s_bmi]	table[x=T,y=b8]	overall.txt;
[s_dm]	table[x=T,y=b9]	overall.txt;
[s_dmi]	table[x=T,y=b10]overall.txt;
title=Non-seperable problem set,title style=yshift=-2.5ex,
ymin=0,ymax=1,ytick distance=0.1,enlarge y limits=0.025,
xmin=1,xmax=100000,xtick distance=10,enlarge x limits=0.03,xmode=log,
grid=both,grid style=line width=.1pt, draw=gray!15,
tick label style=font=,height=0.45,width=0.5,
[s_dc]	table[x=T,y=c1]	overall.txt;
[s_hl]	table[x=T,y=c3]	overall.txt;
[s_mr]	table[x=T,y=c5] overall.txt;
[s_bm]	table[x=T,y=c7]	overall.txt;
[s_dm]	table[x=T,y=c9]	overall.txt;
[s_dci]	table[x=T,y=c2]	overall.txt;
[s_hli]	table[x=T,y=c4]	overall.txt;
[s_mri]	table[x=T,y=c6]	overall.txt;
[s_bmi]	table[x=T,y=c8]	overall.txt;
[s_dmi]	table[x=T,y=c10]overall.txt;
title=Uni-modal problem set,title style=yshift=-2.5ex,
ymin=0,ymax=1,ytick distance=0.1,enlarge y limits=0.025,
ylabel=Fraction of problems solved,ylabel shift = -5pt,
xlabel=Function evaluations / dimension,
xticklabel style = font=,
yticklabel style = font=,
xmin=1,xmax=100000,xtick distance=10,enlarge x limits=0.03,xmode=log,
grid=both,grid style=line width=.1pt, draw=gray!15,
tick label style=font=,height=0.45,width=0.5,
[s_dci]	table[x=T,y=d2]	overall.txt;
[s_hli]	table[x=T,y=d4]	overall.txt;
[s_mri]	table[x=T,y=d6]	overall.txt;
[s_bmi]	table[x=T,y=d8]	overall.txt;
[s_dmi]	table[x=T,y=d10]overall.txt;
[s_dc]	table[x=T,y=d1]	overall.txt;
[s_hl]	table[x=T,y=d3]	overall.txt;
[s_mr]	table[x=T,y=d5] overall.txt;
[s_bm]	table[x=T,y=d7]	overall.txt;
[s_dm]	table[x=T,y=d9]	overall.txt;
title=Multi-modal problem set,title style=yshift=-2.5ex,
ymin=0,ymax=1,ytick distance=0.1,enlarge y limits=0.025,
xlabel=Function evaluations / dimension,
xmin=1,xmax=100000,xtick distance=10,enlarge x limits=0.03,xmode=log,
xticklabel style = font=,
grid=both,grid style=line width=.1pt, draw=gray!15,
tick label style=font=,height=0.45,width=0.5,
legend columns=5,legend style=at=(1.025,-0.25),font=, column sep=-1pt,legend cell align=left,
[s_dci]	table[x=T,y=e2]	overall.txt;
[s_hli]	table[x=T,y=e4]	overall.txt;
[s_mri]	table[x=T,y=e6]	overall.txt;
[s_bmi]	table[x=T,y=e8]	overall.txt;
[s_dmi]	table[x=T,y=e10]overall.txt;
[s_dc]	table[x=T,y=e1]	overall.txt;
[s_hl]	table[x=T,y=e3]	overall.txt;
[s_mr]	table[x=T,y=e5] overall.txt;
[s_bm]	table[x=T,y=e7]	overall.txt;
[s_dm]	table[x=T,y=e9]	overall.txt;
Impr. , Impr. , Impr. , Impr. , Impr. , Orig. , Orig. , Orig. , Orig. , Orig.

Data profiles: The horizontal axis represents the number of function evaluations per dimension, while the vertical axis represents the fraction of solved problems

The data profiles [31] depicted in <Ref> showcase how all algorithms perform on test problems with various properties of .
These profiles provide a comprehensive view of algorithm performance across different types of problems.
Meanwhile, the data profiles in <Ref> offer an overall ranking of the algorithms on all test problems, providing a more focused perspective on their performance in a broader context.

Hybridization of pure -type algorithms significantly impacts the results, particularly when dealing with straightforward uni-modal or separable test problems.
The inclusion of a local search procedure proves to be particularly advantageous for uni-modal problems, as it accelerates the convergence speed to reach optimal solutions more efficiently.
On the other hand, pure -type algorithms might prioritize the global search and exhaust the evaluation budget without locating the solution within the prescribed accuracy.
As a result, the curves of the improved versions of , , and  demonstrate significantly better performance than the original versions, especially for small evaluation budgets (${ \leq} 1000{\times}n$).
However, it is worth noting that the most successful pure -type algorithm, , eventually achieves nearly identical performance within the maximum evaluation budget, regardless of whether the problems are separable or uni-modal.

The improved hybrid algorithm  exhibits slightly lower performance within a small evaluation budget ($M_{\rm max}{\leq} n{\times}10^2$).
However, as the evaluation budget increases ($M_{\rm max}{\geq} n{\times}10^4$), the improved version outperforms the original version.
This difference in performance becomes particularly evident when the algorithm is applied to non-separable or multi-modal test problems.

On the other hand, the curves of the two versions of the hybrid algorithm  are almost indistinguishable within a smaller evaluation budget ($M_{\rm max}{\leq} 2n{\times}10^4$).
However, within a larger evaluation budget, the original algorithm  exhibits slightly better performance.

ymin=0,ymax=0.9,ytick distance=0.1,enlarge y limits=0.025,
ylabel=Fraction of problems solved,ylabel shift = -5pt,
xlabel=Function evaluations / dimension,
xmin=1,xmax=100000,xtick distance=10,enlarge x limits=0.01,xmode=log,
grid=both,grid style=line width=.1pt, draw=gray!15,
tick label style=font=,height=0.55,width=0.8,
legend pos=outer north east,legend style=row sep=0pt,font=,legend cell align=left,
empty legend
[s_dci]	table[x=T,y=a2]	overall.txt;
[s_dc]	table[x=T,y=a1]	overall.txt;
[s_hli]	table[x=T,y=a4]	overall.txt;
[s_dm]	table[x=T,y=a9]	overall.txt;
[s_dmi]	table[x=T,y=a10] overall.txt;
[s_bmi]	table[x=T,y=a8]	overall.txt;
[s_bm]	table[x=T,y=a7]	overall.txt;
[s_hl]	table[x=T,y=a3]	overall.txt;
[s_mri]	table[x=T,y=a6]	overall.txt;
[s_mr]	table[x=T,y=a5]	overall.txt;
Order of algorithms, Impr. , Orig. , Impr. , Orig. , Impr. , Impr. , Orig. , Orig. , Impr. , Orig.

Data profiles: The horizontal axis represents the number of function evaluations per dimension, while the vertical axis represents the fraction of solved problems

Based on the four graphs in <Ref> and the overall ranking of the algorithms in <Ref>, a consistent conclusion can be drawn: the performance of the improved and original  algorithm is the most efficient or at least comparable to the best-performing algorithm.
Analyzing the curves, it is evident that the improved algorithm  exhibits the highest efficiency rates across all graphs compared to other algorithms within any evaluation budget in $[0, n{\times}10^5]$.
Although the original performance of  becomes competitive, it requires a significant budget for the evaluations of functions ($M_{\rm max} {\geq} n{\times}10^4$).
Overall, the improved performance of the  algorithm remains competitive, requiring fewer function evaluations to achieve the desired optimal value in most test functions.

§.§.§ Statistical analysis of the results

To validate the results and comparisons between algorithms, as well as to evaluate the significance of improvements achieved by , we conducted the Friedman mean rank test [7] and the non-parametric Wilcoxon signed test [13] at a significance level of $5 \%$.
A $p$-value greater than $0.05$ indicates that the difference in results between methods is statistically insignificant.

<Ref> displays the Friedman mean rank values for considered algorithms, utilizing the founded solution values within different evaluation budgets for all test problems.
The results reveal that the improved versions consistently outperform their original counterparts in all budgets, except for the algorithm , where the original version obtained a higher rank in one specific evaluation budget ($M_{\rm max} {=} n{\times}10^5$).
The improvements made to the algorithms have resulted in performance gains ranging from small to significant, as indicated by the higher mean rank values.

Friedmann mean rank values with different objective function evaluation budgets.

2*Algorithm     4cFunction evaluation budget $(M_{\rm max})$

$n{\times}10^2$     $n{\times}10^3$     $n{\times}10^4$     $n{\times}10^5$

Impr.     $4.7610$     $4.6128$     $4.6128$     $4.6601$

Orig.     $6.0095$     $5.3375$     $5.3375$     $4.7831$

Impr.     $5.5670$     $5.5229$     $5.5229$     $5.3249$

Orig.     $7.2752$     $7.1372$     $7.1372$     $6.1672$

Impr.     $5.3730$     $5.2500$     $5.2500$     $5.8028$

Orig.     $5.3730$     $6.8099$     $6.8099$     $7.1435$

Impr.     $4.6151$     $4.6562$     $4.6562$     $5.1333$

Orig.     $5.0103$     $5.0765$     $5.0765$     $5.6356$

Impr.     $5.4219$     $5.2886$     $5.2886$     $5.2492$

Orig.     $5.5938$     $5.3084$     $5.3084$     $5.1002$

<Ref> presents the $p$-values obtained by comparing the improved algorithms with their original counterparts, using the solutions found within four evaluation budgets on all test problems.
For the improved algorithm , there is strong statistical evidence that the improved version significantly outperforms the original version within a small evaluation budget ($M_{\rm max}{\leq} n{\times}10^3$).
However, as the evaluation budget increases ($M_{\rm max}{>} n{\times}10^3$), the higher $p$-values suggest that the significance of the improvement decreases and the difference between the improved and original versions becomes less statistically significant.
In contrast, the situation is different for the other two pure -type algorithms.
The improved versions of  and  show no significant improvement compared to the original versions at $M_{\rm max} {=} n{\times}10^2$.
However, for larger evaluation budgets, the $p$-values are low, indicating that the improvements are statistically significant.

For the  algorithm, the $p$-values are low, indicating that the improvement of the improved version of  compared to the original version is statistically significant in all these budgets.
Regarding ] algorithm, we can conclude that the improved version of the algorithm is statistically better if the evaluation budgets are $M_{\rm max} {=} n{\times}10^2$ and $M_{\rm max} {=} n{\times}10^4$.

Wilcoxon signed test $p$-values at $5 \%$ significance level, comparing improved vs. original algorithms across various objective function evaluation budgets.

2*Algorithm     4cFunction evaluation budget $(M_{\rm max})$

$n{\times}10^2$     $n{\times}10^3$     $n{\times}10^4$     $n{\times}10^5$

$6.3325{\times}10^{-3}$     $2.4241{\times}10^{-8}$     $2.6994{\times}10^{-1}$     $5.8529{\times}10^{-1}$

$2.3254{\times}10^{-1}$     $4.0565{\times}10^{-13}$     $5.3640{\times}10^{-10}$     $3.3265{\times}10^{-13}$

$1.0000{\times}10^{0}$     $2.0141{\times}10^{-34}$     $4.5374{\times}10^{-40}$     $5.9712{\times}10^{-34}$

$2.5863{\times}10^{-2}$     $2.8668{\times}10^{-9}$     $1.0548{\times}10^{-12}$     $1.5552{\times}10^{-15}$

$3.0296{\times}10^{-8}$     $4.6683{\times}10^{-1}$     $8.2874{\times}10^{-3}$     $4.4600{\times}10^{-4}$

§ CONCLUSIONS AND FUTURE WORKS

This study introduces a novel generalized -type algorithmic framework known as , for derivative-free global optimization.
The proposed framework empowers users to construct a wide range of -type algorithms.
Such innovative work can foster the development of new -type algorithms and help identify the most suitable algorithm for various practical applications.

To demonstrate the efficiency of , we enhanced five selected -type algorithms with the goal of improving their performance and solving global optimization problems more effectively.
Evaluation of these constructed algorithms was carried out using benchmark test functions from .
The results were analyzed both graphically and statistically to gain insight into the algorithms' performance.
The findings concluded that the newly developed versions of the -type algorithms significantly outperformed their original counterparts in most cases.

In conclusion, this paper has focused on box-constrained global optimization problems, but the generalized -type algorithmic framework () could potentially be extended to handle constrained cases as well.
Furthermore, due to the numerous combinations of algorithms within , manually testing all of them becomes impractical.
Therefore, future research should explore the automation of these processes using advanced machine-learning techniques.
By automating the algorithmic components process, optimization can become more efficient and effective.

§ DATA STATEMENT

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

* <https://github.com/blockchain-group/DIRECTGOLib>,

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

[1]
Abdesslem, L.: New hard benchmark functions for global optimization (2022).
MATLAB Central File Exchange. Retrieved February 18, 2022.

[2]
Agrawal, P., Abutarboush, H.F., Ganesh, T., Mohamed, A.W.: Metaheuristic
algorithms on feature selection: A survey of one decade of research
IEEE Access 9, 26766–26791 (2021)

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

[4]
Chiter, L.: Experimental data for the preprint "diagonal partitioning strategy
using bisection of rectangles and a novel sampling scheme" (2023).

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

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

[7]
Friedman, M.: The use of ranks to avoid the assumption of normality implicit in
the analysis of variance.
Journal of the American Statistical Association 32(200),
675–701 (1937).

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

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

[10]
Golovin, D., Solnik, B., Moitra, S., Kochanski, G., Karro, J., Sculley, D.:
Google vizier: A service for black-box optimization.
In: Proceedings of the 23rd ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, KDD '17, p. 1487–1495. Association for
Computing Machinery, New York, NY, USA (2017).

[11]
Hansen, N., Finck, S., Ros, R., Auger, A.: Real-Parameter Black-Box
Optimization Benchmarking 2009: Noiseless Functions Definitions.
Research Report RR-6829, INRIA (2009).

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

[13]
Hollander, M., Wolfe, D.: Nonparametric Statistical Methods, Solutions Manual.
Wiley Series in Probability and Statistics. Wiley (1999).

[14]
Holmström, K., Edvall, M.M.: The TOMLAB Optimization Environment, pp.
Springer US, Boston, MA (2004).

[15]
Jamil, M., Yang, X.S.: A literature survey of benchmark functions for global
optimisation problems.
International Journal of Mathematical Modelling and Numerical
Optimisation 4(2), 150–194 (2013).
PMID: 55204

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

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

[18]
Jones, D.R., Schonlau, M., Welch, W.J.: Efficient Global Optimization of
Expensive Black-Box Functions.
Journal of Global Optimization 13(4), 455–492 (1998).

[19]
Kerschke, P., Hoos, H.H., Neumann, F., Trautmann, H.: Automated Algorithm
Selection: Survey and Perspectives.
Evolutionary Computation 27(1), 3–45 (2019).

[20]
Kudela, J., Matousek, R.: New benchmark functions for single-objective
optimization based on a zigzag pattern.
IEEE Access 10, 8262–8278 (2022).

[21]
Kudela, J., Matousek, R.: Recent advances and applications of surrogate models
for finite element method computations: a review.
Soft Computing 26, 13709–13733 (2022).

[22]
Larson, J., Menickelly, M., Wild, S.M.: Derivative-free optimization methods.
Acta Numerica 28(2010) (2019).

[23]
Liang, J.J., Qu, B.Y., Suganthan, P.N.: Problem definitions and evaluation
criteria for the cec 2014 special session and competition on single objective
real-parameter numerical optimization.
Computational Intelligence Laboratory, Zhengzhou University,
Zhengzhou China and Technical Report, Nanyang Technological University,
Singapore 635(2) (2013)

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

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

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

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

[28]
Liuzzi, G., Lucidi, S., Piccialli, V.: Exploiting derivative-free local
searches in direct-type algorithms for global optimization.
Computational Optimization and Applications 65, 449–475
DOI 10.1007/s10589-015-9741-9

[29]
Mockus, J.: On the pareto optimality in the context of lipschitzian
Informatica 22(4), 521–536 (2011).

[30]
Mockus, J., Paulavičius, R.: On the reduced-set pareto-lipschitzian
Computational Science and Techniques 1(2), 184–192 (2013)

[31]
Moré, J.J., Wild, S.M.: Benchmarking derivative-free optimization
SIAM Journal on Optimization 20(1), 172–191 (2009).

[32]
Oldenhuis, R.: Test functions for global optimization algorithms.
Online; accessed: 2023-02-22

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

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

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

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

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

[38]
Paulavičius, R., Žilinskas, J., Grothey, A.: Investigation of
selection strategies in branch and bound algorithm with simplicial partitions
and combination of Lipschitz bounds.
Optimization Letters 4(2), 173–183 (2010).

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

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

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

[42]
Shi, H.J.M., Xuan, M.Q., Oztoprak, F., Nocedal, J.: On the numerical
performance of derivative-free optimization methods based on
finite-difference approximations (2021).

[43]
Stripinis, L., Kůdela, J., Paulavičius, R.: Directgolib - direct global
optimization test problems library (2023).
Pre-release v2.0

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

[45]
Stripinis, L., Paulavičius, R.: An extensive numerical benchmark study of
deterministic vs. stochastic derivative-free global optimization algorithms

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

[47]
Stripinis, L., Paulavičius, R.: DIRECTGO: A New DIRECT-Type MATLAB Toolbox
for Derivative-Free Global Optimization.
ACM Transactions on Mathematical Software  (2022).

[48]
Stripinis, L., Paulavičius, R.: Directgo: A new direct-type matlab toolbox
for derivative-free global optimization.
ACM Trans. Math. Softw. 48(4) (2022).

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

[50]
Stripinis, L., Paulavičius, R.: Experimental study of excessive local
refinement reduction techniques for global optimization direct-type
Mathematics 10(20) (2022).

[51]
Stripinis, L., Paulavičius, R.: An empirical study of various candidate
selection and partitioning techniques in the direct framework.
Journal of Global Optimization  (2022).

[52]
Stripinis, L., Paulavičius, R.: Lipschitz-inspired halrect algorithm for
derivative-free global optimization.
Journal of Global Optimization  (2023).

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

[54]
Wolpert, D.H., Macready, W.G., et al.: No free lunch theorems for search.
Tech. rep., Citeseer (1995)

[55]
Wu, G., Mallipeddi, R., Suganthan, P.N.: Problem definitions and evaluation
criteria for the cec 2017 competition on constrained real-parameter
National University of Defense Technology, Changsha, Hunan, PR China
and Kyungpook National University, Daegu, South Korea and Nanyang
Technological University, Singapore, Technical Report  (2017)