2018 Optimization Days

HEC Montréal, Québec, Canada, 7 — 9 May 2018

Schedule Authors My Schedule

TB4 Blackbox and derivative-free optimization III

May 8, 2018 03:30 PM – 05:10 PM

Location: Hélène Desmarais (48)

Chaired by Sébastien Le Digabel

3 Presentations

  • 03:30 PM - 03:55 PM

    A new strategy for selecting variables in the parallel space decomposition for the mesh adaptive direct search algorithm

    • Nadir Amaioua, presenter, Polytechnique Montréal
    • Sébastien Le Digabel, GERAD, Polytechnique Montréal
    • Charles Audet, GERAD - Polytechnique Montréal
    • Stéphane Alarie, Institut de recherche d'Hydro-Québec
    • Louis-Alexandre Leclaire, IREQ

    The parallel space decomposition of the Mesh Adaptive Direct Search algorithm (PSD-MADS) is an asynchronous parallel technique for derivative-free optimization. PSD-MADS uses a simple generic strategy to select variables used to build subproblems from the original problem. The present work defines a new strategy for selecting variables combining between a statistical technique to quantify the influence of variables on the outputs and a classification technique to analyze the statistical results and provide clusters of influential variables. This new approach improves upon the random strategy used in PSD-MADS and treats larger problems up to 4000 variables.

  • 03:55 PM - 04:20 PM

    A taxonomy of constraints for blackbox-based optimization

    • Stefan Wild, presenter, Argonne National Laboratory
    • Sébastien Le Digabel, GERAD, Polytechnique Montréal

    The types of constraints encountered in black-box simulation-based optimization problems differ significantly from those treated in nonlinear programming. We introduce a characterization of constraints to address this situation. We provide formal definitions for several constraint classes and present illustrative examples in the context of the resulting taxonomy. We believe that this taxonomy is a critical step for modeling and problem formulation, as well as optimization software development and deployment. Such a taxonomy can also be used as the basis for a dialog with practitioners in moving problems to increasingly solvable branches of optimization as well as informing the development of new classes of mathematical optimization algorithms. Attendees are invited to provide constraint (counter)examples as part of this effort.

  • 04:20 PM - 04:45 PM

    The mesh adaptive direct search algorithm for granular and discrete variables

    • Sébastien Le Digabel, presenter, GERAD, Polytechnique Montréal
    • Charles Audet, GERAD - Polytechnique Montréal
    • Christophe Tribes, Polytechnique Montréal

    The mesh adaptive direct search (MADS) algorithm is designed for blackbox optimization problems where the functions defining the objective and the constraints are typically the outputs of a simulation seen as a blackbox. It is a derivative-free optimization method designed for continuous variables and is supported by a convergence analysis based on the Clarke calculus. This work introduces a modification to the MADS algorithm so that it handles granular variables, i.e. variables with a controlled number of decimals. This modification involves a new way of updating the underlying mesh so that the precision is progressively increased. A corollary of this new approach is the ability to treat discrete variables. Computational results are presented using the NOMAD software, the free C++ distribution of the MADS algorithm.