Nelder-Mead Simplex Optimization Routine for Large-Scale Problems: A Distributed Memory Implementation

The Nelder-Mead simplex method is an optimization routine that works well with irregular objective functions. For a function of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$n$$</EquationSource> </InlineEquation> parameters, it compares the objective function at the <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$n+1$$</EquationSource> </InlineEquation> vertices of a simplex and updates the worst vertex through simplex search steps. However, a standard serial implementation can be prohibitively expensive for optimizations over a large number of parameters. We describe an implementation of the Nelder-Mead method in parallel using a distributed memory. For <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$p$$</EquationSource> </InlineEquation> processors, each processor is assigned <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$(n+1)/p$$</EquationSource> </InlineEquation> vertices at each iteration. Each processor then updates its worst local vertices, communicates the results, and a new simplex is formed with the vertices from all processors. We also describe how the algorithm can be implemented with only two MPI commands. In simulations, our implementation exhibits large speedups and is scalable to large problem sizes. Copyright Springer Science+Business Media New York 2014