# A Direct Search Algorithm for Global Optimization
## 3 A Direct Search Algorithm for Global Optimization
### Function Transformation
If \(\mathbf{x}=0\), then \(\mathcal{B}_{P}(\mathbf{0})\) is the fundamental \(n\)-box of the function \(\phi\), _i.e._, \(B_{P}(\mathbf{0})=(0,P^{-1})^{n}\). For another \(\mathbf{x}\in\mathbb{R}^{n}\), \(\mathcal{B}_{P}(\mathbf{x})\) is an \(n\)-box of length \(P^{-1}\), where the function \(\phi\) takes the same values as in the fundamental \(n\)-box \(\mathcal{B}_{P}(\mathbf{0})\). Note that there are \(P^{n}\) different \(n\)-boxes for \(\mathbf{x}\in(0,1)^{n}\); then, the function \(\phi\) repeats \(P^{n}\) times in the unit \(n\)-box \((0,1)^{n}\). **Example 1**. : The function \(f(x)=|x|-|\sqrt{x}\sin(3\pi x)|\), and the transformed function \(\phi(\xi)=f(\text{frac}(P\xi))\) for \(P=10\) are depicted for the open unit interval in Figure 1. The function \(f\) is continuous on the open unit interval \((0,1)\) and has three local minima. The transformed function \(\phi\) is periodic, of period \(P^{-1}=0.1\), and piecewise continuous on the open unit interval. The fundamental period of \(\phi\) is \(\mathcal{B}(0)=(0,0.1)\), and the function value repeats ten times on the unit interval. The function \(\phi\) is continuous on each interval \(\mathcal{B}(x)=\{\xi:\lfloor 10\xi\rfloor=\lfloor 10x\rfloor,\;10\xi\
ot\in \mathbb{Z}\}\) for \(x\in\mathbb{R}\), but discontinuous at the boundary points of these intervals, which are given by \(\xi=0.1k\) for any integer \(k\). This discontinuity always occurs if \(f(0+\epsilon)\
eq f(1-\epsilon)\) for any \(\epsilon>0\), as occurs in this example and which is clearly visible in Figure 1. Moreover, the function \(\phi\) is not necessarily defined for these points of discontinuity. Consider the unconstrained optimization problem:  
\[\min\{\phi(\boldsymbol{\xi}):\boldsymbol{\xi}\in\text{dom}\;\phi\} \tag{12}\]  
The function \(\phi\) has a global optimizer at \(\boldsymbol{\xi}^{*}\) if \(\phi(\boldsymbol{\xi}^{*})\leq\phi(\boldsymbol{\xi})\) for all \(\boldsymbol{\xi}\in\text{dom}\;\phi\). The following theorem proves that the transformed unconstrained minimization problem Equation (12) also provides the minimum value of the original optimization problem Equation (1). **Theorem 1**. : _Let \(f\) be a real value continuous function on the open unit \(n\)-box, and let \(\phi\) be defined as \(\phi(\xi)=f(\operatorname{frac}(P\xi))\), where \(P\) is a positive integer, then \(\lambda^{*}=\min\{f(\mathbf{x}):\mathbf{x}\in(0,1)^{n}\}\) if and only if \(\lambda^{*}=\min\{\phi(\xi):\xi\in\operatorname{dom}\phi\}\)._  
Proof. : (If): Let \(\mathbf{x}^{*}\) be such that \(\lambda^{*}=f(\mathbf{x}^{*})=\min\{f(\mathbf{x}):\mathbf{x}\in(0,1)^{n}\}\) and \(\phi(\xi)=f(\operatorname{frac}(P\xi))\), where \(P\) is a positive integer; then define \(\xi^{*}=P^{-1}(\mathbf{x}^{*}+\mathbf{\eta})\) for any \(\mathbf{\eta}\in\mathbb{Z}^{n}\); then \(\phi(\xi^{*})=f(\mathbf{x}^{*})=\lambda^{*}\). (Only if): Let \(\xi^{*}\) be such that \(\lambda^{*}=\phi(\xi^{*})=\min\{\phi(\xi):\xi\in\operatorname{dom}\phi\}\); define \(\mathbf{x}^{*}=\operatorname{frac}(P\xi^{*})\); then \(f(\mathbf{x}^{*})=\phi(\xi^{*})=\lambda^{*}\). Theorem 1 allows us to obtain a global minimizer of the original function \(f\) on the open unit \(n\)-box by solving the unconstrained optimization problem (12). If we have a method that computes a global minimizer \(\xi^{*}\) of the unconstrained optimization problem (12), then \(\mathbf{x}^{*}=\operatorname{frac}(P\xi^{*})\in(0,1)^{n}\), and it satisfies \(\phi(\xi^{*})=f(\mathbf{x}^{*})\). The following lemma proves that any regular \(n\)-box of a size greater than or equal to \(P^{-1}\) always contains a point \(\xi^{*}\) that attains the global minimum of the unconstrained optimization problem (12). **Lemma 4**. : _Let \(\mathcal{B}\) be a regular \(n\)-box of edge length \(\Delta_{B}\), such that \(P\Delta_{B}\geq 1\), and let \(\lambda^{*}=\min\{f(\mathbf{x}):\mathbf{x}\in(0,1)\}\); then, the \(n\)-box \(\mathcal{B}\) always contains a point \(\xi^{*}\in\mathbb{R}^{n}\), such that \(\phi(\xi^{*})=\lambda^{*}\)._  
Proof.