Abstract/Details

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

Le Digabel, Sebastien.   Ecole Polytechnique, Montreal (Canada) ProQuest Dissertations Publishing,  2008. NR46109.

Abstract (summary)

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.

Indexing (details)


Business indexing term
Subject
Operations research
Classification
0796: Operations research
Identifier / keyword
Applied sciences; Mesh adaptive direct search; Nonsmooth functions
Title
Extensions à l'algorithme de recherche directe MADS pour l'optimisation non lisse
Alternate title
Extensions to the MADS Forward Search Algorithm for Non-Smooth Optimization
Author
Le Digabel, Sebastien
Number of pages
140
Publication year
2008
Degree date
2008
School code
1105
Source
DAI-B 70/01, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
978-0-494-46109-9
University/institution
Ecole Polytechnique, Montreal (Canada)
University location
Canada -- Quebec, CA
Degree
Ph.D.
Source type
Dissertation or Thesis
Language
French
Document type
Dissertation/Thesis
Dissertation/thesis number
NR46109
ProQuest document ID
304805489
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
https://www.proquest.com/docview/304805489