Multidirectional search: A direct search algorithm for parallel machines

In recent years there has been a great deal of interest in the development of optimization algorithms which exploit the computational power of parallel computer architectures. We have developed a new direct search algorithm, which we call multi-directional search, that is ideally suited for parallel computation. Our algorithm belongs to the class of direct search methods, a class of optimization algorithms which neither compute nor approximate any derivatives of the objective function. Our work, in fact, was inspired by the simplex method of Spendley, Hext, and Himsworth, and the simplex method of Nelder and Mead. The multi-directional search algorithm is inherently parallel. The basic idea of the algorithm is to perform concurrent searches in multiple directions. These searches are free of any interdependencies, so the information required can be computed in parallel. A central result of our work is the convergence analysis for our algorithm. By requiring only that the function be continuously differentiable over a bounded level set, we can prove that a subsequence of the points generated by the multi-directional search algorithm converges to a stationary point of the objective function. This is of great interest since we know of few convergence results for practical direct search algorithms. We also present numerical results indicating that the multi-directional search algorithm is robust, even in the presence of noise. Our results include comparisons with the Nelder-Mead simplex algorithm, the method of steepest descent, and a quasi-Newton method. One surprising conclusion of our numerical tests is that the Nelder-Mead simplex algorithm is not robust. We close with some comments about future directions of research