# A Direct Search Algorithm for Global Optimization
## 3 A Direct Search Algorithm for Global Optimization
### Convergence of the Basic Algorithm
Subtracting \(\langle\
abla\phi(\xi_{k}),\mathbf{d}_{i}\rangle|\Delta_{k}|\) from both sides leads to:  
\[-c\Delta_{k}^{2}-\langle\
abla\phi(\xi_{k}),\mathbf{d}_{i}\rangle|\Delta_{k}| \leq\langle\
abla\phi(\xi_{k}+\alpha_{k}|\Delta_{k}|\mathbf{d}_{i})-\
abla \phi(\xi_{k}),\mathbf{d}_{i}\rangle|\Delta_{k}|\]  
Applying Equation (21) yields:  
\[\frac{1}{\sqrt{n}}\|\
abla\phi(\xi_{k})\|\leq\langle\
abla\phi(\xi_{k}+\alpha _{k}|\Delta_{k}|\mathbf{d}_{i})-\
abla\phi(\xi_{k}),\mathbf{d}_{i}\rangle+c| \Delta_{k}|\]  
Taking into account that \(\phi\) is continuously differentiable in \(\mathcal{B}_{P}(\xi_{k})\) and its gradient \(\
abla\phi\) is Lipschitz with constant \(PM\) in \(\mathcal{B}_{P}(\xi_{k})\),  
\[\frac{1}{\sqrt{n}}\|\
abla\phi(\xi_{k})\|\leq PM\|\alpha_{k}\Delta_{k} \mathbf{d}_{i}\|+c|\Delta_{k}|\leq(PM+c)|\Delta_{k}|\]  
because \(\alpha_{k}\in(0,1)\) and \(\|\mathbf{b}_{i}\|=1\). Consequently,  
\[\|\
abla\phi(\xi_{k})\|\leq\sqrt{n}(PM+c)|\Delta_{k}|\]  
and taking the limit when \(k\) approaches infinity, it is possible to conclude that:  
\[\lim_{k\to\infty}\|\
abla\phi(\xi_{k})\|\leq\sqrt{n}(PM+c)\lim_{k\to\infty}| \Delta_{k}|=0,\text{ for }k\in\mathcal{U}\]  
and finally, by making \(\mathbf{x}_{k}=\mathrm{frac}(\xi_{k})\):  
\[\frac{1}{\sqrt{n}}\leq\cos\theta=\frac{\langle-\
abla\phi(\xi_{k}),\mathbf{b} _{i}\rangle}{\|\
abla\phi(\xi_{k})\|\|\mathbf{d}_{i}\|}\]0Consequently, the sequence of points generated by the basic algorithm converges to a stationary point. **Remark 2**. : The basic algorithm can be applied to any cost function \(f\), not necessarily continuous or differentiable in the search space \((0,1)^{n}\). For a continuous and differentiable function with a Lipschitz continuous gradient, the basic algorithm converges to a stationary point. If in addition the cost function is strictly convex, then the unique optimizer is a stationary point, and Theorem 3 guarantees that the basic algorithm converges to the unique optimizer. Note that we do not need to know the value of the Lipschitz constant \(M\). **Example 2**. : The evolution of the basic algorithm for the function \(f(x)=|x|-|\sqrt{\pi}\sin(3\pi x)|\) is depicted in \[\frac{1}{\sqrt{n}}\leq\cos\theta=\frac{\langle-\
abla\phi(\xi_{k}),\mathbf{b} _{i}\rangle}{\|\
abla\phi(\xi_{k})\|\|\mathbf{d}_{i}\|}\]1 The parameters of the algorithm are \(P=10^{4}\), \(\sigma=0.5\), \(\rho=1.05\), \(c=0.01\), \(\epsilon=10^{-4}\). Since this problem is unidimensional, the simplex is an interval. The left plots represent the vertex points of the simplex in the original space (above) and their corresponding function values (below) after each iteration. The right plots represent the values of the worst (above) and best (below) points of the simplex in the original space that were obtained during the execution of the algorithm. Note that the algorithm explores the whole range of the unit interval. This exploration is performed whenever the length of the simplex edge \(\Delta_{k}\) satisfies \(P\Delta_{k}\geq 1\), which corresponds to the exploratory phase of the algorithm. Once \(\Delta_{k}\) is \(P\Delta_{k}<1\), then the algorithm enters the phase of convergence to a stationary point. In this example, the algorithm stops after 24 iterations. From Iterations 1 to 12, the algorithm is in the exploratory phase, and from Iterations 13 to 24, the algorithm is in the convergence phase to a stationary point. The point obtained corresponds to \(f(0.1721)=-0.2422\), which is the global minimal value within the space tolerance \(\epsilon\).