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

Abstract

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, 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 describes the introduction of the Variable Neighborhood Search (VNS) metaheuristic, commonly used in combinatorial optimization, into MADS. The complementarity of the two methods increases the stability of the results.

The second 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 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.

Alternate abstract:

L'optimisation non lisse s'applique aux problemes ne possedant pas la structure derivative usuelle requise par les methodes d'optimisation classiques. Ces problemes se rencontrent dans divers domaines, notamment l'ingenierie. En effet, la plupart des situations reelles se modelisent ou se simulent par des fonctions compliquees, typiquement des codes informatiques, dont on ne peut exploiter la structure.

Une recente famille d'algorithmes developpee en 2006, la recherche directe sur treillis adaptifs (MADS), est specialement concue pour ces problemes, et assure des proprietes de convergence basees sur le calcul de Clarke des fonctions non lisses. 

Cette these propose des ameliorations a MADS, sous la forme de trois extensions correspondant a autant d'articles acceptes ou soumis pour publication: la premiere permet de coupler MADS a la meta-heuristique de recherche a voisinage variable (VNS) utilisee habituellement en optimisation combinatoire. L'aspect complementaire des deux methodes accroit la stabilite des resultats.  

La deuxieme extension decrit PSD-MADS, une parallelisation de MADS asynchrone permettant de resoudre des problemes de plus grande taille, pour la premiere fois de l'ordre de plusieurs centaines de variables. 

La derniere extension donne une alternative deterministe, ORTHOMADS, a l'implementation originale de MADS donnee en, LTMADS, qui comportait une composante aleatoire. Elle assure aussi une repartition egalement distribuee des directions de recherche a chaque iteration de MADS. 

Chacune de ces extensions est soutenue par une analyse de convergence rigoureuse basee sur le calcul non lisse de Clarke. Elle est de plus testee numeriquement sur des ensembles de problemes tests comprenant des problemes analytiques de la litterature ainsi que des problemes reels tires de diverses application du genie. Les resultats obtenus permettent d'avancer que les extensions de cette these constituent bien des ameliorations de MADS.