Optimization Online


Parallel Space Decomposition of the Mesh Adaptive Direct Search algorithm

Charles Audet (Charles.Audet***at***gerad.ca)
John E. Dennis, Jr. (dennis***at***rice.edu)
Sébastien Le Digabel (Sebastien.Le.Digabel***at***gerad.ca)

Abstract: This paper describes a parallel space decomposition PSD technique for the mesh adaptive direct search MADS algorithm. MADS extends a 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 the 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: SIAM J. Optim. Volume 19, Issue 3, pp. 1150-1170 (2008), (http://dx.doi.org/10.1137/070707518).


Entry Submitted: 04/16/2008
Entry Accepted: 04/16/2008
Entry Last Modified: 11/12/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society