# A Direct Search Algorithm for Global Optimization
## 3 A Direct Search Algorithm for Global Optimization
### Function Transformation
: Let \(\mathbf{x}^{*}\in(0,1)^{n}\) be such that \(f(\mathbf{x}^{*})=\lambda^{*}\leq f(\mathbf{x})\) for any \(\mathbf{x}\in(0,1)^{n}\), and let \(\tilde{\mathbf{\xi}}\in\mathcal{B}\), such that \(\lfloor P\tilde{\mathbf{\xi}}\rceil=\lfloor P\tilde{\mathbf{\xi}}+\mathbf{x}^{*}\rfloor\). Consider the open \(n\)-box \(\mathcal{B}_{P}(\tilde{\mathbf{\xi}})=\{\mathbf{\xi}\in\mathbb{R}^{n}:\lfloor P\xi\rfloor =\lfloor P\tilde{\mathbf{\xi}}\rfloor,\ P\xi\
ot\in\mathbb{Z}^{n}\}\), then \(\mathcal{B}_{P}(\tilde{\mathbf{\xi}})\) has edge length \(P^{-1}\), and the point \(\xi^{*}=P^{-1}(\mathbf{x}^{*}+\lfloor P\tilde{\mathbf{\xi}}\rfloor)\) satisfies \(\xi^{*}\in\mathcal{B}(\tilde{\mathbf{\xi}})\cap\mathcal{B}\) and \(\phi(\xi^{*})=f(\mathbf{x}^{*})=\lambda^{*}\). We are also interested in determining the size of an \(n\)-simplex similar to the standard \(n\)-simplex that always contains a global minimizer of \(\{\phi(\xi):\mathbf{\xi}\in\operatorname{dom}\phi\}\). Since Lemma 4 establishes that such a point is always contained in a regular \(n\)-box of length not less than \(P^{-1}\), then the solution is an isosceles right \(n\)-simplex that contains a regular \(n\)-box of length \(P^{-1}\). From Lemma 1, this \(n\)-simplex has edge length \(nP^{-1}\) and content \(P^{-n}/(n-1)!\). The following lemma states the result. **Theorem 2**. : _Let \(\Sigma\) be an isosceles right \(n\)-simplex of length \(\Delta\), such that \(P\Delta\geq n\), and let \(\lambda^{*}=\min\{f(\mathbf{x}):\mathbf{x}\in(0,1)^{n}\}\); then, the \(n\)-simplex \(\Sigma\) always contains a point \(\xi^{*}\in\operatorname{dom}\phi\), such that \(f(\operatorname{frac}(\xi^{*}))=\lambda^{*}\)._  
Figure 1: A continuous function \(f(x)=|x|-|\sqrt{x}\sin(3\pi x)|\) with three local minima in the unit interval \((0,1)\) and the corresponding transformed function \(\phi(\xi):=f(\operatorname{frac}(P\xi))\) where \(P=10\) for the same interval. Proof. : A regular \(n\)-box of edge length \(\Delta_{B}=\Delta/n\) can be inscribed inside any isosceles right \(n\)-simplex of length \(\Delta\). Since \(P\Delta\geq n\), then \(P\Delta_{B}\geq 1\), and the theorem statement is a straightforward consequence of Lemma 4. In the rest of this section, we shall design a direct search algorithm to obtain a solution for the optimization problem (1). We distinguish two algorithms, the basic algorithm and the complete algorithm. The basic algorithm is a simplex-based algorithm for the transformed cost function. An initial point is embedded at the right vertex of an isosceles right \(n\)-simplex of edge length \(\Delta_{0}\). This \(n\)-simplex evolves by a sequence of operations. As a result of each iteration, another \(n\)-simplex is obtained that is similar to the standard \(n\)-simplex and has the point with minimum value of the transformed cost function located in the right vertex. The edge length of the \(n\)-simplex decreases by a constant factor if no operations performed during the iteration produce a vertex with a smaller value of the transformed cost function. Whenever the edge length is no less than \(nP^{-1}\), we say that the algorithm is in exploratory phase, because the \(n\)-simplex always contains a global minimizer of \(\{\phi(\xi):\xi\in\text{dom }\phi\}\). When the edge length of the \(n\)-simplex is less than \(nP^{-1}\), then we say that the algorithm is in convergence phase, and it aims to approach a stationary point. Thus, the basic algorithm is designed to preserve the good properties of direct search algorithms, such as convergence to a stationary point, but increases the possibility to reach the global optimum at the end of the exploratory phase. Another feature of the basic algorithm is that there is no interruption or change from one phase to the other, it is a straightforward consequence of using the transformed cost function.