Guillaume Lameynardie

Underuse of parallel ressources arises in two cases :

During the poll step of the MADS algorithm, the objective and constraints functions are evaluated near the best incubent following directions of a positive spanning set in the search space. As a performance issue, the software NOMAD 4 that implements MADS, uses a positive basis, which is a positive spanning set of minimal cardinality. For a problem of dimension n, this positive basis is composed of 2n orthogonal directions and so the poll step leads to 2n evaluations of the objective and constraints. Nowadays, access to massively parallel ressources is easier. For instance, the research laboratory of Hydro-Québec (IREQ) owns a supercomputer made of 152 nodes and 36 CPUs per node. In this context, at the poll step, the execution of NOMAD 4 leads to an underuse of the available ressources. Indeed, the number of evaluations is far lower than the number of available processors. It seems relevant to evaluate the objective and constraints in a larger number of polling directions.

Intensives polling strategies

Three points generation strategies are described in order to generate more than 2n points. Those strategies differs in the geometry given to the polling points.

• Multi poll aims to generate the neighbours of neighbours polling points. For positive basis of 2n points, this strategy generates (2n+1)x2n points.
• Oignon poll aims to reflect the behaviour of MADS when the algorithm is failing to improve the objective function several times in a row. Polling points are generated on frames of different size, all centerd on the best incubent.
• Enriched poll aims to generate more than *2n* points by generating points inside the poll frame.

Dynamic intensification

The number of points generated with Oignon and Enriched poll can be decided at each iteration k of MADS. A criterion on increasing the number of polling directions is set up in order to feed processors with more evaluations only when it seems to be relevant. Hence, one avoid generating too much evaluations when improving the objectif function seems to be easy. The intensification factor is said to be linear when 2n polling directions are added between two iterations that fails to improve the objective function. It is said to be exponential when the number of polling directions is multiplied by 2 between two iterations that fails to improve the objective function

When an iteration successfully improves the objective function, it is possible to reduce the number of polling directions. The intensification is said to be without memory if when a success is met, the number of polling directions of the next iteration is reset to 0. With memory, the number of polling directions is reduced the same way it is increased with the intensification factor.

Efficient ordering of the evaluation stack

The generation of a larger amount of points per iteration lead to the problem of evaluating those points. Those evaluaitons represents a workload that one can order by deciding which evaluaution must be completed on which processor. This ordering is relevant when the operator has access to an easy estimation of the time or the workload of each evaluation.