## 3 Preliminaries
### DIRECT Framework  
In 1993, [PERSON] et al. [21] took inspiration from Lipschitzian optimization and introduced the DIRECT algorithm, which does not require prior knowledge of the Lipschitz constant. The DIRECT algorithm regards the entire solution space as a hyperrectangle, and continuously divides it to obtain new sub-hyperrectangles. In each iteration, it selects the potentially optimal hyperrectangles according to certain rules which are then subdivided into equal parts along the longest side, and calculates the corresponding function at the center points. It is obvious that one of the keys to determining the algorithm's efficiency is the strategy for selecting potentially optimal hyperrectangles. Assuming that there are currently \(m\) hyperrectangles in the solution space, the \(j\)th hyperrectangle is considered as the potentially optimal hyperrectangle if there is a constant \(\tilde{K}\) satisfies the Formula (6)  
\[f(c_{j})-\tilde{K}d_{j} \leq f(c_{i})-\tilde{K}d_{i},\text{ for all }i=1,2,\ldots,m\] \[f(c_{j})-\tilde{K}d_{j} \leq f_{min}-\epsilon|f_{min}| \tag{6}\]  
where \(\epsilon\) is a positive constant, \(f(c_{j})\) is the function value at the center point of hyperrectangle \(j\), and \(d_{i}\) refers to the center-vertex distance of hyperrectangle \(i\), and \(f_{min}\) denotes the current optimal function value. Figure 1 shows the properties of potentially optimal hyperrectangles more intuitively.  
After the potentially optimal hyperrectangles are determined, they will be sub-divided along the longest side to form new sub-hyperrectangles. For an \(n\)-dimensional solution space, there may be multiple longest sides of the same length. In such a situation, it is necessary to specify the partition strategy because different strategies form different sub-hyperrectangles. For example, the DIRECT algorithm could successively select the coordinate direction with the smallest value of \(v_{i}=\min\{f(c+\delta e_{i}),f(c-\delta e_{i})\}\). The detailed partition procedure is provided in Algorithm 1.  
Figure 1: Properties of potentially optimal hyperrectangles.  
```
0: Function to be minimized \(f\), the current potentially optimal hyperrectangle \(i\)
0: Newly acquired hyperrectangles from \(i\)
1: Find the dimension set \(I\) with the largest side length and set \(\delta\) to be \(1/3\) of the largest side length.
2: Calculate the function value at the points \(c\pm\delta e_{i}\) for all \(i\in I\), where \(c\) refers to the center of a hyperrectangle and \(e_{i}\) denotes the unit vector of corresponding direction.
3: Divide all the longest side dimensions of the current hyperrectangle into 3 equal parts, starting from the dimension of minimum \(v_{i}=\min\{f(c+\delta e_{i}),f(c-\delta e_{i})\}\) continuing to the dimension of maximum \(v_{i}\).
```  
**Algorithm 1** Procedure for hyperrectangle partition  
Then, the DIRECT algorithm can be expressed in Algorithm 2.  
```
0: Function to be minimized \(f\), evaluation budget \(t\)
0: Approximate minimum of function \(f\)
1: Normalize the solution space to a hyperrectangle with \(c_{1}\) to be the center point.
2: Calculate the function value \(f(c_{1})\) for \(c_{1}\) and set \(f_{min}=f(c_{1}),\ m=1,\ t=0\).
3:while evaluation budget is not exhausted do
4: Identify the current set \(S\) of potentially optimal hyperrectangles.
5:while\(S\
eq\varnothing\)do
6: Choose a potentially optimal hyperrectangle \(j\in S\).
7: Divide the hyperrectangle \(j\) to generate new hyperrectangles by Algorithm 1.
8: Update \(f_{min}\) and \(m=m+\Delta m\). \(\triangleright\)\(\Delta m\) is the number of new hyperrectangles generated during the partition procedure.
9:\(S\gets S-\{j\}\)
10:\(t=t+1\)
```  
**Algorithm 2** DIRECT algorithm