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 [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.

Indexing (details)


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
Author
Le Digabel, Sebastien
Number of pages
140
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
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