Introduction

Note

NOMAD = Nonlinear Optimization by Mesh Adaptive Direct Search

Note

Please cite NOMAD with Reference [AuLeRoTr2021].

NOMAD is a software application for simulation-based optimization. It can efficiently explore a design space in search of better solutions for a large spectrum of optimization problems. NOMAD is at its best when applied to blackbox functions.

_images/blackbox.png

Such functions are typically the result of expensive computer simulations which have no exploitable property such as derivatives, may be contaminated by noise, may fail to give a result even for feasible points.

NOMAD is a C++ implementation of the Mesh Adaptive Direct Search (MADS) algorithm (see references [AbAuDeLe09], [AuDe2006], [AuDe09a] for details) designed for constrained optimization of blackbox functions in the form

\[\min_{x \in \Omega} f(x)\]

where the feasible set \(\Omega = \{ x \in X : c_j(x) \leq 0, j \in J\} \subset \mathbb{R}^n\), \(f, c_j : X \rightarrow \mathbb{R} \cup \{ \infty \}\) for all \(j \in J= \{ 1,2,\ldots,m \}\), and where \(X\) is a subset of \(\mathbb{R}^n\).

NOMAD also implements the DMultiMads algorithm (see references [BiLedSa2020] and Advanced functionalities) for solving multiobjective optimization problems.

Basics of the MADS algorithm

At the core of NOMAD resides the Mesh Adaptive Direct Search (MADS) algorithm. As the name implies, this method generates iterates on a series of meshes with varying size. A mesh is a discretization of the space of variables. However, also as the name implies, the algorithm performs an adaptive search on the meshes including controlling the refinement of the meshes. The reader interested in the rather technical details should read Reference [AuDe2006].

The objective of each iteration of the MADS algorithm, is to generate a trial point on the mesh that improves the current best solution. When an iteration fails to achieve this, the next iteration is initiated on a finer mesh.

Each iteration is composed of two principal steps called the Search and the Poll steps. The Search step is crucial in practice because it is so flexible and can improve the performance significantly. The Search step is constrained by the theory to return points on the underlying mesh, but of course, it is trying to identify a point that improves the current best solution.

The Poll step is more rigidly defined, though there is still some flexibility in how this is implemented. The Poll step generates trial mesh points in the vicinity of the best current solution. Since the Poll step is the basis of the convergence analysis, it is the part of the algorithm where most research has been concentrated.

A high-level presentation of MADS is shown in the pseudo-code below.

_images/mads-algo.png

Using NOMAD

Warning

NOMAD does not provide a graphical user interface to define and perform optimization.

Minimally, users must accomplish several tasks to solve their own optimization problems:

- Create a custom blackbox program(s) to evaluate the functions \(f\) and \(c_j\) OR embed the functions evaluations in C++ source code to be linked with the NOMAD library.

- Create the optimization problem definition in a parameter file OR embed the problem definition in C++ source code to be linked with the NOMAD library.

- Launch the execution at the command prompt OR from another executable system call.

Users can find several examples provided in the installation package and described in this user guide to perform customization for their problems. The installation procedure is given in Installation. New users should refer to Getting started. The most important instructions to use NOMAD are in NOMAD usage. In addition, tricks that may help solving specific problems and improve NOMAD efficiency are presented in Tricks of the trade. Advanced parameters and functionalities are presented in Advanced functionalities.

Supported platforms and environments

NOMAD source codes are in C++ and are identical for all supported platforms. See Installation for details to obtain binaries from the source files.

Authors and fundings

The development of NOMAD started in 2001. Three versions of NOMAD have been developed before NOMAD 4. NOMAD 4 and NOMAD 3 are currently supported. NOMAD 4 is almost a completely new code compared with NOMAD 3.

NOMAD 4 has been funded by Huawei Canada, Rio Tinto, Hydro-Québec, NSERC (Natural Sciences and Engineering Research Council of Canada), InnovÉÉ (Innovation en Énergie Électrique) and IVADO (The Institute for Data Valorization)

NOMAD 3 was created and developed by Charles Audet, Sebastien Le Digabel, Christophe Tribes and Viviane Rochon Montplaisir and was funded by AFOSR and Exxon Mobil.

NOMAD 1 and 2 were created and developed by Mark Abramson, Charles Audet, Gilles Couture, and John E. Dennis Jr., and were funded by AFOSR and Exxon Mobil.

The library for dynamic surrogates (SGTELIB) has been developed by Bastien Talgorn (bastien-talgorn@fastmail.com), McGill University, Montreal. The SGTELIB is included in NOMAD since version 3.8.0.

Developers of the methods behind NOMAD include:

- Mark A. Abramson (abramson@mathematics.byu.edu), Bringham Young University.

- Charles Audet (https://www.gerad.ca/Charles.Audet), GERAD and Département de mathématiques et de génie industriel, École Polytechnique de Montréal.

- J.E. Dennis Jr. (http://www.caam.rice.edu/∼dennis), Computational and Applied Mathematics Department, Rice University.

- Sébastien Le Digabel (http://www.gerad.ca/Sebastien.Le.Digabel), GERAD and Département de mathématiques et de génie industriel, École Polytechnique de Montréal.

- Viviane Rochon Montplaisir (https://www.linkedin.com/in/montplaisir).

- Christophe Tribes, GERAD (https://www.gerad.ca/en/people/christophe-tribes) and Département de mathématiques et de génie industriel, École Polytechnique de Montréal.

Acknowledgments

The developers of NOMAD wish to thank Maud Bay, Eve Bélisle, Vincent Garnier, Michal Kvasnička, Alexander Lutz, Rosa-Maria Torres-Calderon, Yuri Vilmanis, Martin Posch, Etienne Duclos, Emmanuel Bigeon, Walid Zghal, Jerawan Armstrong, Stéphane Alarie and Klaus Truemper for their feedbacks and tests that significantly contributed to improve NOMAD.

Some features of NOMAD have been developed under the impulsion of enthusiastic users/developers/interns: Andrea Ianni, Florian Chambon, Mohamed Sylla, Quentin Reynaud, Amina Ihaddadene, Bastien Talgorn, Nadir Amaioua, Catherine Poissant, Alexandre Expert and Victoire Houyau Pedascoll.

We also wish to thank Pascal Côté and Jan Provaznik for their contribution in the development and distribution of the Python interface PyNomad and Jonathan Currie for the development of the foundations for a strong NOMAD interface for MATLAB. Another special thank to Jean-Max Redonnet for pushing the development of the Java Swig interface.

The contributions of Miguel Anjos, Romain Couderc, Miguel Diago Martinez, Solène Kojtych, Guillaume Lameynardie, Wim Lavrijsen, Alexis Montoison, Caroline Rocha, Ludovic Salomon, Renaud Saltet, Yassine Diouri, Xavier Lebeuf and Tangi Migot was highly appreciated during the development and testing of NOMAD 4.

License

NOMAD is a free software application released under the GNU Lesser General Public License v 3.0. As a free software application you can redistribute and/or modify NOMAD source codes under the terms of the GNU Lesser General Public License.

For more information, please refer to the local copy of the license obtained during installation. For additional information you can contact us or visit the Free Software Foundation website.

Contact us

All queries can be submitted by email at

In particular, feel free to ask technical support for problem specification (creating parameter files or integration with various types of simulations) and system support (installation and plateform-dependent problems).

Bug reports and suggestions are valuable to us! We are committed to answer to posted requests as quickly as possible.