Group for Research in Decision Analysis

Selection of variables in parallel space decomposition for the mesh adaptive

Stéphane Alarie, Nadir Amaioua, Charles Audet, Sébastien Le Digabel, and Louis-Alexandre Leclaire

The parallel space decomposition of the Mesh Adaptive Direct Search algorithm (PSD-MADS 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 4,000 variables. The results show an important improvement over the original version of PSD-MADS.

, 20 pages