====== Steps and Algorithms ======

===== Steps =====
An algorithm consists of a succession of steps.

For instance, this is the MADS algorithm, simplified:
<code>
Step 0 - Initialization
Repeat:
    Step 1 - Update
    Step 2 - Search
    Step 3 - Poll
Until termination condition is reached.
Step 4 - Termination
</code>

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:\\
{{:groupe-dfo-bbo:projets:nomad:mads2.png?600|}}

===== Algorithms =====
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. \\
{{:groupe-dfo-bbo:projets:nomad:algorithm2.png?600|}}

===== Search Methods =====
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: 
  - Speculative Search
  - Quad Model Search
  - Sgtelib Model Search
  - Latin Hypercube Search
  - 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.

{{:groupe-dfo-bbo:projets:nomad:searchmethod2.png?600|}}

===== Search Method using Algorithms =====
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. 
{{ :groupe-dfo-bbo:projets:nomad:searchwithalgorithm.png?400 |}}
===== Poll =====
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.
{{:groupe-dfo-bbo:projets:nomad:poll.png?400|}}

===== MADS Algorithm =====
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.\\
{{:groupe-dfo-bbo:projets:nomad:madsalgorithmclassic.png?600|}}

===== Group Evaluations =====
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.\\
{{:groupe-dfo-bbo:projets:nomad:megasearchpoll.png?600|}}