# A Direct Search Algorithm for Global Optimization
## 1 Introduction  
An optimization problem consists of finding an element of a given set that minimizes (or maximizes) a certain value associated with each element of the set. In this paper, we are interested in minimizing the value of a real valued function defined over the \(n\)-dimensional Euclidean space. Without loss of generality, our problem is equivalent to minimizing a real valued function over the open unit \(n\)-box \((0,1)^{n}\subset\mathbb{R}^{n}\).  
Let \(f\) denote a real function defined over the open unit \(n\)-box \((0,1)^{n}\subset\mathbb{R}^{n}\), and consider the following optimization problem:  
\[\min\{f(\mathbf{x}):\mathbf{x}\in(0,1)^{n}\} \tag{1}\]  
The function to be minimized \(f\) is called the cost function and the unit \(n\)-box \((0,1)^{n}\) is the search space of the problem. Our aim is to obtain a point \(\mathbf{x}^{*}\in(0,1)^{n}\), such that the cost function \(f\) attains a minimum at \(\mathbf{x}^{*}\), _i.e._, \(f(\mathbf{x}^{*})\leq f(x)\), \(\forall\mathbf{x}\in(0,1)^{n}\). We shall make the following assumption:  
* The cost function \(f\) attains its minimum at a point of the search space. If the function \(f\) is continuously differentiable in \((0,1)^{n}\), then: \[\
abla f(\mathbf{x}^{*})=0,\ \mathbf{x}^{*}\in(0,1)\] (2)  
Many optimization methods make use of the stationarity Equation (2) to compute candidate optimizer points. These methods require the explicit knowledge of the gradient, but they do not guarantee that the point obtained is an optimizer, except for a pseudoconvex function.  
We shall also make an additional assumption that will restrict our alternatives to design a procedure to compute the optimum.  
* The gradient of the cost function is not available for the optimization mechanism.  
Consequently, only function evaluations can be used to compute the minimum.  
**Remark 1**.: The problem Equation (1) is equivalent to unconstrained optimization. Consider the following unconstrained optimization problem:  
\[\min\{f(\boldsymbol{\xi}):\boldsymbol{\xi}\in\mathbb{R}^{n}\} \tag{3}\]  
and let \(\boldsymbol{\xi}=\begin{bmatrix}\xi_{1}&\xi_{2}&\cdots&\xi_{n}\end{bmatrix}^ {T}\) be the vector of variables of the cost function. The invertible transformation:  
\[x_{i}=\frac{1}{1+e^{-\xi_{i}}} \tag{4}\]  
transforms the real line into the unit interval. Consequently, we can convert an unconstrained minimization problem into an open unit \(n\)-box constrained minimization problem by transforming each of its variables. Similarly, the linear transformation:  
\[x_{i}=\frac{\xi_{i}-a}{b-a} \tag{5}\]  
converts the open interval \((a,b)\) into the open unit interval. Consequently, both unconstrained and arbitrary open \(n\)-box optimization problems are included in our formulation. Furthermore, under Assumption A2 and by choosing appropriate values of \(a\) and \(b\), the global minimum of function \(f\) is attained in an interior point of the open \(n\)-box \((a,b)^{n}\).  
The rest of this paper is organized as follows. Section 2 is a review of the literature on direct search and global optimization algorithms. The direct search algorithm for global optimization is designed in Section 3. The algorithm makes use of a set of simplex-based operations for a transformed cost function. We begin by reviewing some basic results about \(n\)-dimensional simplices that will be used later to define the algorithm and study its properties. Then, we will introduce a transformation of the cost function that is crucial to improving the exploratory properties of the algorithm. Finally, we conclude this section by explaining the algorithm in detail and analyzing its convergence properties. In Section 4, an experimental study of the algorithm's performance is accomplished by using three well-known test functions. Its performance is also compared to other global optimization strategies. The conclusions are presented in Section 5.