Parallel Space Decomposition of the Mesh Adaptive Direct Search algorithm

Charles Audet (Charles.Audetgerad.ca)
John E. Dennis, Jr. (dennisrice.edu)
Sebastien Le Digabel (Sebastien.Le.Digabelgerad.ca)

Abstract: This paper describes a Parallel Space Decomposition (PSD) technique for the Mesh Adaptive Direct Search (MADS) algorithm. MADS extends Generalized Pattern Search for constrained nonsmooth optimization problems. The objective of the present work is to obtain good solutions to larger problems than the ones typically solved by MADS. The new method (PSD-MADS) is an asynchronous parallel algorithm in which the processes solve problems over subsets of variables. The convergence analysis based on the Clarke calculus is essentially the same as for the MADS algorithm. A practical implementation is described and some numerical results on problems with up to 500 variables illustrate advantages and limitations of PSD-MADS.

Keywords: Parallel Space Decomposition, Mesh Adaptive Direct Search (MADS), Asynchronous parallel algorithm, Nonsmooth optimization, Convergence analysis.

Category 1: Applications -- OR and Management Sciences

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: Tech. Report - Les Cahiers du GERAD - G-2007-81 (www.gerad.ca). Submitted to SIAM Journal on Optimization (in revision).

Download: [PDF]

Entry Submitted: 04/16/2008
Entry Accepted: 04/16/2008
Entry Last Modified: 04/16/2008

Modify/Update this entry