Optimization Online


Selection of variables in parallel space decomposition for the mesh adaptive direct search algorithm

Stéphane Alarie(alarie.stephane***at***ireq.ca)
Nadir Amaioua(nadir.amaioua***at***gerad.ca)
Charles Audet(charles.audet***at***gerad.ca)
Sébastien Le Digabel(sebastien.le-digabel***at***polymtl.ca)
Louis-Alexndre Leclaire(leclaire.louis-alexandre***at***ireq.ca)

Abstract: The parallel space decomposition of the Mesh Adaptive Direct Search algorithm (PSDMADS proposed in 2008) is an asynchronous parallel method for constrained derivative-free optimization with large number of variables. It uses a simple generic strategy to decompose a problem into smaller dimension subproblems. The present work explores new strategies for selecting subset of variables defining subproblems to be explored in parallel. These strategies are based on ranking the variables using statistical tools to measure their influence on each output. Determining the most influential variables is performed using the k-mean algorithm. In addition, an hybrid approach using both the k-mean method and the random selection of variables to build subproblems is presented. These new methods improve the decomposition of the problem into smaller more relevant subproblems. Computational tests are conducted on a set of constrained instances with up to 4000 variables. The results show an important improvement over the original version of PSDMADS.

Keywords: Parallelism; Derivative-free optimization; k-mean algorithm; PSDMADS; Mesh adaptive direct search.

Category 1: Nonlinear Optimization

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

Citation: Technical report, Cahier du GERAD G-2018-38, 2018.

Download: [PDF]

Entry Submitted: 06/12/2018
Entry Accepted: 06/12/2018
Entry Last Modified: 06/12/2018

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 Optimization Society