Steps and Algorithms

An algorithm consists of a succession of steps.

For instance, this is the MADS algorithm, simplified:

Step 0 - Initialization
Repeat:
    Step 1 - Update
    Step 2 - Search
    Step 3 - Poll
Until termination condition is reached.
Step 4 - Termination

Hence, NOMAD 4 has a Step class.

Each Step has start(), run(), and end methods.

The Steps are organized in a tree which is ran depth-first. For the aforementioned MADS algorithm, we have classes Initialization, Update, Search, Poll and Termination which all derive from base class Step.

For management reasons, the Search and Poll steps are regrouped under the Iteration step. The Update and Iteration steps are regrouped under the MegaIteration step. Each MegaIteration has one Update and multiple Iteration steps. MADS has one Initialization, multiple MegaIteration, and one Termination steps.

This gives a representation of the MADS algorithm:

The MADS algorithm implementation is generalized to an Algorithm class. The Algorithm class is used to implement MADS as well as other algorithms that are useful in NOMAD. It is generic and flexible enough for our needs. Already implemented algorithms are Nelder Mead, Sgtelib and Quad Models, Latin Hypercube, Phase One (to satisfy the extreme barrier constraints). Other algorithms such as Generalized Pattern Search (GPS) and Coordinate Search will also be implemented.

A NOMAD user may be interested in implementing a new algorithm, and it is easily done using the Algorithm class. In our experience though, the user input was more often than not in the form of a new Search method. As the MADS algorithm is conceived, it allows for user input of points that may be interesting to evaluate, based on the user knowledge of the problem. The only conditions is that the provided points are on the mesh (not detailed here).

NOMAD already provides multiple search methods:

1. Speculative Search
2. Quad Model Search
3. Sgtelib Model Search
4. Latin Hypercube Search
5. Nelder Mead Search

A search method basically generates points, and then evaluates them. When a new search method needs to be implemented, only the point generation method needs to be implemented, as the evaluation is the same for any search method.

A Search may be quite simple in its process for generating points. For example, Speculative Search's generated points are points in the direction of the last success. A Search may also be sophisticated and build a model, like Quad Model Search, or otherwise use a popular algorithm, like Nelder Mead Search. In these cases, an Algorithm is implemented separately. The Search can use the Algorithm to generate points. When the Algorithm is done generating points, the points are evaluated.

The Poll step is necessary for MADS' proof of convergence. Like the Searches, the Poll generates points, and then evaluates them. The Poll step is not currently customizable, apart from some parameters. An user that wants to reimplement the Poll differently may dive directly into the code, or implement it as a Search step.

From the previous schemas, the MADS Algorithm may be redrawn. Note that MegaIteration step is not useful for the comprehension of this schema, so it was skipped, along with the Update and Termination steps.

In the context of parallelism, we might want to generate many points before evaluating them. The point generation may occur for all searches steps and for the poll step of an Iteration before the evaluation is proceeded. In NOMAD 4, we call this step a MegaSearchPoll.