# A Direct Search Algorithm for Global Optimization
## 3 A Direct Search Algorithm for Global Optimization
### Convergence of the Basic Algorithm  
The basic algorithm has been designed to provide termination and improvement by performing a sequence of simplex transformations. If in addition, the cost function is differentiable and its gradient is Lipschitz continuous, then the basic algorithm converges to a stationary point. **Theorem 3**: _Let \(f\) be the cost function of a minimization problem on the open unit \(n\)-box; then the basic algorithm always terminates. If, in addition, \(f\) is differentiable and its gradient \(\Delta f\) is Lipschitz continuous on the unit \(n\)-box, then the sequence of points generated at each iteration by the basic algorithm converges to a stationary point._  
Proof. : Let \(\mathcal{S}\) and \(\mathcal{U}\) denote the index sets of successful and unsuccessful iterations of the basic algorithm, respectively. Let \(\mathbf{x}_{k}=\operatorname{frac}(P\boldsymbol{\xi}_{k})\), then \(f(\mathbf{x}_{k})=\phi(\boldsymbol{\xi}_{k})\). If \(k\in\mathcal{S}\), then \(f(\mathbf{x}_{k+1})<f(\mathbf{x}_{k})-c\Delta_{k}^{2}\) and \(\Delta_{k+1}=\rho\Delta_{k}\), while if \(k\in\mathcal{U}\), then \(f(\mathbf{x}_{k+1})\geq f(\mathbf{x}_{k})-c\Delta_{k}^{2}\) and \(\Delta_{k+1}=\sigma\Delta_{k}\). Let us infinity, the update rule \(\Delta_{k+1}=\sigma\Delta_{k}\) yields \(\lim_{k\to\infty}|\Delta_{k}|=0\). In addition, there exists \(\underline{\Delta}>0\), such that for each successful iteration \(\ell\in\mathcal{S}\), \(|\Delta_{\ell}|\geq\underline{\Delta}\) and:  
\[f(\mathbf{x}_{\ell+1})<f(\mathbf{x}_{\ell})-c\Delta_{\ell}^{2}\leq f(\mathbf{x }_{\ell})-c\underline{\Delta}^{2}\]  
However, since \(\ell\) approaches infinity, this implies that \(f(\mathbf{x}_{\ell+1})\to-\infty\), which contradicts the fact that the function \(f\) is bounded below on \((0,1)^{n}\). Consequently, the boundedness of \(f\) implies that \(\underline{\Delta}=0\) and \(\lim_{k\to\infty}|\Delta_{k}|=0\). This proves the termination of the basic algorithm. For the second part of the theorem, if \(f\) is continuous and differentiable on \((0,1)^{n}\), then so is \(\phi(\xi)=f(\mathrm{frac}(P\xi))\) on the \(n\)-box \(\mathcal{B}_{P}(\mathbf{x})=\{\xi\in\mathbb{R}^{n}:\lfloor P\xi\rfloor= \lfloor P\mathbf{x}\rfloor,\;P\xi\
ot\in\mathbb{Z}^{n}\}\) for any \(\mathbf{x}\in\mathbb{R}^{n}\). Furthermore, if \(\
abla f\) is Lipschitz continuous with constant \(M\) on \((0,1)^{n}\), then so is \(\
abla\phi\) in \(\mathcal{B}_{P}(\mathbf{x})\) with constant \(PM\). Since we proved that \(\lim_{k\to\infty}|\Delta_{k}|=0\), then there always exists a positive integer \(L\), such that \(\lfloor P\xi_{k}\rfloor=\lfloor P\xi_{L}\rfloor\) for any positive integer \(k>L\). The basic algorithm searches points along the coordinate directions; then, from Lemma 2 and for any positive integer \(k>L\), no matter the value of \(\
abla\phi(\xi_{k})\), there is always at least one (positive or negative) coordinate direction \(\mathbf{d}_{i}\in\{\mathbf{b}_{i},-\mathbf{b}_{i}\}\), such that:  
\[\frac{1}{\sqrt{n}}\leq\cos\theta=\frac{\langle-\
abla\phi(\xi_{k}),\mathbf{b} _{i}\rangle}{\|\
abla\phi(\xi_{k})\|\|\mathbf{d}_{i}\|}\]  
or equivalently:  
\[\frac{1}{\sqrt{n}}\|\
abla\phi(\xi_{k})\leq-\langle\
abla\phi(\xi_{k}), \mathbf{d}_{i}\rangle \tag{21}\]  
because \(\|\mathbf{d}_{i}\|=1\). For any unsuccessful iteration \(k\in\mathcal{U}\), \(\phi(\xi_{k}+|\Delta_{k}|\mathbf{d}_{k})\geq\phi(\xi_{k})-c\Delta_{k}^{2}\), the mean value theorem establishes that:  
\[-c\Delta_{k}^{2} \leq\phi(\xi_{k}+|\Delta_{k}|\mathbf{d}_{i})-\phi(\xi_{k})\] \[=\langle\
abla\phi(\xi_{k}+\alpha_{k}|\Delta_{k}|\mathbf{d}_{i}), \mathbf{d}_{i}\rangle|\Delta_{k}|\]  
for some \(\alpha_{k}\in[0,1]\).