# A Direct Search Algorithm for Global Optimization
## 2 Direct Search Methods and Global Optimization
### Local Optimization Approaches  
Since there does not exist a suitable algorithmic characterization of global optima, most optimizers are based on local optimization. The most important derivative-free local based methods are pattern search methods and model-based search methods. Pattern search methods perform local exploration of the cost function on a pattern (a set of points conveniently selected). The Hooke-Jeeves [13] method and the Nelder-Mead simplex method [14] are two well-known examples of pattern search local methods.  
The method of Hooke and Jeeves consists of a sequence of exploratory moves from a base point in the coordinate directions, which, if successful, are followed by pattern moves. The purpose of an exploratory move is to acquire information about the cost function in the neighborhood of the current base point. A pattern move attempts to speed up the search by using the information already acquired about the function to identify the best search direction.  
The Nelder-Mead simplex algorithm belongs to the class of simplex-based direct search methods introduced by [PERSON] _et al._ in [15]. This class of methods evolves a pattern set of \(n+1\) vectors on an \(n\)-dimensional search space that is interpreted as the vertex set of a simplex, _i.e._, a convex \(n\)-dimensional polytope. Different simplex-based methods use different operators to evolve the vertex set. The Nelder-Mead algorithm starts by ordering the vertices of the simplex and uses five operators: reflection, expansion, outer contraction, inner contraction and shrinkage. At each iteration, only one of these operations is performed. As a result, a new simplex is obtained such that either contains a better vertex (a vertex that is better than the worst one and substitutes it) or has a smaller volume. From the point of view of the function value, every operator, except for the shrinkage, is productive and obtains a vertex that improves the worst one. The shrinkage operator reduces the volume of the simplex to guarantee algorithm termination. Unfortunately, the convergence of the Nelder-Mead simplex algorithm to a local minimizer is not guaranteed [16], and a number of modifications have been introduced to get convergence. Nevertheless, the Nelder-Mead simplex algorithm remains as one of the most popular direct search algorithms.  
Model-based search methods are based on the idea of using function evaluations to compute a model of the cost function and to obtain derivative approximations from this model. Many model-based methods are trust-region algorithms [17] that interpolate the cost function in some region of appropriate shape and size to obtain a good approximation of the cost function that can later be easily optimized on that region. Typically, the model to be adjusted is a fixed-order polynomial, and the trust region is a sphere in some norm of the search space. The model function is sequentially optimized in the trust region, and the trust region is updated for the next iteration until the approximated model satisfies a first-order optimality condition. Model-based methods also include [18; 19; 20]. During the last decade, there has been a considerable amount of work to handle constraints in the field of direct search methods. New algorithms have been developed to deal with bounds and linear inequalities [21; 22] smooth nonlinear constraints [23; 24] or non-smooth constraints [25; 26; 27]. In this work, we do not deal with constraints. Our aim here is to develop a simple and efficient algorithm that improves the heuristics-based optimization methods that are presently used to obtain the global minimum in a multidimensional and multimodal continuous function.