Extensions à l'algorithme de recherche directe MADS pour l'optimisation non lisse

Nonsmooth optimization applies to problems that do not possess the derivative structure usually required by conventional optimization methods. These problems occur in a wide variety of fields, including engineering, where real situations are modelled or simulated using complicated functions, usually computer codes without exploitable structure.

A recent class of algorithms developed in 2006, the Mesh Adaptive Direct Search, or MADS [20], is specially designed for these problems, with a hierarchical convergence analysis based on the Clarke calculus for nonsmooth functions.

This thesis suggests improvements to MADS, through three extensions corresponding to three papers accepted or submitted for publication: The first extension [12] describes the introduction of the Variable Neighborhood Search (VNS) metaheuristic [68, 100], commonly used in combinatorial optimization, into MADS. The complementarity of the two methods increases the stability of the results.

The second [22] describes PSD-MADS, an asynchronous parallelization of MADS and targets problems with a large number of variables, for the first time in the order of several hundred variables.

The third extension [6] provides a deterministic new implementation of MADS, ORTHOMADS, the previous and original one (LTMADS) being defined with a random component. It also provides a better distribution of search directions in the space of variables at every iteration of MADS.

Each of these extensions is backed by a rigorous convergence analysis based on the Clarke calculus for nonsmooth functions and is tested on sets of problems including analytic problems from the literature as well as real problems originating from various applications of engineering. The results obtained support the conclusion that the proposed extensions are improvements of MADS.