RSCS: A parallel simplex algorithm for the Nimrod/O optimization toolset

Article type: Research Article

Authors: Lewis, Andrew | Abramson, David | Peachey, Tom

Affiliations: Division of Information Services, Griffith University, Brisbane, Qld, Australia. E-mail: a.lewis@griffith.edu.au | Department of Computer Science, and Software Engineering, Monash University, Melbourne, Vic., Australia. E-mail: {davida,tcp}@csse.monash.edu.au

Abstract: This paper describes a method of parallelisation of the popular Nelder-Mead simplex optimization algorithms that can lead to enhanced performance on parallel and distributed computing resources. A reducing set of simplex vertices are used to derive search directions generally closely aligned with the local gradient. When tested on a range of problems drawn from real-world applications in science and engineering, this reducing set concurrent simplex (RSCS) variant of the Nelder-Mead algorithm compared favourably with the original algorithm, and also with the inherently parallel multidirectional search algorithm (MDS). All algorithms were implemented and tested in a general-purpose, grid-enabled optimization toolset.

Keywords: Parallel programming, optimization, Nelder-Mead algorithm

Journal: Scientific Programming, vol. 14, no. 1, pp. 1-11, 2006